Optimization problems occasionally yield unbounded solutions. To find the cause one can modify the model and solve it to gain information. This is done through the imposition of “artificially” large bounds. Linear programming solvers discover unboundedness when they find a variable which is attractive to make larger, but find that the variable may be increased without limit. In GAMS some solvers return such information but typically only one unbounded variable will be reported, if any and there may be numerous other variables which have not been examined and could be unbounded. Unfortunately, the LST file does not generally give enough information to diagnose and fix the cause of the unboundedness and pre-solves rarely find such problems. Commonly, the solution report contains an instance where a particular item is tagged as unbounded (with the marker UNBND), but there will also be other variables marked as non-optimal (NOPT) which may or may not be unbounded. Finally, note that use of GAMSCHK ANALYSIS and correction of all identified problems and models still can be bounded. Thus, most modelers will occasionally contend with models that are unbounded and will need to discover what is causing that condition.
What causes an Unbounded Model
Causes of unbounded models are not always easily identified. Solvers may report a particular variable as unbounded when in reality a different variable or interactions between variables is the real cause. Consider the following example:
Max 3X1 - X2 + X3
s.t. X1 - X2 = 0
X3 ≤ 20
X1 , X2 , X3 ≥ 0
Here the unboundedness is caused by the interrelationship between $X_{1}$ and $X_{2}$. There may be several potential explanations as to why the unboundedness is present. The profit contribution from $X_{1}$ and $X_{2}$ may not be volume independent and some form of diminishing revenue or increasing cost as sales increase may be omitted. Second, there may be omitted constraints on $X_{1}$ or $X_{2}$. Third, there may be multiple errors involving the above cases. A run with CPLEX resulted in the marking of $X_{2}$ as the unbounded item. This may or may not be a proper identification of the problem causing mistake. The mistake may be on the $X_{1}$ side and we don’t see anything about that in the output. There is a general point here usually unboundedness occurs because of the interaction of multiple variables and constraints, not just the one variable that the solver happens to mark. In a more complex model, potentially a set of 50 variables and constraints could be involved. Thus, we need to find the involved set of variables and equations and then look for the root cause of the unboundedness. How then does one go about discovering this? Again, model modifications may be necessary.
Finding Causes of Unboundedness – Basic Theory
The obvious solution to an unbounded model is to bound it. Thus, we bound variables we think are potentially unbounded so they are less than or equal to some very large number like 1010. The consequent model will be bounded, but the solution may have variable some quite large valued variables. In this case we will bound the $X_{1}$ and $X_{3}$ variables since both contribute revenue to the objective function.
Max 3X1 -X2 +X3
s.t. X1 -X2 = 0
X3 ≤ 20
X1 ≤ 1000000000
X3 ≤ 1000000000
X1 , X2 , X3 ≥ 0
Note we are making the problem “artificially” bounded. If it is truly unbounded, then we should expect that the solution will show $X_{1}$ and $X_{2}$ taking on large values which are far larger than any anticipated “non artificial” value. However, when unboundedness is not present the large upper bound constraints should be redundant with no effect on the solution although in solvers using dual simplex they can slow down convergence substantially. The resultant solution is
Objective : 20000000040.000000
LOWER LEVEL UPPER MARGINAL
---- EQU obj . . . 1.0000
---- EQU r1 -INF . . 1.0000
---- EQU r2 -INF 20.0000 20.0000 2.0000
LOWER LEVEL UPPER MARGINAL
---- VAR objmax -INF 2.000000E+10 +INF .
---- VAR x1 . 1.000000E+10 1.000000E+10 2.0000
---- VAR x2 . 1.000000E+10 +INF .
---- VAR x3 . 20.0000 1.000000E+10 .
This solution tells us what is wrong through the variable levels. The levels for both $X_{1}$ and $X_{2}$ are distorted while $X_{3}$ is unaffected. Thus, the modeler would receive signals that the unboundedness involves the interaction of the $X_{1}$ and $X_{2}$. In turn, one would examine these variables and any binding equations relating them to fix the unboundedness. The above material indicates a way of finding the cause of unboundedness. Namely, set up the model with large bounds present, solve it and look for distorted (large) levels to find the causal set of variables and equations. One word of caution, this will always identify some of the unboundedness causes, but in the face of a non-unique primal solution caused by degeneracy or alternative optimals may not reveal them all. Thus, multiple applications of the procedure may be needed.
Details on Large Bound Approach to Resolving Unboundedness
The following gives the steps for finding unboundedness causes.
Step 1 Identify the relevant variables for which artificially large bounds need to be added.
Step 2 Add bounds to those variables.
Step 3 Solve the model.
Step 4 Examine the model solution. When variable and equation solution levels are found which are excessively large, identify those as the variables and equations to be examined for the cause of infeasibility.
Step 5 Fix the model and repeat the process if needed.
There are several questions inherent in the above procedure. In particular, which items need bounds? What type of bounds should be entered? How does one find an excessively large level? Each is discussed below.
Where Do We Add Large Bounds?
The places where bounds are required can be determined in several ways. One could look at the model solution and just add bounds on the variables marked by the solver as unbounded or non-optimal. However, while this rather readily points to proper places in the example model, it does not always do such. One approach that can be used is to add bounds to all potentially unbounded variables. Linear programming models are unbounded when the solver finds the objective function can be improved by altering the value of a variable, but finds that variable is not limited by a constraint. Thus, to identify all potentially unbounded variables then one has to find all variables that contribute to the objective function, but are not directly bounded. Such cases in a maximization context involve
a) non-negative variables with positive objective coefficients and no upper bound b) non-positive variables with negative objective coefficients and no lower bound c) Unrestricted or free variables with positive objective coefficients and no upper bound d) unrestricted or free variables with negative objective coefficients and no lower bound
These cases identify a larger than necessary set since the restrictions imposed by the constraint set are not considered. However, more complex tests would be needed to factor in those constraints. The ADVISORY and NONOPT procedures in GAMSCHK have been written to create a list of all occurrences of these cases. Use of ADVISORY does not require the model be solved or while NONOPT in IDENTIFY mode only work after a model solve.
GAMS permits an alternative technique for bounding the problem. Namely, one can go provide a large upper bound on the variable to be maximized or if the problem is a minimization problem, a large negative lower bound.
How Do I Find Distorted Levels?
The next question involves finding the distorted levels. The simple aspect of this is that one can simple review the output find variable levels with large exponents. The more complex aspect is that in a model with thousands of variables and equations this information can be well hidden. The GAMSCHK NONOPT procedure has been written to help in this quest. All items with levels in an optimal solution that are larger in absolute value than 10 to a filter value, are output as potential causes of the unboundedness.
Comparing the Bounding Techniques
As mentioned above there are two bounding approaches that can be used
- bound multiple individual variables which contribute to the desirability of the objective function ( for example, those that are profitable in a maximization problem)
- bound the single variable which is being optimized in the problem.
There can be substantial differences in information generated by these two techniques. The most distinguishing characteristics involve simplicity of use and completeness of information.
- Simplicity of use - When one simply bounds the variable being optimized one adds a single bound without having to think through which variables are desirable to the objective function and then add multiple bound statements on those.
- Completeness of information Simplicity has its costs, as information content in the solution is generally less under the simpler bound technique. Namely, when a unbounded model is solved and there is more than one set of variables causing the unboundedness, the use of the single bound will only reveal one unbounded case at a time.
NLPs, MIPs and Unboundedness
When dealing with unbounded cases in mixed integer programs or nonlinear programs the approach is essentially that above. However, in the nonlinear programming case one also has to consider has two additional issues: objective function form and solver numerical properties.
- In terms of objective function form, nonlinear programming theory requires a concave objective function for the attainment of global optimality in maximization problems and a convex objective function in the case of minimization problems. When a nonlinear programming model is judged unbounded, then one should investigate the objective function convexity/concavity characteristics.
- When a nonlinear programming model is unbounded, one can be running into numerical problems. In particular, issues such scaling, starting points, tolerances and other numerical issues can be the problem. The bounding technique above has been shown in the authors work. To be useful but on occasions has been subject to numerical problems which needed to be resolved before proceeding.
from Bruce McCarl’s GAMS Newsletter No 45 , July 2020