Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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