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
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 ...
Ken Adams's user avatar
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 ...
A.Omidi's user avatar
  • 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 ...
A.Omidi's user avatar
  • 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 ...
user3680510's user avatar
  • 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 ...
k88074's user avatar
  • 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 $\...
dineshdileep's user avatar
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 ...
Octavia's user avatar
  • 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 ...
SAH's user avatar
  • 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$ ...
Nike Dattani's user avatar
  • 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 ...
Nike Dattani's user avatar
  • 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$ ...
Sriram Sankaranarayanan's user avatar