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.

Filter by
Sorted by
Tagged with
2 votes
0 answers
59 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 ...
2 votes
1 answer
48 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 ...
2 votes
2 answers
104 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 ...
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 ...
2 votes
1 answer
145 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 ...
5 votes
1 answer
242 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
0 answers
72 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
1 answer
193 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
3 answers
390 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
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 ...
16 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$ ...