Defining Solution Space in MILP / LP using If Then Statements

Question

I have the following statements for an MILP:

Variables:

• $c$ (can be $1$ or $0$);

• $\alpha_j$ (real numbers with $0\le\alpha_j\le1$).

I have a linear inequality system for $\alpha_j$:

• $\sum_jv_j\cdot\alpha_j = 0$ (with $v_j$ constants)

• $\sum\alpha_j = c$

and I have the following logic:

• If there exists a solution for $c=1$, the formulation should be infeasible;

• If there exists the only one solution $c = 0$ (each $\alpha_j$ must be $0$) the formulation should be feasible.

I need some more equations or changes so that the logic above holds. The background is the following. I want to test if a point (here $(0.0, 0.0, 0.0)$) is inside a polygon. The constants $v_j$ are the vertices of the polygon. The above equations have to be set up for each spatial direction, here we only focus on $x$. If no solution can be found for $c = 1$, the point is outside. For my calculations I have to make sure that the point is outside.

First idea:

When I use an additional constraint $c = 1$ the MILP finds a solution for $c = 1$ und no solution for $c = 0$. This helps to identify if $c$ can be $1$ but this flips the feasible solution space since the solver breaks when $c = 0$ which should be the feasible one. Adding the constraint $c = 0$ will not help, since it is not enough that $c = 0$ is one potential solution, it must be the only one valid solution.

Second idea:

When I use the objective function max(c) I can conclude that IF max(c) = 1 THEN not feasible (or IF max(c) = 0 THEN feasible). However I don't want to use $c$ in the objective function.

Is there any other possibility to change the formulation so that the logic above holds?

Answer 1

I'm not sure I understand the question correctly, but I'm going to assume that you are given a polytope $P\subset \mathbb{R}^d$ specified by its vertex set $v_1,\dots,v_n \in \mathbb{R}^d$ and a point $x\in \mathbb{R}^d$, and you want an optimization model that will be infeasible if $x\in P$ and feasible if $x\notin P$. (The opposite approach -- feasible if $x\in P$ and infeasible if $x\notin P$ -- is easy to formulate.) Let $\alpha \in \mathbb{R}^d$ be a vector of sign-unrestricted (free) variables, and consider the system of inequalities $$\alpha^\prime x \ge \alpha^\prime v_i + 1 \quad\forall i=1,\dots,n.$$You can turn it into a linear program by maximizing or minimizing 0 subject to those constraints.

If $x\in P$, there cannot be a feasible solution, since $x$ would be a convex combination of the $v_i$ and thus $\alpha^\prime x$ would be a convex combination of the $\alpha^\prime v_i$.

If $x\notin P$, you can get a feasible solution as follows. Let $F$ be any face of $P$ such that $x$ lies on the opposite side of $F$ from $P$ (meaning that $F$ is the intersection of $P$ with a hyperplane $H = \lbrace y\in \mathbb{R}^d : \alpha^\prime y = \alpha_0\rbrace$ such that $y\in P \implies \alpha^\prime y \le \alpha_0$ and $\alpha^\prime x \gt \alpha_0$). Just scale up $\alpha$ as needed to get the minimum difference between $\alpha^\prime x$ and any $\alpha^\prime v_i$ to be at least 1.

Edit: It appears I misunderstood the question. Given two convex polytopes $P_1$ and $P_2$ in $\mathbb{R}^d$, to create constraints that are feasible only if $P_1 \cap P_2 = \emptyset$, you can add free variables $w_1, \dots, w_d$ and $u$ along with the constraints $$w^\prime x \ge u + \epsilon\quad \forall x\in P_1$$and $$w^\prime x \le u - \epsilon\quad \forall x\in P_2,$$where $\epsilon$ is a small positive constant and $-1\le w_i \le 1$ for all $i$. (Bounding $w$ is necessary to avoid huge values that let the constraints be "satisfied" courtesy of rounding error.) If a solution exists, it represents a hyperplane separating the polygons. It will be infeasible if the polygons intersect or come too close (with "too close" related to the choice of $\epsilon$).