Re-formulating an LP where a subset of constraints can be loosened?

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"?

• What you are looking for seems to be categorized as the pre-solving phase. Do you try that? Commented Feb 3 at 10:53
• 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.
– prubin
Commented Feb 3 at 16:38
• @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. Commented Feb 3 at 23:26
• 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.
– prubin
Commented Feb 4 at 16:17