0

In linear optimization, I often see linear inequalities that define the solution space being added up. Obviously if $1 < 4$ and $9 < 10$ then also $1 + 9 < 4 + 10$, so adding up both inequalities does not seem to do much harm (if you're adding up inequalities of the same sign). However if you have an optimization problem:

$\max x_2 \\ s.t.: x_1 \leq 1 \\ \ \ \ \ \ \ \ \ \ x_2 \leq 1\\ \ \ \ \ \ \ \ \ \ x_1, x_2 \geq 0 \ \text{and integer}$

then an optimum solution to this problem is obviously $(x_1,x_2) = (0,1)$.

But if you add both inequality constraints and obtain the following linear program:

$\max x_2 \\ s.t.: x_1 + x_2 \leq 2 \\ \ \ \ \ \ \ \ \ \ x_1, x_2 \geq 0 \ \text{and integer}$

The optimal solution clearly changes to $(x_1, x_2) = (0, 2)$. All we did was adding two linear inequalities (which is often done in linear programming, no?) but the solution space, the optimum objective value and the optimum solution clearly changed...

When are we allowed to add inequalities in linear programming without changing

WBM
  • 185
  • $x_1\leq 1,,x_2\leq 1 \implies x_1+x_2\leq 2 $ but it doesn't always hold in the other direction, so your problem is "bigger" now that you added those inequalities – Jakobian Jun 13 '18 at 18:39

2 Answers2

1

Comparing the feasible region in light blue $x_1+x_2 \le 2, x_1 > 0, x_2 > 0$ and containing the smaller square associated to $0 \le x_1 \le 1, 0\le x_2 \le 1$

enter image description here

Cesareo
  • 33,252
0

The two inequalities $$ H_1: x_1 \le 1 \iff (1, 0) \cdot (x_1, x_2) \le 1 \\ H_2: x_2 \le 1 \iff (0, 1) \cdot (x_1, x_2) \le 1 $$ define two affine half spaces (here bounded by lines with given unit normal vectors and distance from the origin) and the solutions are in the intersection $H_1 \cap H_2$.

Together with the other constraints the feasible solutions are in $[0,1]^2\cap \mathbb{Z}^2$.

The inequality $$ H_3: x_1 + x_2 \le 2 \iff (1, 1) / \sqrt{2} \cdot (x_1, x_2) \le \sqrt{2} $$ defines just one affine half space.

The operation of adding the inequalities does not preserve the solution set.

Here is the scene:

enter image description here (Large version)

mvw
  • 34,562
  • But if adding inequalities does not preserve the solution space, how can one aggregate constraints like they did in the UFL problem on page 27 in the following paper: https://www.springer.com/cda/content/document/cda_downloaddocument/9781441975713-c2.pdf?SGWID=0-0-45-1059737-p174034979

    Here they sum over the constraints 2.3 to obtain one aggregated inequality constraint

     – WBM Jun 13 '18 at 19:53
  • Aggregating constraints creates a relaxation of the original problem (as shown in mvw’s figure above). You can’t in general claim to get the same solution, but you can get a bound. – David M. Jun 13 '18 at 22:28