Where note the marginals on r2, r3 and x2 are large.
The question then is: So what? When a linear program is solved, the optimum solution contains items which are influenced by the objective function parameters for the non-zero variables. In particular the GAMS marginals or more classically, the shadow prices, reduced costs and objective function value.
So in this case with the artificial is in the basis, then relaxation of some of the right hand sides will cause that artificial to become smaller and they will have artificially large shadow prices. Similarly the reduced costs on some variables will be influenced by the presence of the artificial indicating that the artificial would get smaller if that variable could go below its lower bound (going negative in this case) or above its upper. Note this is the case for the marginals on r2, r3 and x2 which jointly indicates equations r1, and r2 plus x2>0 is the infeasibility causing set.
General procedure for finding the infeasibility causing set
The following gives the steps for finding infeasibility causes using the Big M, artificial variable approach.
Step 1 Identify the relevant equations and/or variable bounds for which artificials are needed to be added (details about this in next section)
Step 2 Add artificial variables to those equations and bounds. These artificials each have a Big M penalty in the objective function and an entry in a single constraint.
Step 3 Solve the model
Step 4 Examine the model solution. Where the marginals (the reduced costs for the variables and the shadow prices for the equations) are distorted by the presence of the artificials, identify those as the variables and equations to be examined for the cause of infeasibility (note once identified then the modeler needs to examine those in the context of the problem hopefully finding the issue).
Step 5 Fix the model and repeat the process if needed
There are several questions inherent in the above procedure. In particular: Where should artificial variables be added? How should the artificial variables be structured? and How does one find a “distorted” marginal? Each is discussed below.
Where Should one add Artificial Variables?
The places where artificial variables should be added can be determined in several ways. One could look at the model solution and enter artificials in the equations and/or variable bounds marked by the solver as infeasible. However, while this sometimes points to proper places, it does not always do such. The approach advocated here is to add artificials in all possible infeasible locations although a different approach is in order for newly modified models as discussed below.
Programming models will only be infeasible when setting all the decision variables equal to zero is not feasible. This occurs when: a) the interval between variable upper and lower bounds does not include zero; or b) equations appear which are not satisfied when all variables are set to zero.
The equation cases which are not satisfied when the variables are set equal to zero are:
- Less than or equal to constraints with a negative right side i.e. x ≤ -1
- Greater than or equal to constraints with a positive right side. i.e. x ≥1
- Equality constraints with a nonzero right side i.e. x = 1 or x = -1
Additionally, when the interval between a variable’s lower and upper bounds does not include zero then those bounds need to be converted to constraints with artificials. This will occur when:
- The lower bound is positive, or
- The upper bound is negative
The ADVISORY and NONOPT -- IDENTIFY procedures in GAMSCHK have been written to create a list of all occurrences of these five cases.
Adding artificials in newly modified models
When a model that was feasible before has been newly modified and goes infeasible this raises a different artificial adding procedure. Namely, one can just add the artificials into the newly added constraints and/or bounds. Therein one may need to add artificials to newly added constraints or bounds that in fact are satisfied when all the variables are set to zero. This arises because the new constraints are possible members of the infeasibility causing set through their interaction with other constraints that previously could be satisfied. Here artificials would be added to the new =L= constraints with positive right hand sides or new =G= constraints with a negative right hand side. The exact structure these artificials follows the rules given in the next section.
Entering Artificial Variables in GAMS
Once one has found where to add the artificial variables one still has to address: How they should be added? and What should they look like? I recommend using the following general rules address this question.
- In general a new GAMS variable that is specified to be positive should be defined for each identified potential infeasibility causing equation. This variable should have the same dimension as does the equation. Thus, if artificials are added to RESOUREQ(PLANT,RESOURCE), then the artificial should look like ARTRESOURQ(PLANT,RESOURCE).
- Artificials should be entered on the left-hand side of the equation with a coefficient of +1 in =L= equations and -1 in =G= equations. When the equation is an =E= the artificial should be a +1 if the equation right hand side is positive and -1 if it is negative.
Note, one cannot add an artificial into variable bounds which are defined using LO, .UP or .FX syntax. One needs to convert these to =G=, to =L= and =E= equations and then add the artificials following the above rules on signs.
One will also need to enter a large objective function penalty for the artificials. The coefficient will be negative when the objective function is maximized and when it is minimized. The magnitude of this penalty is entirely problem dependent and can cause numerical problems in the solver. All that can be said in general is that the penalty should dwarf the other objective function coefficients and should be large enough so that the artificial is driven to zero in any feasible model.
Alternatively, if numerical problems are plaguing the solution with the artificials entered, one can modify the objective function to one which minimizes some of the artificials. In the above example the simplest way to do this is to multiply the original objective function by zero and convert the penalty on the artificial to something like hundred so that the shadow prices are not extremely small. This means the model becomes