Originally posted by: Vincent Tkindt

I am currently trying to compute Beale's (also called Driebeek) penalties for the basic variables in an optimal solution of a LP.

I know that these coefficients can be obtained by means of calls to the CPXmdleave() function.

What I did is the following:

1. I retrieve, by means of CPXgetbhead() and CPXbinvarow(), the tableau of the simplexe once an optimal solution to the LP has been found. Notice, that I only consider basic structural variables and not the basic slacks (negative values in the array returned by CPXgetbhead()).

2. Then, for each structural basic variable (variables I created in my model), I compute the Beale/Driebeek Lj and Uj values (more precisely the slopes associated to these values, i.e. I do not multiply by xj or (1-xj) as I deal only with variables between 0 and 1).

 

For a given instance with about 1498 rows in the LP basis, 558 of these correspond to basic structural variables. For all these ones, but one, I compute the same values than those returned by CPXmdleave(). My problem is that for one basic structural variable, I found Lj=0 whilst CPXmdleave returns Lj=37.

When I look into the simplexe tableau this basic variable is only linked to a single non basic variable with a coefficient apj=-0.27 (all other coefficients of this row p are equal to 0, except for the column corresponding to the current basic variable for which the coefficient is equal to 1, as normal). The reduced cost of this non basic variable being 0, Beale coefficient Lj is necessarily equal to 0.

 

So, three options:

1. Either, there is some numerical instabilities within CPXbinvarow, thus leading to wrong apj coefficients returned by this function (so which would explain why I cannot get the same values than CPXmdleave),

2. The values returned by CPXmdleave may be incorrect (which I don't believe),

3. CPX mdleave don't really implement Beale (or Driebeek) penalties but other penalties (which I don't believe).

 

I have the code and the LP file corresponding to my problem in case...

 

If someone can help me.

 

Vincent

 

 

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

---

 So, three options:

1. Either, there is some numerical instabilities within CPXbinvarow, thus leading to wrong apj coefficients returned by this function (so which would explain why I cannot get the same values than CPXmdleave),

2. The values returned by CPXmdleave may be incorrect (which I don't believe),

3. CPX mdleave don't really implement Beale (or Driebeek) penalties but other penalties (which I don't believe).

---

Regarding option 1), CPXmdleave ultimately calls the same code as CPXbinvarow, so any sort of ill conditioning in the basis matrix is unlikely to

explain the behavior you saw.   Furthermore, CPXmdleave mostly calls routines used by the simplex method; it does almost no calculations at

all by itself.   But, it you want to check the condition number of the basis matrix, make a call to CPXgetdblquality right before your CPXmdleave call.

You can then get the condition number of the basis associated with the CPXmdleave call and determine if ill conditioning could be involved.   I doubt that is the case, as I don't think you would see inconsistent results for only one variable.

 

Is there anything special about the variable associated with the mismatch in values?   For example, does it have a finite upper bound while all the other variables do not?   Does the associated matrix column show any fundamental differences that might explain this (e.g. extremely large values, so that the computed value of 37 arises from round-off error)?

 

Another possibility is that the values you computed are somehow associated with a different variable, so that you aren't comparing the penalties for the same variable.   One way to check this would be to make this variable the first or last one in the model and see if the trouble persists.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Ed,

 

Thank you for your reply.

 

First, what do you mean by "the condition number" of the basis? I had a look to the documentation of CPLEX 12.6 for function CPXgetdblquality(), and below are some values returned for different parameters related to "condition number" (I put the call to that function right before the call to CPXmdleave  and after the LP has been solved):

Parameter                         |     Value

----------------------------------------------------------------

CPX_KAPPA                             235655.87252183366

CPX_EXACT_KAPPA              638480.62500000000

 

Let me provide you with further details on my LP model and its computed optimal solution :

* In my problem I have 25725 variables: x1 is a variable between -INF;+IINF / x2 to x99 are variables which are either defined in an interval [ri;+INF[ or ]-INF;di] depending on the variable / x100 to x25725 are variables between 0 and 1 (included).

* In the basis : 1498 rows among which 558 correspond to structural variables (others are slacks),

