# Questions tagged [polyhedra]

For questions on the set of points that satisfy a finite set of linear inequalities.

12 questions with no upvoted or accepted answers
Filter by
Sorted by
Tagged with
132 views

### Characterization for total dual integrality

A problem I study reduces to whether the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is integral ($A$ is a matrix with coefficients in $\{0,1\}$). I know that the ...
• 137
86 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,278
118 views

### Polyhedra to Simplex by using convex combination of vertices

Optimization problems over linear constraints (defining a convex polyhedron) can be written as optimization over a simplex in a higher dimension. Let $\mathcal{P}$ be a bounded polyhedron, and the ...
• 3,980
95 views

### Any recommendations for learning about polyhedra and integer programming?

My knowledge on convex polyhedra and systems of linear inequalities (facets, edges, Farkas Lemma, projections, duality, etc.) is very scattered, and I'l like to go through a book to solidify it. I'm ...
• 233
96 views

### Appropriate Rotation Matrix in Nonconvex Optimization with Barrier

Let $x \in \mathbb{R}^n_+$ be a variable such that $\sum_{i=1}^n x_i = 1$. In other words, $x$ is in a probability simplex. I am working on barrier-like functions in nonconvex optimization over such ...
• 3,980
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 ...
• 31
32 views

Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions: $$\text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, ... • 8,960 2 votes 0 answers 60 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 ... 1 vote 1 answer 34 views ### How to generate random bounded polytope by MATLAB defined by Ax=b, x≥0 How can one create a random bounded polytope in MATLAB, specified by the conditions ‎\lbrace‎x:~ Ax = b,~ x \geq 0‎\rbrace‎ 1 vote 0 answers 79 views ### Decomposition of Polyhedra There is no doubt that clear examples consolidate the understanding of concepts being learnt. I am new to finding the structure and decomposition of a polyhedra. Suppose that we have the system$$ \...
• 111
1 vote
There is a proof of how to derive distributionally robust chance constraints with ellipsoid bound. $$\inf_{\mathbb{P}\in\mathcal{D}^{WD}} \mathbb{P}\{\|\mathbf{A\zeta-b}\|_2 \leq 1\} \geq 1-\epsilon$$ ...