4
$\begingroup$

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

Improve this question
$\endgroup$
2
  • $\begingroup$ 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? $\endgroup$
    – fedja
    Commented Nov 26, 2012 at 15:23
  • 2
    $\begingroup$ 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) $\endgroup$
    – Pietro Majer
    Commented Nov 26, 2012 at 18:16

1 Answer 1

Reset to default
2
$\begingroup$

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.

Improve this answer
$\endgroup$

You must log in to answer this question.

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