0
$\begingroup$

I have the following optimisation problem:

$\max |a_0 + a_1x_1 + \dots + a_nx_n |$

subject to bound constraints

$\mathbf{b}_l \leq \mathbf{x} \leq \mathbf{b}_u.$

According to this previous post and this link, this problem converts to a mixed-integer program.

However, I am rather convinced that I can simply replace this problem with the best solution from the following two separate linear programs:

$\max a_0 + a_1x_1 + \dots + a_nx_n$

subject to

$\mathbf{b}_l \leq \mathbf{x} \leq \mathbf{b}_u$

and

$\min a_0 + a_1x_1 + \dots + a_nx_n$

subject to

$\mathbf{b}_l \leq \mathbf{x} \leq \mathbf{b}_u$.

Comparing the two results and choosing the one with greatest absolute value should surely give me the answer to the first optimisation problem, without having to resort to formulating the original problem as a mixed-integer linear program.

If I am wrong, could someone please explain why?

$\endgroup$
1
$\begingroup$

Yes, you can solve this special case of maximizing $|z|$ by separately maximizing and minimizing $z$ and taking the larger resulting value of $|z|$, without introducing any additional variables or constraints. This approach even applies if $z$ is nonlinear and/or if you have more general constraints.

$\endgroup$
  • $\begingroup$ Thank you Rob. This is exactly what I thought. I was just a little confused as to why someone would want to formulate the problem as a mixed-integer program, when solving it as two separate linear programs would be much more efficient. $\endgroup$ – JGross Nov 25 at 10:14
  • $\begingroup$ The mixed integer formulations are really to cover more general cases in which only part of the objective function contains an absolute value. $\endgroup$ – Rob Pratt Nov 25 at 13:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.