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

$\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
    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$ Nov 26, 2012 at 18:16

1 Answer 1

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.

$\endgroup$

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.