0

I'm trying to use a cutting plane algorithm to minimize a convex objective and constraint.

The constraint is an equality constraint, however, and the algorithm only specifies how to work with inequality constraints.

Imagine the constraint to be :

$$ - x_1 + \frac{x_2}{x_3} = 0 $$

Is it valid if I change this to two constraints: $$ - x_1 + \frac{x_2}{x_3} \leq 0\\ x_1 - \frac{x_2}{x_3} \leq 0 $$

Frank
  • 880
  • 1
    Yes, that’s exactly what you need to do. The general so called “standard form” of linear programs require all the constraints to be inequalities and this is the conventional trick to deal with equality constraints in general – curlycharcoal Apr 12 '20 at 06:20
  • Thank you for responding. I am having issues with convergence, do you think it would be wise to add a tolerance of say, $.0001$, so that the constraints would become $x_1 - \frac{x_2}{x_3} \leq .0001$? Also, do you think it makes a difference (to the stability of some solvers) if I Instead set the constraints are $x_1*x_3 - x_2 \leq 0$ ? – Frank Apr 14 '20 at 02:54
  • You can try reformatting the inequality, but I would be surprised if the solver doesn't already have a pre-processing step to standardize anyway.

    In terms of convergence, I can't really comment without seeing the whole problem. Since you're using cutting planes, are you solving a mixed integer linear program with LP relaxation? As a first attempt, try using branch-and-cut instead of pure cutting planes.

    Some ILPs are notoriously hard on standard cuts and require problem specific cuts that exploit the structure. You might want to look into that, too

     – curlycharcoal Apr 14 '20 at 05:03

0 Answers0