3
$\begingroup$

My question is about how to construct a mixed integer programming to model that there is no feasible solution to a given linear system. Specifically, given $x\in \mathbb{R}^{n}$ and $z\in \{0,1\}^{d}$, we have a linear system $f_i(x,z)\le s_i, i = 1,2,\cdots,m$. The linear system can be written in matrix form: $\boldsymbol{A}x + \boldsymbol{B}z\le s$. I have another linear inequality $g(x,z)\le c$. The statement I want to model is:

"there is no feasible solution such that $f_i(x,z)\le s_i, i = 1,2,\cdots,m$ and $g(x,z)\le c$ hold simultaneously."

Is there any way to model this statement in mixed integer programming?

P.S.: Since the question above is only part of my overall problem, I will briefly explain the big picture behind the problem. I want to model a defender-attacker problem. The defender tries to find the best defending choice $\beta\in \{0,1\}^{a}$ with an objective to minimize $\Arrowvert \beta \Arrowvert_0$. The defender requires that once the constraints on the attacker ($f_i(x,z)\le s_i(\beta), i = 1,2,\cdots,m$) hold, the event ($g(x,z)\le c$) will not happen.

Methods I tried:

  1. Farkas-type theorem of alternative. This approach does not work since it requires first to relax the above mixed integer inequalities into linear programming (LP). However, directly relaxing $z\in \{0,1\}^{d}$ to $z\in[0,1]$ is too coarse.
  2. Integer-version theorem of alternative. Currently, I have only found one paper "Cutting planes from a mixed integer Farkas lemma", which requires [A,B] to have full row rank.
$\endgroup$
0
3
$\begingroup$

The following assumes that $s$ is a function of $\beta$ (per your more detailed explanation of the problem).

You can approach this via a row-generation method (similar to logical Benders decomposition). Start with the master problem $$\min\ \left\Vert \beta\right\Vert _{0}$$subject to only the constraint that $\beta\in \lbrace 0,1 \rbrace^a$. Each time the solver finds a candidate solution $\hat\beta$ to the master, calculate $s(\hat\beta)$ and try to solve the linear system\begin{align*} f(x,z) & \le s(\hat{\beta})\\ g(x,z) & \le c. \end{align*} If the linear system is inconsistent, accept $\hat\beta$. If the linear system has a solution, add a "no good" constraint of the form $$ \sum_{i:\hat{\beta}_{i}=0}\beta_{i}+\sum_{i:\hat{\beta}=1}\left(1-\beta_{i}\right)\ge1 $$ to the master problem. Depending on the IP solver you are using for the master problem, this could either mean solving the master from root node to "optimality" each iteration, or it could mean using a callback to add "no good" constraints to the master on the fly (interrupting the solver when a candidate solution is found, then resuming where the solver left off after adding the constraint).

$\endgroup$
2
  • $\begingroup$ Thanks so much for your help. I have a follow-up question: is it possible to model the whole problem as a big single MILP? $\endgroup$ – Yu-di Huang Mar 22 at 13:48
  • $\begingroup$ Probably not. If, for the sake of argument, $s(\beta)$ were a linear function of $\beta$, I think you could enforce the defender's requirement by adding a truly enormous number of linear constraints involving $z$, $\beta$ and some new (continuous) variables, but I think you would be looking at adding $2^{(a+d)}$ systems of equations, each with $m+1$ associated new variables. $\endgroup$ – prubin Mar 23 at 15:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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