Fixing a minimal number of variables in linear programming problem to worsen objective

integer programminglinear programmingmixed-integer programmingoptimization

Consider a fairly standard linear program with $A\in \mathbb{R}^{m\times n}$ and cost vector $c\in \mathbb{R}^n_{\geq 0}$ such that

$\begin{align*}\text{maximize}&& c^Tx\\\text{such that} && Ax \leq b\\ &&0\leq x \leq 1 \end{align*}$

In my application have a solution $z^*$ and the above linear program is solved to optimality. For some user defined limit $0 < L < z^*$, I'm looking to remove (set to zero) a minimal amount of columns $x_i$ such that the linear program objective decreases below $L$, e.g. the new objective $z^*_{new}< L$. I am looking for a nice way to formulate this as an mixed-integer program (preferably linear), but have so far not succeeded.

I tried introducing new variables $y_i$ such that $y_i=1$ iff $x_i=0$ and $y_i=0$ if $x_i$ is unrestricted (safe for the linear program). However, I run into trouble trying to formulate conditions which require that the original linear program (with fixed variables) is optimal. The 'closest' I got is:

$\begin{align*}\text{minimize}&&& 1^Ty\\\text{such that} && Ax &\leq b\\ &&c^Tx&\leq L\\ && x_i + y_i&\leq 1\;\;\;\;\;\;\;\;\;\; \forall i\in [m]\\&&x&\geq 0\\ &&y_i&\in\{0,1\}\;\;\;\; \forall i\in [m] \end{align*}$

But I see no easy way to require that solutions are only feasible if $x$ is an optimal solution to the original linear system with fixed variables, e.g. ensuring that $c^Tx$ is maximized in the sub-linear program, as the above models any feasible solution rather than any optimal solution of the original system of equations. Any suggestions to turn this problem into a MIP or otherwise solvable class of integer program would be very welcome, and any other insights into how to remove variables $x_i$ from the original linear programming solution in order to decrease the objective by as much as possible after reoptimization are welcome as well.

Best Answer

This is an instance of a bilevel program, as you can see it as an optimization problem where one of the constraints is that a variable is optimal in some other optimization problem. It can be represented as a MILP via KKT conditions.

Here is a test in the MATLAB Toolbox YALMIP https://yalmip.github.io/tutorial/bilevelprogramming/

A = randn(10,7);
b = 10*rand(10,1);
c = randn(7,1);
x = sdpvar(7,1);
optimize([0<=x<=1, A*x <= b],-c'*x)

z = value(c'*x);
y = binvar(7,1);
OuterC = [c'*x <= z - 0.1];
OuterO = sum(y);
InnerC = [0<=x<=1, x <= 1-y, A*x <= b]
InnerO = -c'*x;
solvebilevel(OuterC,OuterO,InnerC,InnerO,x)
value(x)
value(y)

This example uses the built-in naive bilevel solver. A typically better solution is to ask it to use an external MILP solver instead or manually use the kkt operator to define the MILP and then call the MILP solver

https://yalmip.github.io/example/bilevelprogrammingalternatives/

https://yalmip.github.io/command/kkt/

Related Question