* Variable  x2274 is in the basis:

         *  x2274=0.216216216216....

          * when looking to the simplex tableau, the coefficients apj are all equal to 0, except:

                           *  -0.027027 for variable x19 (non basic variable) with reduced cost 0.00000. I have x19=1087.000.

                           *  1.0 for variable x2274 (which is normal) with reduced cost 0.000 for x2274 (which is normal).

          * A call to CPXmdleave() returns Lj=37.000 and Uj=0.000000.

          * When I compute Beale coefficients I get Lj=999999999.00 and Uj=0.00000 (High Value means for me that, there is no non basic variable which is eligible for the computation  of the penalty)

 

When I look into the basis to the column associated to variable x2274 I only get a coefficient apj=1.00 for row 140 which corresponds to variable x2274... so this is ok. All other coefficients are 0.

 

If you need more information....

 

Vincent

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Vincent,

               You found the items associated with condition number.  CPX_EXACT_KAPPA computes the exact condition number

as the product of the norm of the basis and norm of the basis inverse.  Since this can be expensive (equivalent to as much as 

m/2 simplex iterations, where m is dimension of the basis), CPX_KAPPA provides a computationally inexpensive estimate.  The specific

value of the condition number is not important; the order of magnitude is.   Note that both values have the same order of magnitude (1e+5)

in your case.    So, it's really up to you which one you choose.   Given the relatively small number of constraints in your model, the calculations

for CPX_EXACT_KAPPA should remain quite modest.   So, you can use that if you want.   But, given that only the order of magnitude matters,

you probably don't need to.   Also, condition numbers of 1e+5 are quite modest, so it's extremely unlikely that ill conditioning is involved in your

problem.

 

If you need more information on condition numbers, here are some resources.

http://orinanobworld.blogspot.com/2010/08/ill-conditioned-bases-and-numerical.html

http://www-01.ibm.com/support/docview.wss?uid=swg21399993

http://pubsonline.informs.org/doi/abs/10.1287/educ.2014.0130

 

 

Regarding your model, you wrote:

>>>>>

x2 to x99 are variables which are either defined in an interval [ri;+INF[ or ]-INF;di]

...

*  -0.027027 for variable x19 (non basic variable) with reduced cost 0.00000. I have x19=1087.000.

>>>>>>

Can you confirm that x19 has an upper bound of 1087 and a lower bound of -INF?

 

Also, do you get the same behavior if you run your program with CPLEX's scale parameter set to -1 so that scaling is disabled?

 

Ed

 

 

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Ed,

 

For your information, my problem is a minimization problem.

 

Variable x19 has an upper bound of +INF and a lower bound of 1087.00 : its value in the LP solution is consistent with the fact that it is a non basic variable.

 

As you suggested, I ran my program with CPXPARAM_Read_Scale set to -1. Nothing as changed.

 

I don't know so much the CPLEX command line interface but is it possible, if write a LP file of my model, to access to the coefficients of the simplex tableau?

 

... and my best wishes for 2016!

Vincent

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Vincent,

              The interactive CPLEX optimizer does not give access to tableau elements such as those given by CPXbinvarow, CPXbinvacol, or

other routines associated with solving linear equations associated with the basis matrix.    If you want to do that interactive, you could try

the Python API.

              Thomas is correct regarding CPXbinvarow and CPXbinvrow.   CPXbinvarow gives you the tableau coefficients only for the

structural variables, while CPXbinvrow gives you the tableau coefficients for the slacks.  

               Regarding the docs for CPXbinvrow, would it help if we changed it to (additions underlined):

 

>>>>

The routine CPXXbinvarow/CPXbinvarow computes the i-th row of BinvA where Binv represents the inverse of the matrix B and juxtaposition specifies matrix multiplication. In other words, it computes the i-th row of the tableau for the structural variables.   Use CPXbinvrow to compute the i-th row of the basis inverse, which corresponds to the i-th row of the tableau for the slack variables.

>>>>>>>

I'll take a closer look at the CPXmdleave program and get back to you on this.  Is x19 the only nonbasic variable at its lower bound in the optimal solution, or do you have other nonbasic variables that also reside at their lower bound, yet you get the expected result from the CPXmdleave program?

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Dear Ed,

 

for the modification in the documentation, I would also suggest more clarification about the links between functions like CPXbinvarow, CPXbinvrow, CPXgetbhead and the way to get reduced costs for both structural and slack non basic variables. It would be also to explain what are the values returned by CPXbinvarow and CPXbinvrow notably with respect to formal mathematical definition of the tableau coefficients. To my opinion, it would be preferable that these explanations are in the User Manual than in the description of these functions.

