4
$\begingroup$

In solving a linear program (in specific a network optimization problem of the shortest path type) with the Excel solver, I noticed two things after running a sensitivity report on the solution suggested by the solver:

First, both the allowable increase as well as the allowable decrease were positive for all variables, which indicates that the solution suggested is a unique optimal solution.

Second, the final value as well as the reduced cost were both 0 for multiple variables, which usually indicates that these variables are part of another Corner Point Feasible solution at another optimal corner.

These two observations obviously contradict one another, which is quite confusing. The solution is definitely the only optimal solution for the problem.

Presented below are the optimization problem and the Sensitivity Report. The objective was to find the shortest path from SE to LN.

Sensitivity Report Problem Setting

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Welcome to OR.SE. Would you say please, have you tried using an LP or BIP formulation? $\endgroup$
    – A.Omidi
    Dec 10, 2021 at 18:56
  • $\begingroup$ Thank you for your answer. I used an LP formulation. $\endgroup$
    – AVAS
    Dec 10, 2021 at 22:56
  • 1
    $\begingroup$ Multiple solutions is about primal and dual solutions. There may be multiple solutions that have the same shortest path: the primal solution is unique but the dual solution is not. $\endgroup$
    – Erwin Kalvelagen
    Dec 11, 2021 at 12:41
  • $\begingroup$ Thanks a lot for your answer. I guess that makes sense. I tried to construct the dual problem and in fact there are multiple optimal solutions for the dual. Have a great day! $\endgroup$
    – AVAS
    Dec 11, 2021 at 13:43

1 Answer 1

Reset to default
2
$\begingroup$

Consider the following LP: \begin{align*} \max\,3x_{1}+5x_{2}\\ \textrm{s.t. }x_{1}+2x_{2} & +s_{1}=3\\ 2x_{1}+x_{2} & +s_{2}=3\\ x_{1}+x_{2} & +s_{3}=2\\ x,s & \ge0 \end{align*} ($s$ being slack variables). The feasible region has corners (0, 0), (0, 1.5), (1, 1) and (1.5, 0), with (1, 1) the unique optimum. If you choose the $(x_1, x_2, s_3)$ as your basis, I think you will find that variable $s_3$ has reduced cost 0 and optimal value 0. This is a result of the optimal solution being degenerate. So you might want to check whether your solution is also degenerate (more 0 values, including any slacks and surpluses, than the dimension of the solution space excluding slacks and surpluses).

Improve this answer
$\endgroup$
9
  • 1
    $\begingroup$ Solver reports s2 to have a reduced cost of 0, with s3 having a reduced cost of -1. CBC, via OpenSolver, reports s3 to have a reduced cost of 0. I believe the choice is arbitrary, as all three constraints pass through (1, 1) but only two constraints need to be binding at the optimal solution. $\endgroup$
    – Solver Max
    Dec 10, 2021 at 21:42
  • 1
    $\begingroup$ I agree that it's arbitrary. There are multiple optimal bases and which one you get is determined by pivoting decisions along the way, which I think might be affected by the order of the rows and columns in the constraint matrix, how the solver factors the matrix, and possibly random quantum occurrences in the computer's CPU. $\endgroup$
    – prubin ♦
    Dec 10, 2021 at 22:00
  • 1
    $\begingroup$ Degeneracy does not require the presence of slack variables. I just included them to make the example a bit easier to follow. $\endgroup$
    – prubin ♦
    Dec 12, 2021 at 1:36
  • 1
    $\begingroup$ How you know a solution is degenerate: number of binding constraints exceeds number of decision variables (not counting slacks and surpluses). If the primal solution is degenerate (whether it is unique or not), the dual has multiple optimal bases. Usually they correspond to different dual solutions, but if I recall correctly, it is possible that both the primal and dual have a single degenerate solution. $\endgroup$
    – prubin ♦
    Dec 12, 2021 at 16:35
  • 1
    $\begingroup$ Constraints having 0 right hand side is a non-issue. Let's say you have $n$ decision variables and $m$ slacks. In decision space ($\mathbb{R}^n$), every 0 value corresponds to a hyperplane intersecting at the solution. If the 0 value is for a decision variable $x_i$, the hyperplane is the $i$-th coordinate hyperplane (the $x_i$ axis in two or three dimensions). If the 0 value is for a slack variable $s_j$, the hyperplane is the $j$-th (inequality) constraint treated as an equality. The intersection of $n$ linearly independent hyperplanes is a vertex; more than $n$ means a degenerate vertex. $\endgroup$
    – prubin ♦
    Dec 12, 2021 at 19:43

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.