Topic
IC4NOTICE: developerWorks Community will be offline May 29-30, 2015 while we upgrade to the latest version of IBM Connections. For more information, read our upgrade FAQ.
7 replies Latest Post - ‏2012-11-19T20:46:24Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts
ACCEPTED ANSWER

Pinned topic upper and lower bounds of slack variables in CPLEX

‏2011-02-13T23:16:34Z |
Dear Forum,

what are the upper and lower bounds of slack variables in CPLEX?

If I add a constraint of the form "c^t x <= b" to a linear program, CPLEX seems to add a slack variable with lower bound 0 and without upper bound.
If I add a constraint of the form "c^t x >= b" to a linear program, does CPLEX add a slack variable with upper bound 0 and without lower bound?
The behavior of CPLEX does not seem to be consistent in this case. On the one hand slack variables of this type can have negative values. On the other hand if the value of the slack variable is 0, the slack variable has the status "at_lower_bound", as can be seen in the following example, where I added three constraints of type ">=".

>>> prob.solution.get_linear_slacks()
[0.0, 0.0, -3.2857142857142856]
>>> prob.solution.basis.get_basis()
([1, 1], [0, 0, 1])
>>> prob.solution.basis.status.at_lower_bound
0
>>> prob.solution.basis.status.basic
1


If I add a constraint of the form "c^t x == b" to a linear program, CPLEX also adds a slack variable. Are its upper and lower bounds 0?

What about ranged constraints of the form "a <= c^t x <= b" what are the upper and lower bounds of its slack variable?

