3
$\begingroup$

I want to add slack variables to the following feasibility problem. Optimally I want the sum of the slack variables to be zero.

Given the problem

$$\min 0$$ s.t. $$e(x) = 0$$ $$l(x) \leq 0$$ $$g(x) \geq 0$$

Is the following a correct way to add slack variables?

$$\min 0 + |\xi_e| + \xi_l + \xi_g$$ s.t. $$e(x) = \xi_e$$ $$l(x) \leq \xi_l$$ $$g(x) \geq -\xi_g$$ $$\xi_l \geq 0$$ $$\xi_g \geq 0$$

Also, if I add a slack variable to one constrain in the model, do I have to add slack variables to all other constraints?

$\endgroup$
2
  • $\begingroup$ Hi @Horvetz, welcome to or.stackexchange. Can you elaborate a little om what you want to achieve by adding slack variables? Do you for example need your constraints to be satisfied (zero slack) in an optimal solution $\endgroup$
    – Sune
    Jun 7, 2022 at 20:36
  • $\begingroup$ @Sune Yes. It is a feasibility problem (c = 0). I'll clarify the question. Thanks! $\endgroup$
    – Rudinberry
    Jun 7, 2022 at 20:38

1 Answer 1

5
$\begingroup$

You can add slacks to whatever combination of constraints you want. But any constraint not having a slack must be satisfiable in its "no slack" form, else the model will be infeasible. And not using a slack on certain constraints might require larger slacks on other constraints; but that will not matter if the original unslacked model is feasible (technically, that the solver can find a feasible point, which if any constraints are non-convex, and the solver is not global, it might not necessarily be able to do, even if the model is actually feasible)

Your formulation adds a nonlinear term to the objective (although it is still convex), because absolute value is nonlinear. The slacks can all be kept and used as continuous linear (the nicest case) by using a double-sided inequality without absolute value, and constraining the slack used on both sides of that inequality constraint to be nonnegative. In practice, some optimization modeling systems (front end to solver) might reformulate your version to essentially the same as mine.

$$\min \xi_e + \xi_l + \xi_g$$ s.t. $$-\xi_e \le e(x)$$ $$e(x) \le \xi_e$$ $$\xi_e \geq 0$$ $$l(x) \leq \xi_l$$ $$g(x) \geq -\xi_g$$ $$\xi_l \geq 0$$ $$\xi_g \geq 0$$

where the first 2 inequality constraints replace your equality constraint.

$\endgroup$
1
  • 1
    $\begingroup$ Yes, if you have a vector or matrix of constraints, i.e.., evaluating to a vector or matrix RHS, i.e., $n$ or $n^2$ or $mn$ (scalar) constraints written in vector or matrix form as a single vector or matrix constraint. In the case of a vector, you can think of using a vector slack variable, with all elements of the slack vector constrained to be nonnengative. If the constraint involves a vector or matrix variable on the LHS, but evaluates to a scalar (i.e., scalar RHS), then there would only be a single scalar slack variable for that constraint. $\endgroup$ Jun 8, 2022 at 14:30

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.