Questions tagged [polyhedra]
For questions on the set of points that satisfy a finite set of linear inequalities.
10
questions
1
vote
0answers
36 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 ...
5
votes
2answers
181 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 ...
3
votes
1answer
110 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$ ...
9
votes
1answer
136 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 ...
10
votes
1answer
161 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 ...
10
votes
3answers
195 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
0answers
71 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 ...
23
votes
6answers
1k 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 ...
14
votes
2answers
1k 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?
11
votes
1answer
136 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 ...
