7
$\begingroup$

Suppose I have a linear program (LP) that has many optimal solutions. Of those optima, I want to find the optimum that activates (aka, "pegs" or "bumps") the largest number of constraints. Is there a general mechanism to achieve this?

I was able to achieve what I wanted via MIP by duplicating the constraints and adding a binary variable for each of the duplicates -- an "enabler". I then maximize the sum of those. It gives very good results. However, this takes my 30ms LP to two minutes of processing (using Gurobi), and that's not an acceptable delay.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
8
$\begingroup$

Suppose your problem is of the form $\min c^Tx$ subject to $Ax+e =b$, where $e$ denotes the slack variables.

You could proceed in two steps.

  1. Solve the initial LP. Let $z^*$ be the value of the optimal solution.
  2. Solve the initial LP with the following modifications: add the constraint that the objective function must equal $z^*$ ($c^Tx = z^*$), and instead minimize the sum of the slack variables ($\mathbb{1}^Te$), or perhaps the largest slack variable ($\max_i \{e_i\}$).

Maybe it is also worth trying to directly minimize the slack variables along with $c^Tx$, but this might degrade the objective function value: $$ \min c^T x + w^Te $$ $$ \mbox{subject to } Ax+e = b $$ You will have to tweak $w$.

Improve this answer
$\endgroup$
4
  • 7
    $\begingroup$ Just to clarify, minimizing the sum (or maximum) of slacks might not yield the maximum number of 0 slacks, so this is an approximation. $\endgroup$
    – RobPratt
    Feb 18, 2022 at 18:19
  • 2
    $\begingroup$ Further to @Rob Pratt 's comments, paragraph 2 minimizes total slackness, not number of slack constraints. So basically, .minimizing the convex $L^1$ norm as a proxy to the non-convex $L^0$ "norm". Maybe that's good enough for what the OP really cares about? $\endgroup$
    – Mark L. Stone
    Feb 18, 2022 at 19:16
  • $\begingroup$ Yes, good point, I guess the OP would have to specify if he prefers having $1$ active constraint, or $2$ "nearly" active. $\endgroup$
    – Kuifje
    Feb 18, 2022 at 19:27
  • $\begingroup$ In my small experiments I just ran, manually adding the slack sum to the minimizer does help quit a bit; it's about 4x better than letting the slacks float. The MIP approach is 8x better. It makes me wonder about doing something slightly more complex than an LP; maybe an $e^2$ would be interesting, or maybe some of these optimization tools do support an $L^0$ norm, or maybe there is some way to maximize variance. $\endgroup$
    – Brannon
    Feb 18, 2022 at 19:51
4
$\begingroup$

Finding all optima of a linear program can be NP-annoying, so finding the optimum with the most binding constraints is likely also NP-annoying.

The multiple optima will be vertices of a facet of the feasible region, so you can explore them by sliding along edges of the optimal facet. A heuristic approach would be as follows. First, solve the LP. Find a nonbasic variable whose reduced cost is 0 and pivot it into the basis, taking you to another vertex. Keep track of each basis visited (you just need to record a boolean vector indicating which variables are basic or the list of basic variables; you don't need to record variable values) and if you wind up at a vertex already visited, don't pick the same nonbasic variable for the next pivot (to avoid looping). Repeat until you can't find a new pivot to make or you run out of time. Obviously, at each vertex you'll count active constraints and retain as incumbent the vertex with the most active constraints.

A slightly more sophisticated approach might use something like tabu search to avoid getting stuck in one area of the optimal facet.

Improve this answer
$\endgroup$

Your Answer

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

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