1
$\begingroup$

This has be asked on other forums, though couldn't find authoritative answer.

I have a linear program over the reals and don't want to introduce integer or binary variables.

The objective function is $\text{maximize} \sum |x_i|$ (maximizing sum of absolute values of variables).

Is is possible to model this as a standard linear program (without integer variables and extensions like disjunctions).

What I know. Minimizing sum of absolute values is possible.

This blog suggests several solutions. The solution with SOS2 method appears to work sometimes in glpk and coin-or, though sometimes it doesn't work.

The lpsolve documentation suggests using a binary variable.

If this is impossible, there might be reduction from a NP-hard problem.

$\endgroup$
1
  • $\begingroup$ What do the constraints look like? If you have a typical polyhedral feasible region, then maximizing the sum of absolute values is in general nonconvex, hence not a linear program (which are convex). $\endgroup$
    – martin
    Feb 12, 2014 at 12:12

1 Answer 1

4
$\begingroup$

In general such a problem is NP-hard, so not expressible by a polynomially-sized linear program. A special case of the problem you mention is computing the $\lVert A\rVert_{\infty,1}$ norm of a matrix, i.e. the maximum of $\lVert Ax\rVert_1$ over all $x$ with $\lVert x\rVert_\infty\leq 1$. Rohn has shown that this matrix norm is NP-hard to approximate in the paper ``Computing the norm $\Vert A\rVert_{\infty,1}$ is NP-hard''.

$\endgroup$
0

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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