Questions tagged [polyhedra]
For questions on the set of points that satisfy a finite set of linear inequalities.
24
questions
2
votes
2
answers
66
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 ...
- 6,114
0
votes
2
answers
89
views
On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope
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 ...
- 119
6
votes
1
answer
143
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,493
3
votes
1
answer
103
views
Extreme points for capacitated flow polytope
Given a network as a directed acyclic graph with a source and sink, and non-negative edge capacities, I am interested in the extreme source-sink flows. More formally, I am interested in a ...
- 1,311
5
votes
1
answer
158
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 $\...
- 241
1
vote
1
answer
168
views
References to publications on representation of any boolean function as a system of linear inequalities
It is known that any boolean function may be represented, in some sense, as a system of linear inequalities. But my rather intensive literature search brought a little references. I will appreciate ...
- 79
6
votes
0
answers
101
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
1
vote
0
answers
71
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
0
answers
71
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?
6
votes
1
answer
292
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.) ...
- 346
9
votes
2
answers
200
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
3
votes
0
answers
84
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,786
5
votes
2
answers
151
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.
...
- 3,487
5
votes
0
answers
93
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,786
3
votes
0
answers
65
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
9
votes
3
answers
3k
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
1
answer
234
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$ ...
- 185
10
votes
1
answer
237
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
10
votes
1
answer
184
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
10
votes
3
answers
351
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,256
6
votes
0
answers
82
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,256
25
votes
6
answers
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,110
14
votes
2
answers
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?
- 6,114
12
votes
1
answer
455
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,786