-1
$\begingroup$

Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a subspace of dimension $length(x)$ yields feasible points of union of original programs?

$C$ could have exponentially many constraints as $A$ and $B$ and $length(y)$ could be exponentially as big as $length(x)$.

$\endgroup$

closed as off-topic by Emil Jeřábek, Stefan Kohl, Chris Godsil, Mikhail Katz, Piotr Hajlasz Jun 15 '18 at 15:09

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "MathOverflow is for mathematicians to ask each other questions about their research. See Math.StackExchange to ask general questions in mathematics." – Emil Jeřábek, Chris Godsil, Piotr Hajlasz
If this question can be reworded to fit the rules in the help center, please edit the question.

1
$\begingroup$

The answer is: This can be done if and only if the union is convex.

Indeed, let $P:=\{x\colon Ax\le b\}$, $Q:=\{x\colon Bx\le c\}$, and $R:=P\cup Q$. The necessity of the convexity of $R$ was already pointed out by Robert Israel.

Now suppose that $R$ is convex. Note that $P$ and $Q$ are convex polyhedra. Also, any extreme point $p$ of the convex set $R$ is an extreme point of either $P$ or $Q$, depending on whether $p\in P$ or $p\in Q$; similarly for the extreme rays of $R$. So, $R$ is a convex polyhedron and hence the intersection of a finite number of half-spaces; that is, $R=\{x\colon Cx\le d\}$ for some appropriate $C$ and $d$.

Added in response to a comment by the OP: If $R$ is convex, then the plane of any face of $R$ is the plane of a face of either $P$ or $Q$, and so, the matrix $[C\ d]$ is a row-submatrix of the matrix $\begin{bmatrix}A&b\\B&c\end{bmatrix}$. Indeed, take any support plane $S$ of the convex polyhedron $R$. Then $S$ is a support plane of both $P$ and $Q$. Suppose now that $F:=S\cap R$ is of dimension $n-1$, where $n$ is the maximum of the dimensions of $P$ and $Q$; that is, $F$ is a face of $R$. Then either $S\cap P$ or $S\cap Q$ is of dimension $n-1$, and hence a face of $P$ or $Q$, as desired.

$\endgroup$
  • $\begingroup$ @Freeman. : The matrix $[C\ d]$ is a row-submatrix of the matrix $\begin{bmatrix}A&b\\B&c\end{bmatrix}$. I have added details on this to the answer. $\endgroup$ – Iosif Pinelis Jun 14 '18 at 12:47
  • $\begingroup$ @Freeman. : No, this latter $C$ would work for the intersection of $P$ and $Q$, but not for the union in general. $\endgroup$ – Iosif Pinelis Jun 14 '18 at 13:19
  • $\begingroup$ @Freeman. : I am not an expert on execution time, but the work on faces described in my answer seems pretty simple. $\endgroup$ – Iosif Pinelis Jun 14 '18 at 13:36
  • 1
    $\begingroup$ A row of $A_i x \le b_i$ of $A x \le b$ should be included iff it doesn't cut off any of the feasible set for $C x \le d$, i.e. if the linear programming problem max $A_i x$ subject to $C x \le d$ has optimal value $\le b_i$. This can be decided in polynomial time. $\endgroup$ – Robert Israel Jun 14 '18 at 19:07
1
$\begingroup$

The feasible region in linear programming is convex, and linear projections of convex sets are convex, so if the union of the feasible regions for $Ax \le b$ and $Bx \le c$ is non-convex there is no way to do this.

On the other hand, you might do this with a binary ($0-1$) variable $z$: if feasible regions of $Ax \le b$ and $Bx \le c$ are bounded take constraints $A x - M z \le b$ and $ B x - M (1-z) \le c$ , where $M$ is sufficiently large.

$\endgroup$

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