2
$\begingroup$

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?

$\endgroup$
2
  • $\begingroup$ Maybe I'm missing something but why not just add a constraint $c=0$? $\endgroup$ – LarrySnyder610 Dec 8 '20 at 15:39
  • $\begingroup$ Hi Larry, I‘m sorry, I think I described the problem not precisely enough (of just wrong). I edited it. $\endgroup$ – Claudi Dec 8 '20 at 18:17
1
$\begingroup$

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$).

$\endgroup$
5
  • $\begingroup$ Hi prubin, thanks for your answer. If I understand it correctly, you are talking about the "classical" seperating hyperplane approach? The problem: I want to check collision for two polytopes. For this I build the minkowsi difference where I only have to check if the point (0.0, 0.0, 0.0) is outside to avoid collision. The idea was to use ∑vj αj − ∑wj βj = 0 (1), ∑αj = 1 (2), ∑βj = 1 (3) for that. $\endgroup$ – Claudi Dec 9 '20 at 8:49
  • $\begingroup$ Furthermore I want to add polytope rotation as variables to the problem, using linearized sine and cosine functions. They can be easily added to the above equation. However with this I can't identify the faces of the minkowski polytope prior to the calculation. $\endgroup$ – Claudi Dec 9 '20 at 8:49
  • $\begingroup$ You have identified the equations (along with sign restrictions on $\alpha$ and $\beta$) that can be solved to determine if zero difference (intersection) is possible. If that system is feasible, the intersection is nonempty; if infeasible, the intersection is empty. Is there some reason why you need feasible to mean empty intersection and infeasible to mean nonempty intersection? $\endgroup$ – prubin Dec 10 '20 at 18:48
  • $\begingroup$ I do packaging optimization and one restriction is, that the polytopes do not collide. No collision needs to be feasible, so that the position and rotation can be further optimized and collision must be infeasible so that this means no valid solution. I know I can do it when I take the objective function into account, but I want to optimize other criterions, thats why I don't want to put the collision avoidance into the objective function. $\endgroup$ – Claudi Dec 11 '20 at 15:43
  • $\begingroup$ Hi prubin. That's it. And it is so easy, thanks a lot! $\endgroup$ – Claudi Dec 16 '20 at 9:30

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.