Originally posted by: fabioftv

Hello,

I am trying to solve some linear benchmark problems using the CPXpivot subroutine. These problems are written in MPS format and do not include any slack, surplus, or artificial variables. My code first reads the MPS file and finds a starting basic feasible solution to the problem. I use the subroutine CPXgetbase (int CPXgetbase(CPXENVptr env, CPXLPptr lp, int *cstat, int *rstat))to obtain the correspondent basis. The basis returned is partitioned into the basis status of the columns in the LP problem object (cstat) and the basis status of the slack/surplus/artificial variable associated with each row in the constraint matrix (rstat).

However, CPXpivot can only handle cstat and not rstat. For instance, suppose a maximization problem with three variables and three constraints. Let the starting feasible basis be cstat = [1,1,0] and rstat = [0,0,1] where 1 represents a variable is basic and 0 a nonbasic variable at its lower bound. I can easily swap cstat[0] with cstat[2] by using CPXpivot(env, lp, 2, 0, CPX_AT_LOWER). However, I cannot swap cstat[0] with rstat[0]. This returns an illegal pivot.

Does anyone have suggestions on how to handle this issue? One way I though was to include the slack, surplus, or artificial variables into the MPS file but I guess there should be an easier way. Any help is appreciated.

Thanks

Originally posted by: BoJensen

I am not sure I completely understand your problem. You mention CPXPivot does not handle rows i.e (slack, surplus, or artificial variables), but the manual explicitly mention them. These are not variables added by the user, yes a user can add them explicitly, but then they will be treated like ordinary variables. What error message do you get by calling CPXPivot ? Could it be that you exchange two variables and the basis exchange leads to a singular basis ?

Originally posted by: fabioftv

Hello BoJensen,

Thanks for your quick response. The problem here is that CPLEX does not understand rstat as part of the basis and only cstat. For instance, if I use the routine CPXmbasewrite to write the basis into a BAS file I would have something like that:

NAME          TESTPROB.mps  Iterations 0  Rows 3  Cols 3
 XL X1        LIM1    
 XL X3        LIM3    
ENDATA

That is, only the actual basic variables show here but there is nothing about the slack variable that is also basic.

Regarding the error, this is more of a memory allocation problem. For example, cstat has size 3 and calling CPXpivot(env, lp, 5, 0, CPX_AT_LOWER) would result in an illegal pivot (CPLEX Error 1267: Illegal pivot). Even if I allocate cstat with size 6 for example, I would get the same error.

Do you have any other ideas other than adding the variables explicitly into the problem?

Thanks

Originally posted by: fabioftv

Hi Bojensen,

I actually figured out how to solve this issue. It is easier if you look at the basis from CPXgetbhead. This routine returns all elements of the basis, including slack/surplus/artificial variables, and the order these variables are allocated. From the previous example, CPXgetbhead would return something like [0,1,-3] where the first and second variables are basic and the slack variable of the third row is also basic. Thus, if you want to enter the slack variable associated with the second row in place of the first variable we just call CPXpivot(env, lp, -2, 0, CPX_AT_LOWER).

Thanks for the help.

Best.

Originally posted by: BoJensen

Good. Please mark the question answered/resolved, thank you.