Questions tagged [convex-hull]
For questions related to the convex hull of a set, often (but not limited to) referring to the feasible region in optimization.
8
questions
5
votes
1answer
61 views
Can we remove symmetry from polytopes for analyzing them?
Consider the boolean quadric polytope, which is defined on a complete graph $G=(V,E)$ as:
$$QP = \{(x,z) \in \{0,1\}^{V+E} : x_ix_j=z_{ij} \}$$
Now we can generate for small examples with tools like ...
1
vote
1answer
136 views
How to prove the following statement about convex hulls?
Consider $M$ finite sets of integer points $P_m$, $m=1,\ldots,M$. Let
$$A = \left\{x_m\in\operatorname{conv}P_m, m=1,\dots,M, \sum_{m=1}^MN_mx_m=0\right\}$$
and
$$B =\operatorname{conv}\left\{x_m\in ...
4
votes
1answer
123 views
Extreme points of a simple polyhedron
Consider the polyhedron given by the set of inequalities
\begin{align}
\mathbf{b}^T\mathbf{x} ~&\leq~ c \\
\mathbf{e}^T\mathbf{x} - 1 ~&\leq~0 \\
\mathbf{x}~&\geq~0
\end{align}
where $\...
3
votes
0answers
64 views
Theoretical aspect of using extended formulation
If I can show a polyhedron Y is an extended formulation of polyhedron X and every extreme point in Y is integral, does that automatically imply the projection of Y onto the variable space of X gives ...
2
votes
1answer
115 views
How to transform these conditional constraints to linear integer ones in a more efficient way?
The conditional constraints A and B can be transformed to a set of linear integer constraints as follows:
A) $\text{if} \ x_1=0 \ \text{then} \ d_1=1 \ \text{else} \ d_1= 0\\ x_1\in {\rm I\!R}^{\geq ...
10
votes
3answers
266 views
Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?
Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities? If it is not, then what is?
For $m$ inequalities in $d$ ...
6
votes
0answers
80 views
What are the top three applications (in terms of number of citations) of the "reverse search" algorithm of David Avis?
I can see that this algorithm is quite popular, and that one of the original papers now has 820 citations on Google Scholar. However, what are the most highly cited applications of it?
If in Google ...
15
votes
1answer
774 views
When is the McCormick envelope exact?
I know that given $S$ of the form
$$
S = \{ (x,y,z) \in \mathbb R^3: \ell_x \leq x \leq u_x; \ell_y \leq y \leq u_y; z = xy\}
$$
with finite lower and upper bounds, the McCormick envelope of $S$ ...
