An Example
Let's consider a simple LP with multiple optimal solutions:\begin{eqnarray*}\textrm{maximize } x\\ x & \le & 1\\ x + y & \le & 3 \\ x, y & \ge & 0.\end{eqnarray*} The feasible region and two optima (blue dots) are depicted in the following graph:
Ordinarily, the hyperplane (isoquant) corresponding to the objective function at its optimal value (the set of all points where the optimal objective value is reached) is tangent to the feasible region of an LP at a single point. Tilt it a little and it is still tangent at the same point. When multiple optima occur, the isoquant is tangent along a face of dimension greater than zero, as in this picture (where it is tangent along the vertical segment between the blue dots). Now think about what would happen in the illustration if we perturbed the slope of the objective function slightly. If we tilted it at all upward (say, maximize $x + \epsilon y$ for small positive $\epsilon$), $(1,2)$ would be the unique winner ($1 + 2\epsilon \gt 1$).
If we tilted it at all downward (say, maximize $x - \epsilon y$), $(1,0)$ would be the unique winner ($1 \gt 1-2\epsilon$).
So the tipoff that you may have multiple optima is that there is some objective coefficient which, if perturbed at all in the wrong direction, causes the current optimal solution to cease to be optimal.
Sensitivity Output for the Objective Function
I coded this model in CPLEX, entering the constraint $x\le 1$ as an upper bound on $x$ rather than as a functional constraint (but the end result would be the same either way). The Java API for CPLEX contains a method, IloCplex.getObjSA(), that takes as arguments two double precision vectors and a vector of variables, and returns the lower and upper limits for the constraint coefficients in the first and second vectors respectively. As long as any one objective coefficient changes but stays between its upper and lower limits, and the others stay constant, the current optimal solution is known to remain optimal. Here's the results of a call to getObjSA (along with the current objective coefficients):
| Objective Coefficient | |||
|---|---|---|---|
| Variable | Low | Current | High |
| $x$ | 0 | 1 | $+\infty$ |
| $y$ | $-\infty$ | 0 | 0 |
CPLEX does not literally return values of $\pm \infty$; I'm interpreting anything with magnitude $10^{20}$ or larger as $\infty$. Note that the upper limit of the objective coefficient for $y$ matches its current value ($0$). Any increase in that coefficient, however small, jumps to a new solution. That is the signal of a possible alternate optimum.
"Possible" Alternate Optimum?
There's one small catch with this. Having an objective coefficient at its upper or lower limit is a necessary condition for an alternate optimum to exist, but not quite a sufficient one. Suppose we change our objective to maximizing $x+2y$ and add one more constraint to our example: $x+2y \le 0$. The feasible region collapses down to just the origin (which must therefore be the optimal solution), and the origin is a degenerate corner (more than the requisite number of constraints, two in this case since we are operating in $\mathbb{R}^2$, are binding).
| Objective Coefficient | |||
|---|---|---|---|
| Variable | Low | Current | High |
| $x$ | 1 | 1 | $+\infty$ |
| $y$ | $-\infty$ | 2 | 2 |
This time we have two signals of a possible alternate optimum: the objective coefficient of $x$ is at its lower limit, and the objective coefficient of $y$ is at its upper limit. From the graph, though, it is clear that no other optimum can exist (since no other feasible point exists).
As with the objective function, we can get sensitivity information for the right-hand sides of constraints (IloCplex.getRHSSA()) and variable bounds (IloCplex.getBoundSA()). If any one right-hand side or bound changes but stays within the indicated range, with all other right-hand sides/bounds remaining constant, the current basis remains a valid basis (although the values of the variables will change). Violate a range and the basis may change. Degeneracy is signaled by a right-hand side or bound that has no room to move in one particular direction.
For our modified example, the sensitivity tables are as follows:
| Lower Bound | Upper Bound | |||||
|---|---|---|---|---|---|---|
| Variable | Low | Current | High | Low | Current | High |
| $x$ | $-\infty$ | 0 | 0 | 0 | 1 | $+\infty$ |
| $y$ | -0.5 | 0 | 0 | 0 | $+\infty$ | $+\infty$ |
| Constraint | Low | Current | High |
|---|---|---|---|
| $x+y\le 3$ | 0 | 3 | $+\infty$ |
| $x+2y\le 0$ | 0 | 0 | 1 |
We have three signals of degeneracy.
The Bottom Line
The first thing to look at, when trying to detect alternate optima, is the objective ranging table. A coefficient at one of its limits is a necessary condition. The next step is a bit less obvious. You can check bound and constraint sensitivity. If there are no signals of degeneracy, the necessary condition becomes sufficient: you have other optima. If degeneracy is present, however, that does not rule out alternate optima; it just means the objective ranging condition is not sufficient to be sure.
One way to resolve the uncertainty (and also find another optimum, if one exists) is to select one of the objective coefficients which is at a limit, and nudge it just a little past that limit. Then solve the modified LP, verify that the new solution is not the old solution (i.e., that you nudged the coefficient enough to jump to a new vertex of the feasible region). Finally, evaluate the new solution using the original coefficient and verify that the objective value matches the original optimal value (i.e., that you did not nudge the objective coefficient too far).
No comments:
Post a Comment
Due to intermittent spamming, comments are being moderated. If this is your first time commenting on the blog, please read the Ground Rules for Comments. In particular, if you want to ask an operations research-related question not relevant to this post, consider asking it on Operations Research Stack Exchange.