2

Original Optimization:

Let say I want to minimize below function:

minimize

$\left|a_1x_1+a_2x_2-c_1\right| + \left|b_1x_1+b_2x_2-c_2\right|$

subject to:

$x_1^{lower} \le x_1 \le x_1^{upper}$

<p><span class="math-container">$x_2^{lower} \le x_2 \le x_2^{upper}$</span></p>

Solutions online: I have seen that the proposed solutions are mainly to introduce an auxiliary variables $t_1$ and $t_2$, and try to minimize $(t_1 + t_2)$ subject to some constraints around $t_1$ and $t_2$ values. (e.g. this post).


Can below Linear Programming reformulation work?

But here is another possibility with seems simpler and effective. I am not sure what am I missing and why nobody has suggested this:

maximize

$a_1x_1+a_2x_2 + b_1x_1+b_2x_2$

subject to:

$a_1x_1+a_2x_2 \le c_1$

<p><span class="math-container">$b_1x_1+b_2x_2 \le c_2$</span></p>

<p><span class="math-container">$x_1^{lower} \le x_1 \le x_1^{upper}$</span></p>

<p><span class="math-container">$x_2^{lower} \le x_2 \le x_2^{upper}$</span></p>


user1780424
  • 133

1 Answers1

1

No, it doesn't. Let's consider an extreme case where $$\min |x_1 +x_2 - 1|+ |x_1 +x_2 - 1|$$

$$1 \le x_1 \le 1$$

$$1 \le x_2 \le 1$$

which is feasible.

Your method would construct the following feasible set.

$$x_1 + x_2 \le 1$$ $$x_1 + x_2 \le 1$$ $$1 \le x_1 \le 1$$

$$1 \le x_2 \le 1$$

which is not feasible.

Siong Thye Goh
  • 149,520
  • 20
  • 88
  • 149
  • Interesting example. So it the $t_1$ and $t_2$ solution which I linked to from another post the only possibility ? – user1780424 Nov 09 '18 at 05:28
  • To claim that something is the only way to do something is a very bold statement. I welcome new ideas unless it's proven that that's the only way. – Siong Thye Goh Nov 09 '18 at 05:36