Originally posted by: SystemAdmin

Dear Forum,

I'm trying to generate Gomory-Mixed-Integer-Cuts based on LP-Solutions provided by the CPLEX-LP solver.
Unfortunately the order of the rows of Simplex-Tableaus depends on the LP-Method, and the order of the Simplex-Tableau rows does not necessarily match the order of the variables of the LP-solution.

Let me illustrate this phenomenon with the following LP-Problem:

max x1 + x2

5 x1 + 3 x2 + 1 x3 = 15
2 x1 + 7 x2 + 1 x4 = 14

the basis of the solution consists of column 1 and column2.

If I order the basis by [column1, column2] the basis inverse is:
http:// 0.241379310344828 -0.103448275862069
http://-0.0689655172413793 0.172413793103448

If I order the basis by [column2, column1] the basis inverse is:
http://-0.0689655172413793 0.172413793103448
http:// 0.241379310344828 -0.103448275862069

now if i try to solve this LP-problem with CPLEX 12.2 by the default LP-solver and then try to view the basis inverse with the method binvrow

prob.solution.advanced.binvrow()
>>> [[0.24137931034482757, -0.10344827586206895], [-0.068965517241379296, 0.17241379310344826]]

the columns of the basis inverse are ordered by [colum1,column2].

However, if i first set the method of the LP-solver to dual-simplex and then try to view the basis inverse with the same command, the solution is ordered by [column2,column]

prob.solution.advanced.binvrow()
>>> [[-0.068965517241379296, 0.17241379310344826], [0.24137931034482757, -0.10344827586206895]]

.

Note that in both cases the values of the LP-solution are ordered by [column1,column2]:

prob.solution.get_values()
[2.172413793103448, 1.3793103448275863]

So, if I try to solve the LP-problem with the dual simplex method, the order of the LP-solution values does not agree with the order of simplex-tableau rows, which therefore causes my Gomory-Mixed-Integer-cut-method to choose the wrong simplex tableau row for the cut.

Is this behavior a bug in CPLEX? Is there a way in CPLEX to view the order of the basis variables of the simplex-tableau?
How would you choose the simplex-tableau row corresponding to a specific basis variable?

I have used the CPLEX-Python module and I've eattached the complete session.

Any help is highly appreciated.
Philipp
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

What you are missing to understand the simplex tableau is the magic method CPXgetbhead(). I guess it has a similar name in the Python API.

The simplex basis for a problem with n columns and m rows is an m by m quadratic matrix. Each column of the basis matrix corresponds to either a structural variable 0 <= j < n, or a slack variable for row 0 <= i < m. Consequently, the row of the basis inverse correspond to structural and slack variables as well.

The CPXgetbhead() method tells you the mapping. It provides a "head" vector of length m, with the interpretation:

• head[k] = j, if row k of the basis inverse corresponds to structural variable j,
• head[k] = -i-1, if row k of the basis inverse corresponds to the slack variable for row i.

Hope this helps.
Tobias
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

Thank you Tobias,

I found the function "prob.solution.basis.get_header()" which tells me the order of the basis.

Philipp
#CPLEXOptimizers
#DecisionOptimization