# Questions tagged [polyhedra]

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

36 questions
Filter by
Sorted by
Tagged with
1 vote
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‎$
100 views

### Maximum distance between two extreme points of a polyhedron

Let $P := \{x:Ax\le b\}$ and $V := \{x\in P: x = \frac{x^1+x^2}{2} \implies x^1 = x^2 = x\}$. i.e., $V$ is the set of extreme points of $P$. Assume $P$ is bounded. Is there a fast algorithm to ...
20 views

### Supremum of a probabilistic function with ambiguity distribution set using Wasserstein metric

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$$ ...
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 ...
162 views

1 vote
388 views

### Discrete point inside a polygon formed by set of vertices

I am working on a problem where I have a set of 2D vertices and a test point. I want to chek whether the test point lies inside ...
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 ...
64 views

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 ...
1 vote
79 views

183 views

### What are examples of integral polytopes, where there exists an algorithm to write a given point as a convex combination of integral points?

Given a set of integer points $S$, one is often interested in finding $\operatorname{conv}(S)$ or characterizing certain cases, where $\operatorname{conv}(S)$ is described by few inequalities. ...
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 ...
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 ...
397 views

### Estimation of the number of optimum vertices

Consider any linear programming model of $n$ variables and $m$ constraints which has multiple optimum solutions. If it is possible, I'd like to know the lower and upper limits (in terms of $n$, $m$ ...
350 views

### Solving convex programs defined by separation oracles?

General question: What software can solve convex programs defined by a separation oracle? The objective function is concave, and the feasible set is a polytope. By a separation oracle I mean that I ...
875 views

### Simplest way to eliminate redundant constraints due to a new cut

I have a polyhedral set for constraining $x$: \begin{align} \mathcal{P} = \{x \in \mathbb{R}^n_{+} : \ Dx \leq d \} \end{align} where $D \in \mathbb{R}^{m \times n}, d \in \mathbb{R}^m$. I find the ...
201 views

### Finding the linear functions defining a polyhedron through integer data?

Let's say I have a bunch of linear functions $f_1,\cdots,f_n$ in $k$ variables; then $f_1,\cdots, f_n\le0$ defines a polyhedron $P$ in the $k$-dimensional space. What I'm looking for is going the ...
395 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$ ...
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 ...