# Tag Info

### 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$...
• 5,412
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 ...
• 6,167

### 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"...
• 39.1k
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 ...
• 1,667
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 ...
• 3,188

### 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 ...

### 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 ...
• 671
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 ...
• 2,725

• 39.1k

### 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 ...
• 5,919

### 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 ...
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. ...
• 39.1k

### 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 ...

### 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 ...
• 3,166
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 ...
• 39.1k
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 ...
• 1,750