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.

Improve this question
$\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
    Commented Feb 12, 2014 at 12:12

1 Answer 1

Reset to default
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''.

Improve this answer
$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .