# 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
2k views

### How to compare two different formulations of a problem?

I somewhat know how to compare two MILP formulations of a problem that both use the same set of decision variables (as in the classical MTZ vs DFJ formulations of the TSP). I was wondering how two ...
• 2,150
2k views

### Polyhedra, Polyhedron, Polytopes and Polygon

About Polyhedra, Polyhedron, Polytopes and Polygon, what do they mean in the context of linear programming and what is the difference between them?
• 8,960
7k views

### How to find all vertices of a polyhedron

I have a convex polyhedron given by a set of linear inequalities, for example: $$x_1 \geq 0,~~ x_2 \geq 0, ~~x_3\geq 0 \\ x_1+x_2\leq 1,~~ x_2+x_3\leq 1,~~ x_3+x_1\leq 1$$ I want to list all the ...
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 ...
• 3,980
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$ ...
• 1,278
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 ...
• 103
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 ...
• 203
293 views

### How to get all the facet inequalities from a set of valid inequalities?

For a given set of valid inequalities $\cal V$ $$\left\{\sum_{i}^n w_k x_i + c_k \le 0\right\}_k$$ we can obtain a polyhedron $P$ in $n$-dimensional space. It's known that the polyhedron $P$ can be ...
• 191
1k views

### Extreme rays of a small polyhedral cone: How do I get them?

In a nutshell I have a small 2-dimensional polyhedral cone. $$C=\{(x_1,x_2): 2x_1-x_2 \leq 0, x_1+3x_2 \leq 0\}$$ I am looking for a simple, illustrative, procedure to get its extreme rays. Any ...
• 1,691
974 views

### Linear Program: Verify whether a feasible solution is an extreme point

My question is about a Linear Program (LP) of the form $\bf Ax\ge b$ with $\bf x\ge0$. From a theoretical standpoint: Given a feasible solution $\mathbf{x^{(0)}}$, how can we check (verify) whether it ...
457 views

### Extreme point and extreme ray of a network flow problem

"It is a well-known result in network flow theory that an extreme point and an extreme ray of the polyhedron defined by the convex hull of feasible region corresponds to a path and cycle (resp.) ...
133 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
253 views

• 123
32 views

• 111
1 vote
127 views

### Vertices of Polytope using Gurobi

Is there any way I can obtain all the vertices of a polytope using Gurobi? If this isn't possible, can I log all the intermediate vertices that Simplex finds before it hits the optimal one?
Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid A x \leq b\}$ is integer, while $A$ is ...