21 votes

Polyhedra, Polyhedron, Polytopes and Polygon

The following definitions are taken from this lecture. Polyhedron A polyhedron in $\Bbb R^n$ is the intersection of finitely many sets of all points $x$, such that $ax\le b$ for some $a\in\Bbb R^n$...
ə̷̶̸͇̘̜́̍͗̂̄︣͟'s user avatar
20 votes
Accepted

How to compare two different formulations of a problem?

Even if the decision variables differ, you may still be able to prove that one of the formulations is stronger than the other by introducing an appropriate mapping. Take for example a flow ...
Kevin Dalmeijer's user avatar
15 votes

How to compare two different formulations of a problem?

I'm not sure there is a single, definitive best way to compare models, and if there is I likely have never seen it applied. I lean toward computational comparisons if properly done, but "properly done"...
prubin's user avatar
  • 39.1k
12 votes
Accepted

How to find all vertices of a polyhedron

The problem of enumerating all vertices of a polytope has been studied, see for example Generating All Vertices of a Polyhedron Is Hard by Khachiyan, Boros, Borys, Elbassioni & Gurvich (available ...
dhasson's user avatar
  • 1,667
11 votes
Accepted

Finding the linear functions defining a polyhedron through integer data?

You are looking for algorithms to find the integer convex hull of a polytope. Unfortunately, there is no easy way to do it efficiently and I am not sure the 2. point (the functions have integer ...
Philipp Christophel's user avatar
11 votes

How to compare two different formulations of a problem?

I agree with most of the comments here; Even if the decision variables are different, you may use proof by construction, for example, with appropriate mapping to prove that a formulation is stronger ...
Karmel Shehadeh's user avatar
10 votes

Polyhedra, Polyhedron, Polytopes and Polygon

These are all names used for the feasible set of a linear programming problem. In other words, all the combination of values for the decision variables that correspond to a solution, hence satisfying ...
Thiago Serra's user avatar
8 votes
Accepted

Simplest way to eliminate redundant constraints due to a new cut

As a partial answer, Telgen (1977) has shown that eliminating all redundant inequalities is LP-equivalent, i.e. in general not easier than solving linear programs. Clearly, this does not exclude ...
Marcus Ritt's user avatar
  • 2,725
8 votes

References to publications on representation of any boolean function as a system of linear inequalities

If I understand correctly, you can obtain the desired linear constraints via conjunctive normal form. Explicitly, suppose $f(\bar{x}_1,\dots,\bar{x}_n)=1$, and let $S_0 = \{j\in\{1,\dots,n\}:\bar{x}...
RobPratt's user avatar
  • 32k
6 votes

How to find all vertices of a polyhedron

You obtain all vertices of a polytope using polymake. You can directly try the online version.
Graph4Me Consultant's user avatar
6 votes

How to compare two different formulations of a problem?

I would like to add some criteria for the computational comparison, that I think is appropriate and common. As mentioned, the experiments should be performed on standard benchmarks, and if available, ...
Mostafa's user avatar
  • 2,104
6 votes
Accepted

Estimation of the number of optimum vertices

Your belief that there will be two different vertices in the set of optimal solutions as long as the feasible polyhedron contains more than a single point is incorrect. In practice, most LPs have ...
prubin's user avatar
  • 39.1k
6 votes
Accepted

Solving convex programs defined by separation oracles?

The algorithm you are describing is Kelley's Cutting-Plane Method. Wikipedia gives a good description, and the original paper can be found here. Note that this differs from the cutting plane methods ...
Kevin Dalmeijer's user avatar
6 votes
Accepted

Extreme point and extreme ray of a network flow problem

I believe this result (with proof) is contained in the text book "Network Flows" by Ahuja, Magnati and Orlin. In particular, chapter 11 is on the Network Simplex algorithm and Theorems 11.2 ...
Robert Schwarz's user avatar
6 votes

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?

There are many algorithms suggested for converting the "external" representation of a polyhedron (i.e., the set of solutions to a finite set of linear inequalities) into an "internal" one (i.e., a ...
Marco Lübbecke's user avatar
5 votes

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?

As far as I can tell from the information I could on the "Reverse Search" algorithm, it is a technique that helps to enumerate combinatorial structures. In particular the paper you mention in a ...
Paul Bouman's user avatar
  • 2,100
5 votes

Is the "reverse search" algorithm of David Avis the state-of-the-art method for finding discrete solutions to a system of linear inequalities?

I am not familiar with the "reverse search" algorithm. For solving systems of linear inequalities in practice, algorithms for integer programming or constraint programming are probably most ...
Kevin Dalmeijer's user avatar
5 votes
Accepted

On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope

The answer is yes, and the proof is trivial. Recall that a TUM matrix has all coefficients in $\lbrace -1, 0, 1\rbrace.$ Start with any $P := \{ x\in \mathbb {R}^{n} \mid A x \leq b\}$ that is integer....
prubin's user avatar
  • 39.1k
5 votes
Accepted

Discrete point inside a polygon formed by set of vertices

You can test whether a point $(x,y)$ appears inside a convex polygon with vertices $(x_i,y_i)$ by solving a linear programming problem (with no objective): \begin{align} \sum_i \lambda_i &= 1 \\ \...
RobPratt's user avatar
  • 32k
4 votes

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

For your simple (2 variable, 2 side) cone, you are on the right track. An extreme ray will be defined by $n-1$ binding constraints, which in this case means either $2x_1 - x_2= 0$ or $x_1 + 3x_2 = 0$. ...
prubin's user avatar
  • 39.1k
4 votes
Accepted

Extreme points of a simple polyhedron

Let's assume that (a) the full polyhedron is not empty (a solution to the inequalities exists) and (b) you have identified the extreme points of the unit simplex that remain extreme points after the ...
prubin's user avatar
  • 39.1k
4 votes
Accepted

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

The page you linked is correct. Note that $Ax\ge b$ there includes any nonnegativity constraints, so their $A$ combines your $A$ and an identity matrix. For a feasible solution $x\in\mathbb{R}^n$ to ...
prubin's user avatar
  • 39.1k
3 votes

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

I believe the answer to your question is principally "no." You mention these implementations, and there are some more, like porta or polymake, but in principle, this is an enormously ...
Marco Lübbecke's user avatar
3 votes

How to find all vertices of a polyhedron

It seems to me that cdd libraries can be useful to solve this problem. Description is available at cdd. There is an implementation of this function in R: rcdd. You can use the following instruction to ...
Sławomir Jarek's user avatar
3 votes
Accepted

Faces and Facets in a convex polyhedron

The Euler equation was originally for polyhedra in three dimensions. When applied in two dimensions, it is for planar graphs (graphs with no edge crossings). Your example qualifies as a planar graph. ...
prubin's user avatar
  • 39.1k
3 votes

On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope

You might want to look at MRP(Material Requirements Planning)/Leontief matrices. In an MRP/Leontief matrix/model: Each constraint is an equality, Every column has exactly one positive coefficient and ...
LINDO Systems's user avatar
3 votes

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

In https://scholar.google.com/citations?view_op=view_citation&hl=da&user=kEOeI2gAAAAJ&cstart=20&pagesize=80&citation_for_view=kEOeI2gAAAAJ:KlAtU1dfN6UC Nimrod Megiddo proves that ...
ErlingMOSEK's user avatar
  • 3,166
3 votes
Accepted

Convex not strictly convex!

I think you are confusing two things here. A linear program has a convex feasible region. The term "convex space" refers to an entire vector space, not to a particular region (such as an LP ...
prubin's user avatar
  • 39.1k
2 votes
Accepted

How to enumerate all vertices of a polyhedron as a stream

You can check the lrs software implemented by David Avis from McGill. The software implements the reverse search algorithm described in this serie of papers: Reverse Search: Origins Since the output ...
Stefano Gualandi's user avatar
2 votes
Accepted

Extreme points for capacitated flow polytope

You can have a look at chapter 13, namely "Path and flow polyhedra and total unimodularity", of Alexander Schrijver's masterpiece "Combinatorial Optimization - Polyhedra and Efficiency&...
Hexaly's user avatar
  • 2,976

Only top scored, non community-wiki answers of a minimum length are eligible