# How to implement linear constraints that include several absolute values

Dear all,

I am trying to implement a linear constraint that includes several absolute values in the form: Abs(A) + Abs(B) + Abs(C) + Abs(D) + ... = 1

Since the minimization problem includes quite a lot of variables (~100) it is not feasible to implement a linear constraint for each potential +/- combination. Currently I am using ALGLIB with the MINBLEIC Function. Hence, I think it is also not possible to use additional 0/1 indicator variables (i) and to estimate sth. like (2*i-1)*A.

Every help is very much appreciated! Hugo

-
Do you have just one constraint of this form with the usual linear stuff for the rest? Voting to close already? What's your solution? – fedja Nov 26 '12 at 15:23
Is there any information on the objective function $f$? Otherwise, why should one hope to do better than trying all $2^n$ combinations? The behavior of $f$ on dfferent facets is independent, so the devil may have put the minimum he only knows where. (Of course, if e.g. $f$ is concave, its minimum is on one of the $n$ vertices) – Pietro Majer Nov 26 '12 at 18:16

Without having more information about the problem, I would suggest to generate the constraints of the +/- form on the fly. Several approaches are possible:

1. You can solve the problem, generate the violated constraints and resolve until the process converges.

2. You can construct a Branch-and-Cut algorithm.

3. If you have a sophisticated solver like Gurobi, you can add "Lazy Constraints" every time you find a feasible solution, cutting it of when it fails one of these Lazy Constraints.

The speed of such an approach, as Pietro Majer indicated, depends strongly on the problem structure.

-