Multiple optimal solutions

A common misconception among beginners in optimization is the idea that optimization problems really have just one solution. Surprisingly, this is typically not true. For many practical problems, the objective (whether it is cost or revenue or ...) is dominated by a handful of variables, while most variables are just there to ensure that the actual operation of the solution is possible. Consider a staffing problem, for example, where cost is typically driven by the number of people who work on a given day, not by the specific people.

These kind of situations naturally lead to problems similar to

\begin{displaymath}\begin{array}{lrrl}
\max & y & \vec{c}=&(0,1)\
s.t. & -x \l...
...dot}=&(0,-1)\
& y \leq 1 & A_{4\cdot}=&(0,1).\
\end{array}\end{displaymath}

Graphically this can be depicted as
Image codedraw5
In this situation is clear that <span>$</span>x^1<span>$</span>, <span>$</span>x^3<span>$</span>, and all solutions lying on the line between these two points are optimal. The simplex algorithm will return either <span>$</span>x^1<span>$</span> or <span>$</span>x^3<span>$</span> (and may switch if you change parameters). The barrier algorithm (without crossover) will return <span>$</span>x^2<span>$</span>. These solutions are all correct; the problem as stated has no reason to prefer one over the other. If you do have a preference, you'll need to state it in your objective function.

Try Gurobi for Free

Choose the evaluation license that fits you best, and start working with our Expert Team for technical guidance and support.

Evaluation License
Get a free, full-featured license of the Gurobi Optimizer to experience the performance, support, benchmarking and tuning services we provide as part of our product offering.
Academic License
Gurobi supports the teaching and use of optimization within academic institutions. We offer free, full-featured copies of Gurobi for use in class, and for research.
Cloud Trial

Request free trial hours, so you can see how quickly and easily a model can be solved on the cloud.

Search