The geometry of linear optimization problems

Before showing optimization models that exhibit bad behavior, we first need to understand the geometry behind them. Consider a problem of the form

<span>$</span>\begin{array}{ll}
\max & cx\
s.t. & Ax \leq b.\
\end{array}<span>$</span>
For example:
<span>$</span>\begin{array}{lrrl}
\max & x + y & \vec{c}=&(1,1)\
s.t. & -x \leq 0 & A_{1\cd...
... \leq 0 & A_{3\cdot}=&(0,-1)\
& y \leq 1 & A_{4\cdot}=&(0,1).\
\end{array}<span>$</span>
Note that if we denote <span>$</span>b^t:=(0,1,0,1)<span>$</span>, then the problem can be stated as
<span>$</span>\max_{x\in\mathbb{R}^2}\{ \vec{c}x:Ax\leq b\}.<span>$</span>
The feasible region, direction of improvement <span>$</span>\vec{c}<span>$</span>, and optimal solution <span>$</span>x^*<span>$</span> can be depicted as
\scalebox{1.0}{\includegraphics[width=4in]{refman_misc/codedraw3.pdf}}
Note that whenever we move in the direction of <span>$</span>\vec{c}<span>$</span>, the value <span>$</span>\vec{c}x<span>$</span> increases. Furthermore, since we can not move from <span>$</span>x^*<span>$</span> to another feasible point with better objective value, we can conclude that <span>$</span>x^*<span>$</span> is indeed the optimal solution for the problem. Note that <span>$</span>x^*<span>$</span> is a corner point of the feasible region. This is not a coincidence; you will always find an optimal solution at a corner point if the feasible region is bounded and <span>$</span>\vec{c}<span>$</span> is not zero. If the objective is zero then all feasible solutions are optimal; we will talk more about zero objectives and their implications later.

To understand how changes in the input data affect the feasible region and the optimal solution, consider a small modification: <span>$</span>\tilde{b}^t=(\varepsilon,1,0,1)<span>$</span>, <span>$</span>\tilde{\vec{c}}=(1+\varepsilon,1)<span>$</span>, and <span>$</span>\tilde{A_{4\cdot}}=(\varepsilon,1)<span>$</span>. Then our optimization problem would look like

\scalebox{1.0}{\includegraphics[width=4in]{refman_misc/codedraw4.pdf}}

Note that although we changed the right-hand side, this change had no effect in the optimal solution to the problem, but it did change the feasible region by enlarging the bottom part of the feasible area.

Changing the objective vector tilts the corresponding vector in the graphical representation. This of course also changes the optimal objective value. Perturbing a constraint tilts the graphical representation of the constraint. The change in <span>$</span>A_{4\cdot}<span>$</span> changes the primal solution itself. The amount of tilting constraint undergoes depends on the relative value of the perturbation. For example, although the constraint <span>$</span>x \leq 1<span>$</span> and the constraint <span>$</span>100 x \leq 100<span>$</span> induce the same feasible region, the perturbation <span>$</span>x + \varepsilon y\leq 1<span>$</span> will induce more tilting that the perturbation <span>$</span>100 x + \varepsilon y \leq 100<span>$</span>.

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