I have an LP of the structure below (omitting some constraints that are not directly applicable for this question).

$$\text{min } c'x$$

$$Ax + By \geq d$$

for a given $A \in R^{m \times a}_{>0}, B \in R^{m \times b}_{>0}, d \in R^m_{>0}, c \in R^a_{>0}$ and decision variables and bounds of $x \geq 0$ and $-M \leq y \leq 0$.

The open-source solver I am using to solve this LP finds the solution very quickly. However, I would like to re-formulate the constraint set to only enforce a percentage $T$ of the total $m$ constraints, where the other $(1-T)$ constraints would be bound by 0 on the right-hand side as opposed to $d$. By introducing a set of binary variables $z$, I can re-formulate the problem as a MILP.

$$\text{min } c'x$$

$$Ax + By \geq d'z$$

$$\sum_i z_i \geq mT$$

For a smaller subset of my original problem, the solver finds the optimal solution. However, it struggles to find optimality for the full problem. One thought I had to remedy the issue was to relax the constraints by introducing slack variables $s$ instead to preserve the LP.

$$\text{min } c'x - \lambda s$$

$$Ax + By = d - s$$

$$s \leq d$$

One difficulty here is that it is not obvious what to set the penalty $\lambda$ term to target a specific $T$, and I would assume a poor choice of $\lambda$ would allow the model to target solutions that maximize slack variables rather than minimize the original objective function.

Another thought I had was to iteratively add the constraints up to $T$ to the model in the order of how binding they are in the original LP. However, the other constraints the model has that I have not included would seem to make this not trivial as well.

In general, are there other re-formulations or heuristic methods for LPs that feature a toggle on how many constraints are picked to be "forced"?

  • $\begingroup$ What you are looking for seems to be categorized as the pre-solving phase. Do you try that? $\endgroup$
    – A.Omidi
    Feb 3 at 10:53
  • $\begingroup$ Are $A,B,x,y$ all nonnegative? If not, your binary variable reformulation is not completely relaxing constraints, since it does not allow the left sides to go negative. $\endgroup$
    – prubin
    Feb 3 at 16:38
  • $\begingroup$ @prubin Thank you for the clarification question, I should have been more clear. I have edited the question to reflect the bounds on the variables and that I want to toggle some constraints to be bound by $d$ or 0 on the right-hand side. Since $y$ is negative, the constraints where $z_i=0$ are still enforced. $\endgroup$
    – Mason
    Feb 3 at 23:26
  • $\begingroup$ Rather than looking for a reformulation or a heuristic, you might want to look at why the solver struggles on the full problem (lack of improvement in the incumbent solution, lack of improvement in the best bound, iterations taking a long time) and see if there are solver parameters you can tweak to improve performance. $\endgroup$
    – prubin
    Feb 4 at 16:17


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.