Originally posted by: fbreuer

Hello everyone!

Given an LP in the form Ax >= b that Cplex has solved to optimality, I would like to do find the facets incident to the optimal solution. In other words, if x' is the optimal solution to Ax >= b and some objective function, I'd like to find a linearly independent set B of rows such that the corresponding submatrix A_B satisfies A_B x' = b_B.

What is the best way to achieve this?

I have made some attempts in figuring this out by myself, however I have run into several difficulties. I was hoping that I could simply get the basis of the solution found by Cplex' primal simplex algorithm to find the facet inequalities I am looking for. However, I have a number of questions:

1) Is the basis maintained by Cplex the one obtained after presolving, aggregation, etc? Is there a one-to-one correspondence between rows of the basis and rows of the original basis A anymore? If not, that is fine, I'd be happy to work with the transformed/presolved matrix A'.

2) What is the form of the problem after presolving, etc? A'x = b', x >= 0? If so, where can I access the rest of the matrix A', not just A'_B? And where can I get b'?

In the following cpx is my Cplex instance (in Python) after solving the LP.

3) Does cpx.solution.advanced.binvrow() refer to A' while cpx.solution.basis.get_row_basis() refers to the original A?

4) I noticed that, if cpx is my Cplex instance (in Python), then, after solving, cpx.solution.basis.get_row_basis() throws a TypeError, while cpx.solution.basis.get_col_basis() works fine. (This happens independently of whether I use the primal or dual simplex method.) Why is that? My original problem and the reduced version both have more constraints than variables, so I would expect a basis to be a subset of rows.

5) cpx.solution.advanced.binvrow() is the inverted basis matrix. However, my original matrix has only integer entries, and I'd much prefer to keep it that way, so I'd like to get the basis matrix itself, instead of its inverse, to avoid rounding errors. Is it possible to obtain the basis matrix directly without inverting binvrow()?

Thank you for any guidance!

Best,

Felix

Originally posted by: T_O

Let me write some (unordered) facts:

• CPLEX uses a column basis, not a row basis.
• Both rows and comlums have a basis status, but the status of a row is equivalent to the status of the corresponding slack variable.
• I never had any problems with the basis, when presolving is enabled AND there is a solution. You can use the basis as if presolving were disabled.
• Obtaining the (column) basis matrix is trivial. Just check which colums are basic and use them. For basic rows, just use unit vectors.
• Binvrow calculates (!) a row from the inverted (column) basis matrix.
• A nonbasic variable is a variable that is at one of its bounds (or attains some fixed value, only relevant for unbounded variables). If you have lower bound 0 and no upper bound, a nonbasic variable attains 0.
• There are so-called superbasic variables, but I don't know the details and I never experienced them.
• There is a tool called polymake that might also help you.

Hope this helps a little.

Best regards,
Thomas

Originally posted by: fbreuer

Thanks, that was very helpful. For posterity, here is a snippet of Python code to try it out.

def mult_sparsepair_list(sp,v):
    acc = 0
    k = len(sp.ind)
    for i in range(k):
        var = sp.ind[i]
        acc = acc + v[var]*sp.val[i]
    return acc

cpx = cplex.Cplex()
cpx.read("location.lp")
cpx.set_problem_type(cplex.Cplex.problem_type.LP) # relax problem by making it an LP
cpx.solve()

def check_slack(cpx,i):
    x = cpx.solution.get_values()
    row_basis = cpx.solution.basis.get_basis()[1]
    b = cpx.linear_constraints.get_rhs(i)
    row = cpx.linear_constraints.get_rows(i)
    Ax = mult_sparsepair_list(row,x)
    print "is slack: %d, lhs: %f, rhs: %f" % (row_basis[i],Ax,b)

for i in range(cpx.linear_constraints.get_num()):
    check_slack(cpx,i)

This prints something like

is slack: 1, lhs: 0.314286, rhs: 0.000000
is slack: 1, lhs: 0.314286, rhs: 0.000000
is slack: 1, lhs: 0.000000, rhs: 0.000000
is slack: 0, lhs: 0.000000, rhs: 0.000000
is slack: 0, lhs: 0.000000, rhs: 0.000000
is slack: 0, lhs: 0.000000, rhs: 0.000000

The important thing to note here is that row_basis[i] == 1 if the corresponding slack variable has slack. So the rows *in* the basis are actually those with row_basis[i] == 0. I am not quite sure that this is consistent with your terminology (nonbasic = at bound) since the Cplex documentation says that row_basis[i] == 1 stands for basic slack variables. But no matter the terminology, I think I get it now.

Also, it seems that there is a bug in the CPlex 12.6 Python API. Calling cpx.solution.basis.get_row_basis() throws an exception but cpx.solution.basis.get_basis()[1] works fine. Where do I report this sort of thing?

Originally posted by: T_O

I think you are wrong. If the problem is degnerate, a tight constraint can still have a basic slack variable (c.f. complementary slack). Despite of this, you can still obtain the slack value from CPLEX. Still, I am not sure, if this is what you really want. Do you just want to find out which constraints of the system are tight at the actual solution? Then just obtain the slack.

I cannot help you with the Python API as I do not use it. For bug reports, I think it is ok to post them here.

Best regards,
Thomas

Originally posted by: fbreuer

If the problem is degnerate, a tight constraint can still have a basic slack variable (c.f. complementary slack).

Yes, this can be seen in the third line of the example. row_basis[i] == 1 even though the lhs and the rhs are equal. (I probably should not have written "is slack" to denote the value of row_basis.)

What I want from the basis is to give me a linearly independent, full rank collection of rows that are all tight at the actual solution. Just as you point out, if I took all the rows with 0 slack, then I might get too many if the problem is degenerate and I would need to select a maximum cardinality linearly independent subset of those rows. It is my hope that the 0 of row_basis select such a subset for me - but I have not confirmed that yet.

Originally posted by: T_O

You also have to select the correct rows. Have a look at the attached file. a1 and a2 are facets, but obviously, you can only select (any) two of the constraints to define the optimal vertex in a linear independant way. I guess, you won't be able to ensure selecting the right constraints by looking at the basis status of the slack variables.

Best regards,
Thomas

Originally posted by: fbreuer

You are right, good point. But I am happy to select any collection of inequalities as long as the feasible region the selected inequalities define contain the polytope. It would be great if the inequalities happen to be facet-defining, but they do not have to. To phrase it geometrically, I am looking to obtain a simplicial cone with the optimal vertex as apex that contains the entire polytope defined by the linear program.

By the way, I know about polymake, but I am working with Cplex since I am mainly interested in solving MIPs and these geometric considerations are just a means to that end.

Again, thank you very much for your help Thomas!

Originally posted by: T_O

Hmm, maybe it helps to remove redundant inequalities in advance. You can achieve this by removing the inequality (or modifying its right-hand site) and using the left-hand site as objective function (min/max depending on >= / <= ). Then compare the objective value with the original right-hand site and see if the constraint is redundant. Keep in mind that there can still be degeneracy without redundant constraints, e.g. a pyramid with square as base and the apex being the optimal point of the LP.

On the other hand, reverse search algorithms (like LRS) might be helpful.

Best regards,
Thomas