Questions tagged [polyhedra]

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

Filter by
Sorted by
Tagged with
2 votes
0 answers
28 views

The facet-defining inequalities for a single resource scheduling problem

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+}, ...
A.Omidi's user avatar
  • 8,390
1 vote
1 answer
305 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 ...
Ken Adams's user avatar
2 votes
0 answers
57 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 ...
Ken Adams's user avatar
2 votes
1 answer
64 views

Does this kind of "partition" have a name?

Consider a convex polyhedron $A$. Assume we have subsets $A_1,\ldots,A_n$ of $A$ that are themselves covex polyhedra and are mutually disjoint except maybe sharing an edge, and that their union gives $...
pele's user avatar
  • 123
6 votes
2 answers
770 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 ...
Shuxue Jiaoshou's user avatar
2 votes
1 answer
110 views

Convex not strictly convex!

Update: Linear programming problems (LP) have a convex space, precisely vector space, such as a convex feasible region as pointed out by @prubin. Also, they may have either unique or multiple ...
A.Omidi's user avatar
  • 8,390
5 votes
1 answer
180 views

How to enumerate all vertices of a polyhedron as a stream

I need to find the vertices of a polyhedron from the defining halfspaces. In a previous question libraries for enumerating all vertices were mentioned. However i have a very large polyhedron (~100,000 ...
Daniel's user avatar
  • 103
2 votes
2 answers
101 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 ...
A.Omidi's user avatar
  • 8,390
0 votes
2 answers
153 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 ...
Analyst_311419's user avatar
6 votes
1 answer
783 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 ...
k88074's user avatar
  • 1,641
3 votes
1 answer
135 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 ...
batwing's user avatar
  • 1,458
5 votes
1 answer
239 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 $\...
dineshdileep's user avatar
1 vote
1 answer
172 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 ...
Vladimir VV's user avatar
6 votes
0 answers
124 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 ...
Surpass2019's user avatar
1 vote
0 answers
78 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 $$ \...
holala's user avatar
  • 111
1 vote
0 answers
106 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?
Grigoris Velegkas's user avatar
6 votes
1 answer
412 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.) ...
Pramesh Kumar's user avatar
9 votes
1 answer
277 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 ...
Eden Harder's user avatar
3 votes
0 answers
94 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 ...
independentvariable's user avatar
5 votes
2 answers
176 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. ...
user3680510's user avatar
  • 3,635
5 votes
0 answers
107 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 ...
independentvariable's user avatar
3 votes
0 answers
71 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 ...
Octavia's user avatar
  • 31
12 votes
3 answers
6k 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 ...
Erel Segal-Halevi's user avatar
3 votes
1 answer
350 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$ ...
G Oliveira's user avatar
10 votes
1 answer
329 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 ...
Areaperson's user avatar
10 votes
1 answer
199 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 ...
user12005284's user avatar
10 votes
3 answers
387 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$ ...
Nike Dattani's user avatar
  • 1,268
6 votes
0 answers
85 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 ...
Nike Dattani's user avatar
  • 1,268
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 ...
rasul's user avatar
  • 2,140
15 votes
2 answers
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?
A.Omidi's user avatar
  • 8,390
12 votes
1 answer
757 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 ...
independentvariable's user avatar