Thank you,
Philipp
Updated on 2014-03-24T22:45:54Z at 2014-03-24T22:45:54Z by iron-man
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: upper and lower bounds of slack variables in CPLEX

    ‏2011-02-21T09:04:35Z  in response to SystemAdmin
    Yes, slack variables and their basis status is a bit inconsistent in CPLEX. See the reference manual for CPXgetslack to understand the definition of the slack variables:

    The routine CPXgetslack accesses the slack values for a range of linear constraints. The beginning and end of the range must be specified. Except for ranged rows, the slack values returned consist of the righthand side minus the row activity level. For ranged rows, the value returned is the row activity level minus the righthand side, or, equivalently, the value of the internal structural variable that CPLEX creates to represent ranged rows.
    


    So, we have:
    ax <= b         <=>   ax + s == b, s >= 0
    ax >= b         <=>   ax + s == b, s <= 0
    b <= ax <= b+r  <=>   ax + s == b, 0 <= s <= r
    

    I would always define ranged rows in this way, i.e., with positive r. You can also use a negative r, but (at least in some older versions) there is/was a bug with presolve for negative range values.
    Updated on 2014-03-25T00:17:32Z at 2014-03-25T00:17:32Z by iron-man
    • SystemAdmin
      SystemAdmin
      7929 Posts
      ACCEPTED ANSWER

      Re: upper and lower bounds of slack variables in CPLEX

      ‏2011-02-21T09:13:11Z  in response to SystemAdmin
      Regarding the definition of the basis, you can read the reference manual entry for CPXgetbase:
      The routine CPXgetbase accesses the basis resident in a CPLEX problem object.
      Either of the arguments cstat or rstat may be NULL if only one set of status values is needed.
      
      Updated on 2014-03-25T00:17:28Z at 2014-03-25T00:17:28Z by iron-man
      • SystemAdmin
        SystemAdmin
        7929 Posts
        ACCEPTED ANSWER

        Re: upper and lower bounds of slack variables in CPLEX

        ‏2011-02-21T09:14:52Z  in response to SystemAdmin
        Table 1: Values of elements of cstat
        CPX_AT_LOWER    0  variable at lower bound
        CPX_BASIC       1  variable is basic
        CPX_AT_UPPER    2  variable at upper bound
        
        Updated on 2014-03-25T00:17:24Z at 2014-03-25T00:17:24Z by iron-man
        • SystemAdmin
          SystemAdmin
          7929 Posts
          ACCEPTED ANSWER

          Re: upper and lower bounds of slack variables in CPLEX

          ‏2011-02-21T09:15:46Z  in response to SystemAdmin
          Yes, slack variables and their basis status is a bit inconsistent in CPLEX. See the reference manual for CPXgetslack to understand the definition of the slack variables:

          The routine CPXgetslack accesses the slack values for a range of linear constraints. The beginning and end of the range must be specified. Except for ranged rows, the slack values returned consist of the righthand side minus the row activity level. For ranged rows, the value returned is the row activity level minus the righthand side, or, equivalently, the value of the internal structural variable that CPLEX creates to represent ranged rows.
          


          So, we have:
          ax <= b         <=>   ax + s == b, s >= 0
          ax >= b         <=>   ax + s == b, s <= 0
          b <= ax <= b+r  <=>   ax + s == b, 0 <= s <= r
          

          I would always define ranged rows in this way, i.e., with positive r. You can also use a negative r, but (at least in some older versions) there is/was a bug with presolve for negative range values.

          Regarding the definition of the basis, you can read the reference manual entry for CPXgetbase:
          The routine CPXgetbase accesses the basis resident in a CPLEX problem object. Either of the arguments cstat or rstat may be NULL if only one set of status values is needed.
           
          Table 1: Values of elements of cstat
          CPX_AT_LOWER    0       variable at lower bound
          CPX_BASIC       1       variable is basic
          CPX_AT_UPPER    2       variable at upper bound
                          3       variable free and nonbasic
           
          Table 2: Values of elements of rstat in rows other than ranged rows
          CPX_AT_LOWER    0       associated slack, surplus, or artificial variable is nonbasic at value 0.0 (zero)
          CPX_BASIC       1       associated slack, surplus, or artificial variable is basic
           
          Table 3: Values of elements of rstat for ranged rows
          CPX_AT_LOWER    0       associated slack, surplus, or artificial variable is nonbasic at its lower bound
          CPX_BASIC       1       associated slack, surplus, or artificial variable is basic
          CPX_AT_UPPER    2       associated slack, surplus, or artificial variable is nonbasic at upper bound
          


          The interesting part here are the rstat values. As you can see, regular (non-ranged) rows can only have the CPX_AT_LOWER and CPX_BASIC status. Thus, even for ax >= b, the slack variable will have status CPX_AT_LOWER if the constraint is tight (although the slack variable is actually at its upper bound according to the definition stated in CPXgetslack).
          For ranged rows, the basis status is clear, at least if you use a positive range value.
          Tobias
          Updated on 2014-03-25T01:05:19Z at 2014-03-25T01:05:19Z by iron-man
          • SystemAdmin
            SystemAdmin
            7929 Posts
            ACCEPTED ANSWER

            Re: upper and lower bounds of slack variables in CPLEX

            ‏2011-02-21T09:18:35Z  in response to SystemAdmin
            Okay. Sorry for the mess. For some odd reason the forum does not like me to use the term "s u p e r", which is needed for the third cstat status.
    • SystemAdmin
      SystemAdmin
      7929 Posts
      ACCEPTED ANSWER

      Re: upper and lower bounds of slack variables in CPLEX

      ‏2012-11-19T20:46:24Z  in response to SystemAdmin
      Please note that my original comment about the definition of slacks for ">=" rows is wrong.
      The correct definition used in CPLEX is:
      ax <= b         <=>   ax + s == b, s >= 0
      ax >= b         <=>   ax - s == b, s >= 0
      b <= ax <= b+r  <=>   ax + s == b, 0 <= s <= r
      
      Updated on 2014-03-24T22:45:58Z at 2014-03-24T22:45:58Z by iron-man
  • SystemAdmin
    SystemAdmin
    7929 Posts
    ACCEPTED ANSWER

    Re: upper and lower bounds of slack variables in CPLEX

    ‏2011-02-21T09:12:41Z  in response to SystemAdmin
    Sorry... the forum always complains about "Disallowed content" in my posting. I split it into pieces in order to identify what the reason for this is...