Currently, making links between formal mathematical definitions and CPLEX functions is difficult.

 

For the other point of your answer, variable x19 is not the only variable at its lower bound.

 

vincent

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

CPXbinvarow, CPXbinvrow and CPXgetbhead are advanced routines only available in the C API.   The user manual is more suited for info that is relevant for

all CPLEX APIs.    So, for those 3 routines, I think we need to address any deficiencies in the docs in the descriptions of those routines in the reference manual.

The docs edit I proposed strengthened the link between CPXbinvarow and CPXbinvrow.   Is there something else that you think would help in the description of

CPXgetbhead?

 

Regarding slacks and reduced costs, I see your point, and that info would be useful across all APIs.   I will see if we can add something in the docs, or perhaps

create a technote on the support.ibm.com site that provides more detailed info.  

 

Regarding the original issue with CPXmdleave, I'll take a closer look at the routine and see what it does.    One test you could try that might be interesting

would be to call CPXwriteprob to generate a SAV file of your model (including the optimal basis from which you can CPXmdleave).   Then take the

lpex2.c example and modify it to make a single call to CPXmdleave.   Then check the values it returns for x19 and confirm that they are the same

as in your program.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Now, regarding the CPLEX documentation :-)...

 

First, let me tell you that I don't think that the current CPLEX documentations are suffisant to explain how we can manage with CPLEX the simplex tableau and the reduced costs. Just adding wording in the reference manual for function CPXbinvarrow/CPXbinvrow is not sufficient. I spent a lot of time just looking at the description of CPLEX function due to a lack of centralisation in the information. A Tech Note or, even better, a more complete user manual, is necessary.

current problems with the documentation:

* The term matrix A of coefficient as used in CPLEX doc does not correspond to the mathematical definition of A in Ax=b (slack/surplus variables are missing) : this is misleading.

* It is not clear how bounds for slack/surplus variables are considered in CPLEX

* It is not obvious that CPLEX create slack variables even for '=' constraints.

 

I would rather suggest a nice Tech Note explaining in a simple way how to retrieve and manipulate the simplex tableau coefficient. I would be also in favour of explaining in that note how are computed the Driebeek penalities (but it sounds a bit out of the initial topic of this documentation add-on).

 

 

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Vincent,

              Thanks for taking the time to provide this feedback.   Here's what I've written up to try to address this; we're still deciding whether to include it in the user manual or as a technote.  I'm leaning towards the former.

 

>>>>>>>>
Slack Variables and Solution Values

For most use cases, the values of slack variables returned by CPLEX's solution routines can be viewed as the right hand
side of the constraint minus the value of the linear (or quadratic) expression in the left hand side, regardless
of the constraint sense.    Ranged
rows with finite lower and upper bounds will have slack values consisting of the value of the linear expression
minus the lower bound.    The slack variable values adhere to this convention regardless of the API in use.

However, a few use cases require additional information.   For all APIs, the proper interpretation of the
dual variables as reduced costs on slack variable depends on CPLEX's internal representation of the slacks.   In
that regard, CPLEX adds a nonnegative slack for <= constraints, adds an artificial variables with lower and
upper bounds of 0 to equality constraints, and subtracts a nonnegative surplus variable from >= constraints.
Thus, for >= constraints, the reduced cost on the slack is just the associated dual variable value, while for all other
constraints it is the negative of the dual value.

This convention is also relevant for C API users of the advanced linear programming routines to access
parts of the so-called simplex tableau.   First of all, slacks are handled implicitly and are not part of
the constraint matrix of structural variables passed to CPLEX via routines like CPXcopylp, CPXaddrows or
CPXaddcols.   Therefore, advanced routines CPXbinvarow and CPXbinvacol only generate
simplex row and column tableau information for structural variables.    The tableau row elements associated
with the slack variables are obtained by first calling CPXbinvrow to obtain the associated row of the
basis inverse, then negating the elements associated with the >= constraints.   Tableau columns for slack
variables are obtained by calling CPXbinvcol for the appropriate slack variable, then negating the elements
if the slack corresponds to a >= constraint.   

>>>>>>>>

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Ok for the proposed text. I would have maybe added a wording in the second paragraph to state that for '=' constraints a slack  variable is added but with value 0 in case of a feasible basis.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Dear Ed,

 

