4

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

SecretAgentMan
  • 1,895
  • 2
  • 13
  • 39
AVAS
  • 43
  • 9
  • 1
    Welcome to OR.SE. Would you say please, have you tried using an LP or BIP formulation? – A.Omidi Dec 10 '21 at 18:56
  • Thank you for your answer. I used an LP formulation. – AVAS Dec 10 '21 at 22:56
  • 1
    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. – Erwin Kalvelagen Dec 11 '21 at 12:41
  • 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! – AVAS Dec 11 '21 at 13:43

1 Answers1

2

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

prubin
  • 39,078
  • 3
  • 37
  • 104
  • 1
    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. – Solver Max Dec 10 '21 at 21:42
  • 1
    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. – prubin Dec 10 '21 at 22:00
  • Thank you for your answer. I am pretty sure that the solution is not degenerate as I did not introduce any slack variables. Could it be possible that as Network Optimization Problems differ form general LPs, the sensitivity report cannot be interpreted in the same way and a final value as well as a reduced cost of 0 do not indicate multiple optimal solutions in this special case? – AVAS Dec 11 '21 at 12:41
  • 1
    Degeneracy does not require the presence of slack variables. I just included them to make the example a bit easier to follow. – prubin Dec 12 '21 at 01:36
  • Thank you! Just a follow up question: Is it true that if the primal optimal solution is unique and degenerate, then the dual has multiple optimal solutions? And how do I know for sure that my solution is degenerate? – AVAS Dec 12 '21 at 09:00
  • 1
    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. – prubin Dec 12 '21 at 16:35
  • Alright, thank you. So my problem has 8 binding constraints (6 of wich are =0 constraints) and 13 decision variables (10 of which are 0 in the optimal solution). So if I want to prove degeneracy can I argue that it occurs because many of my constraints are equal to 0 (e.g. the solution may stay the same after a pivot) or because most of my decision variables are equal to 0 in the optimal solution. I really appreciate your help, I just want to be 100% sure that I fully understand why my solution is degenerate. – AVAS Dec 12 '21 at 17:44
  • 1
    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. – prubin Dec 12 '21 at 19:43
  • Great, thank you! – AVAS Dec 13 '21 at 14:06