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.
11
questions
2
votes
0
answers
57
views
System Stability constraints formulation
I am working with a system having a massless 2D plane and on that plane there is a rigid object with some mass placed on it. I want to support the plane with wooden sticks such that the system is ...
- 33
2
votes
1
answer
46
views
A tighter relaxation of the mix logical constraints
Suppose the following logical form there exists.
$$Iff: (x_{j,m} \land x_{k,m}) \implies ((C_{j} \leq S_{k}) \lor (C_{k} \leq S_{j}))$$
This is well-known as a no_overlap_constraint in the parallel ...
- 8,382
2
votes
2
answers
101
views
Faces and Facets in a convex polyhedron
I am willing to find the number of faces and facets in a convex polyhedron. Suppose, in the cube polyhedron there exists $8$ vertices, $12$ edges, and $6$ faces. It satisfies the Euler equation as ...
- 8,382
6
votes
1
answer
72
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 ...
- 3,635
2
votes
1
answer
142
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 ...
- 1,641
5
votes
1
answer
239
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 $\...
- 251
3
votes
0
answers
71
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 ...
- 31
2
votes
1
answer
191
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 ...
- 294
10
votes
3
answers
387
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$ ...
- 1,268
6
votes
0
answers
85
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 ...
- 1,268
15
votes
1
answer
1k
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$ ...