in addition to my message of yesterday, to compute Beale's penalties taking account of the slack variables, I need also to get access to the lower/upper bounds of the slack variables created by CPLEX. How can I do that (as well as retrieving their reduced cost)?

 

Thank you,

 

Vincent

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Vincent,

             The slacks and surplus variables for inequality constraints all have bounds of [0, infinity].   The "slacks" for equality constraints all have

bounds of [0,0].    This can be inferred from the documentation for CPXgetslacks or CPXgetsolution.  For >= constraints, CPLEX subtracts a nonnegative

surplus variable, while it adds a nonnegative slack for <= constraints.  I won't go into the details for ranged rows

here, but if you are using them in your model (which seems unlikely given you mentioned an LP format file, which doesn't use ranged rows),

let me know and I'll provide that info.

              Now that the representation of slacks is known, TO's post about the reduced cost is essentially correct:

>>>>>>>

Aren't the dual values (CPXgetpi) what you call "the reduced costs of the slack variables"? Maybe, you have to take additional care about the sign.

>>>>>>>

The reduced cost for any nonbasic variable is cj - y'A_j   where y are the dual variables.    For all slacks, we have cj = 0, and A_j is just a unit vector

with a +-1 in position i, where i corresponds to the row associated with the slack/surplus variable.    So, for <= constraints, the reduced cost of the slack variable is the negative of the dual variable for that constraint.   For >= constraints, the reduced cost of the surplus variable is then the dual variable itself.

Some optimizers (e.g. MINOS and I think MOSEK) use the right hand sides of constraints to create bounds on the slack variables, but CPLEX does not

do that.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Note that the repeating decimal -.027027027... = -1/37 (see

http://en.wikipedia.org/wiki/Repeating_decimal#Converting_repeating_decimals_to_fractions for how to do these

types of conversions in general).   Similarly, x2274=0.216216216216... = 8/37.

So, if we start to increase x19 from its lower bound of 1087, we will start to increase the basic variable  x2274 from its value of 8/37 at a

rate of 1/37.   Since x2274 is binary, we can only increase it to its upper bound of 1 before violating its bounds, to that means we can

increase x2274 by 29/37, which means we can increase x19 by 29 before driving x2274 above 1.    Since x19 has a negative tableau row coefficient

and resides at a lower bound, we cannot change x19 in a way that preserves feasibility and drives x2274 down to 0.   The change in objective

associated with branching up on fractional basic variable x2274 is the reduced cost on variable x19 multiplied by 29, the amount by which we

increase the nonbasic variable x19.   However, this analysis is based on the primal model rather than the dual, as it's still possible that the

increase in x19 by 29 will cause a loss of primal feasibility for some other basic variable that currently is feasible.

 

Regarding CPXmdleave, it does a dual simplex pivot associated with the primal infeasibility created by changing the bounds on x2274 to [1,1].

Given that the tableau row associated with basic variable x2274 only has a nonzero coefficient in the column associated with x19, the dual

simplex ratio test only need examine that tableau element and the reduced cost of x19.    So, if CPXmdleave returns a value of 37, that would

be consistent with a reduced cost of 1, not 0.

 

With this as background, I suggest the following.

1.  Double check that the reduced cost of x19 is 0.0.
2.  Make sure the upratio and downratio arrays you pass in to CPXmdleave are indexed in the same way as the indices array.   Thus, if x2274 is in position for of the indices array, look at upratio[4] for the value, but do not look in position 4 in the reduced cost array for the value of x19.   And, do not look in the 19th position in the upratio array for the value.
3. Regarding the previous suggestion, perhaps the simplest test would be to make a call to CPXmdleave where you only request the upratio and downratio value for a single basic variable, namely x2274.   If you try that, what result do you get?

 

If these tests don't help, please include the code fragment leading up to the CPXmdleave call in question, including the code that shows

how the arrays passed into this routine are set up, and also a SAV file of the model in question with the associated optimal basis (i.e. insert

a call to CPXwriteprob to export this SAV file just before the call to CPXmdleave).

 

 

 

Ed

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Ed,

 

Thank you. I am modifying my code and check it in order to be able to answer you and see if my problem is solved.Then, I will answer you.

 

But, I still have a question regarding on of your previous answer. You wrote:

The reduced cost for any nonbasic variable is cj - y'A_j   where y are the dual variables.    For all slacks, we have cj = 0, and A_j is just a unit vector

with a +-1 in position i, where i corresponds to the row associated with the slack/surplus variable.    So, for <= constraints, the reduced cost of the slack variable is the negative of the dual variable for that constraint.   For >= constraints, the reduced cost of the surplus variable is then the dual variable itself.

 

I am ok with that, but what happen for '=' constraints ? From theory, no slack/surplus variable should be created by CPLEX.

In practice I am wondering wether CPLEX  creates slack/surplus variables or not: when I look at the output of CPXbinvrow(j), then CPXgetnumrows() coefficients are returned for a given row j.

Again, when I call CPXgetpi(env,lp,pdRedCostSlacks,0,CPXgetnumrows(env,lp)-1) it works and dual variables corresponding to '=' constraints have a value of 0 (implying that the reduced cost of the corresponding slack/dual variable is 0).

 

=> This currently makes trouble when I compute Beale's coefficient and if my guess is correct then I will have to not consider the "CPLEX slack" variables created for '=' constraints.

 

vincent

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Ed,

 

my problem seems to be fixed now. In my code, as you and Thomas suggested, I know consider non basic structural and slack variables.

Notice that, as indicated in my previous message, CPLEX seems to create slack variables even for '=' constraints (which is not theoretically necessary). So I only consider non basic slack/surplus variables associated to <= and >= constraints.

 

Based on that new code, I can confirm that:

  * x19 has a reduced cost of 0,

  * There is only one non basic slack variable and it has a value of 027027027 with a reduced cost of 1.0 => So now my Lj coeffiicent is 37 like returned by CPXmdleave.

I tested on several instances and never found a difference between my computation and CPLEX computation of Beale's.

 

I agree with the explanation you gave about increasing x19. Similar arguments are true for non basic variables at their upper bound (but in that case simplex tableau coefficient must be of opposite sign: negative for the computation of Lj). If I understood correclty what you ment at the end of your paragraph, even if increasing x19 to 1 leads to primal infeasibilities, in the computation of Beale's Lj we don't care since it is defined as a min_j(redcost_j/apj) : if there are some primal infeasibilities it means that Lj is an improvable lower bound.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

Concerning the so-called artificial variables for =-constraints:

You are right, the do not seem necessary. But from a mathetical point of view and for the implementation side, they are very helpful. For the user, they should not be a problem as they should always have value 0 in the optimal solution. But during the run of e.g. the dual simplex, they can have non-zero values. Furthermore, it is very helpful to have an identity matrix inside the constraint set, because then you can always use it as initial basis for phase 1.

So in your implementation, these variables should not bring you into trouble.

Best regards,
Thomas

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

In addition to TO's (correct) comments, keep in mind that CPLEX's solution query routines can operate for LP bases that are associated with infeasible solutions.

In such cases, the slack (i.e. artificial) variable associated with an equality constraint can take on a nonzero value, and that value may be of interest.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

I agree.

But this should be documented that '=' constraints are associated a slack variable as returned by CPXbinvrow(). From a primal point of view it is not straightforward.

 

I strongly believe that CPLEX solver is implemented in an appropriate way with respect to mathematical programming, but my remarks are more about the links between math prog and the API which are not well documented. 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Ed,

 

do you know why only Driebeek's penalties are implemented? It sounds that there are some improved penalties for non basic variables in the literature...

 

 

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

Vincent,

               If by improved penalties you are referring to pseudo costs based on strong branching (i.e. run some dual simplex iterations

on both the up and down branch and look at the change in objective), CPLEX uses those by default in its variable selection.    But,

the CPXmdleave() routine and the associated Driebeek penalties were made available in CPLEX at least 20 years ago, and at that

time strong branching based penalties were still considered potentially too expensive.    If you are referring to something else in the

literature, please provide the references to this thread. 

             To a certain extent the CPXmdleave() routine was made unnecessary by subsequent additions to CPLEX's C API.   Specifically,

you could fix the basic variable for which you want to compute the penalty to 0 and 1, then call the CPXpivot routine to do one pivot and

see the objective change.    But, CPXmdleave() remains available.    I think it was made accessible to users because Bob Bixby, the original

creator of CPLEX, had numerous academic colleagues doing research that benefited from easily computing these values.

 

Ed

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

I was thinking about some other penalties/pseudo-costs. My concern is about boolean variable fixing.  I found some pseudo-costs improving Beale's penalties (Tomlin or Armstrong and Sinah) but it is not clear for me whether there are "exact" penalties or not: I think that they are only "pseudo-costs" as you mentionned, i.e. estimates in the change of the objective function (and so, sometimes they over-estimate the changes => they cannot be applied to do variable fixing to optimality).

I agree with you argumentation around CPXpivot(), but to the best of my knowledge doing a pivot operation is more time consuming than computing penalties. Ok, it is more efficient, but in the context of variable fixing, calling too much time CPXpivot() may result in an inefficient procedure (as far as running time is concerned) while you could have someting efficient by using instead penalties.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: EdKlotz

CPXmdleave essentially does just such a dual simplex pivot.   So, at least for Driebeek penalties, CPXmdleave() will offer no performance advantage over

doing the fixings yourself and calling CPXpivot.   It just saves a few lines of coding.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Another element: when I compute Beale's penalties, I use the coefficients are returned by CPXbinvarow(), ie. coefficients apj corresponding, for a given basic variable Xp, to non basic structural variables xj.... this includes all variables x1 to x25725.

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

Maybe, I am off the track, but do you remember that CPXbinvarow does not give the complete tableau, but only the part of the tableau corresponding to the structural variables? If you want to have what is typically called "tableau", you have to use CPXbinvarow and CPXbinvrow and select the nonbasic colums of both.

Best regards,
Thomas

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Dear Thomas,

 

I have not with me my notes but as far as I remember Beale's coefficients are not computed taking account of the slack variables. But may be I am wrong and at least, I did not took account of the non basic slack variables.

 

Can you  confirm that Beale's coefficients, as computed inside CPLEX, are a min() among non basic structural and slack variables?

 

Vincent

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

In any case, I was unsucessful in finding appropriate documentation about simplex advanced functions. The documentation provided with CPLEX is really poor on that aspects.

I spent a lot of hours in trying to understand how works CPXbinvarow and what it returns....

 

If you have more detailled documentation on functions related to simplex functions, I would be very happy to get them.

 

vincent

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

I cannot answer your first question as I never worked with these coefficients.

Concerning your second question, I think I can bring some light into the darkness. I first ran into the problem with CPXbinvarow when I tried to calculate my own Gomory mixed-integer cuts. There you need the "tableau", which in this case means B^-1*A_N, where A_N is the nonbasis matrix (or whatever it is called in English).

In CPLEX, you have the matrix A only belonging to the structural variables. But you also have the identity matrix belonging to the slack/surplus/artificial variables. So the "complete" matrix is ( A I ) and the nonbasis matrix is part of ( A I ), let's call it ( A I )_N. So the tableau is B^-1 * ( A I )_N. As far a I understood it, CPXbinvarow calculates a row of B^-1 * A and CPXbinvrow calculates a row of B^-1 (which is B^-1 * I).

So, let's do a small calculation: tableau = B^-1 * ( A I )_N = ( B^-1*A   B^-1*I )_N = ( ( B^-1*A )_N1   (B^-1)_N2 ). So, in order to get a row of the tableau, use CPXbinvarow and take the nonbasic variables out of it and use CPXbinvrow and take the nonbasic variables out of it.

I hope, I did not do any mistake.

@CPLEX-Team: If this is wrong, please correct me.

Best regards,
Thomas

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

Thomas,

 

I did a quick check in my model:

    * I created 25725 variables when building the model,

    * A call to CPXgetnumcols() returns 25725 columns.

For me this has some implications:

    * It seems that you are true in your arguments since CPXbinvarow() seems to return a vector of lenght equal to the number of columns in the problem (though it is not perfectly clear in the documentation).

    * But then, I have a problem: how can I retreive the reduced costs of the non basic slack variables since CPXgetdj() function only allows to pass as an argument a structural variable (a number lower than CPXgetnumcols()).

 

I hope that Ed will provide answers next monday!

 

Vincent

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: T_O

Aren't the dual values (CPXgetpi) what you call "the reduced costs of the slack variables"? Maybe, you have to take additional care about the sign.

Best regards,
Thomas

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: Vincent Tkindt

In any case, thank you Ed and Thomas for your valuable help.... You win a drink in case we meet a day!

 

Best

 

Vincent

#CPLEXOptimizers
#DecisionOptimization