Topic
  • 7 replies
  • Latest Post - ‏2012-11-19T20:46:24Z by SystemAdmin
SystemAdmin
SystemAdmin
7929 Posts

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

    Re: upper and lower bounds of slack variables in CPLEX

    ‏2011-02-21T09:04:35Z  
    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

    Re: upper and lower bounds of slack variables in CPLEX

    ‏2011-02-21T09:12:41Z  
    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...
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: upper and lower bounds of slack variables in CPLEX

    ‏2011-02-21T09:13:11Z  
    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:

    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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. </pre>

    So, we have:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">ax <= b <=> ax + s == b, s >= 0 ax >= b <=> ax + s == b, s <= 0 b <= ax <= b+r <=> ax + s == b, 0 <= s <= r </pre>
    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.
    
    Updated on 2014-03-25T00:17:28Z at 2014-03-25T00:17:28Z by iron-man
  • SystemAdmin
    SystemAdmin
    7929 Posts

    Re: upper and lower bounds of slack variables in CPLEX

    ‏2011-02-21T09:14:52Z  
    Regarding the definition of the basis, you can read the reference manual entry for CPXgetbase:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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. </pre>
    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

    Re: upper and lower bounds of slack variables in CPLEX

    ‏2011-02-21T09:15:46Z  
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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 </pre>
    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

    Re: upper and lower bounds of slack variables in CPLEX

    ‏2011-02-21T09:18:35Z  
    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:

    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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. </pre>

    So, we have:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">ax <= b <=> ax + s == b, s >= 0 ax >= b <=> ax + s == b, s <= 0 b <= ax <= b+r <=> ax + s == b, 0 <= s <= r </pre>
    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:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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 </pre>

    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
    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

    Re: upper and lower bounds of slack variables in CPLEX

    ‏2012-11-19T20:46:24Z  
    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:

    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">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. </pre>

    So, we have:
    <pre class="java dw" data-editor-lang="java" data-pbcklang="java" dir="ltr">ax <= b <=> ax + s == b, s >= 0 ax >= b <=> ax + s == b, s <= 0 b <= ax <= b+r <=> ax + s == b, 0 <= s <= r </pre>
    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.
    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