# Tag Info

20

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$ and $b\in\Bbb R$. Polyhedra Polyhedra is the plural of polyhedron. Polytope A polytope is a bounded polyhedron, equivalent to the convex hull of a ...

19

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 formulation and a route formulation for a vehicle routing problem (minimization). Typically, the folllowing argument can be made: Given (fractional) values for the route ...

15

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" is in the eye of the beholder. The most obvious criteria for computational comparisons are that they use the same test problems (not selected because they ...

11

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 than another one. When comparing two different (yet equivalent) formulation for the same problem, I often use three criteria: (1) LP relaxation/tightness, (2) ...

11

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 coefficients) is even possible. I used to do this for studying cutting planes (for small toy problems) using PORTA (http://porta.zib.de/), which is not under ...

10

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 free online at Springer's website) and A Survey and Comparison of Methods for Finding All Vertices of Convex Polyhedral Sets by T. H. Matheiss and D. S. Rubin. ...

10

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 all of the constraints. In linear programming, you have continuous variables and linear constraints, which can be equalities or inequalities. For example, let ...

8

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 heuristics (e.g. A heuristic approach for identification of redundant constraints in linear programming models) or a better strategy for removing (a subset of) the ...

8

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}_j = 0\}$ and $S_1 = \{j\in\{1,\dots,n\}:\bar{x}_j = 1\}$. You want to enforce \left[\left(\bigwedge_{j\in S_0} \lnot x_j\right) \bigwedge \left(\bigwedge_{j\...

6

You obtain all vertices of a polytope using polymake. You can directly try the online version.

6

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 and 11.3 are about optimal solutions in the form of spanning trees. The proofs use the structure of the dual solutions, and also use previous results, so it's ...

6

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 unique solutions. As far as an upper bound on the number of optimal vertices, let's assume that you have $m$ constraints including sign restrictions on the ...

6

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 described in the note that you link. These 'ellipsoid method like methods' are also called cutting planes methods. The difference is that with Kelley's method, ...

6

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 finite set of generators, extreme points and extreme rays). At it's core there often is some sort of finding all (discrete) solutions to a set of linear ...

6

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, on more than one benchmark. Then, the metrics can be: Number of feasible solutions, Number of best found solutions, Number of optimal solutions, Gap to the ...

5

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 applicable. If you are concerned about theoretical complexity, there exist algorithms to solve integer programming problems in polynomial time in fixed dimension. For ...

4

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 new constraint has been added. Any other extreme points will necessarily satisfy the new constraint as an equality ($\mathbf{b}^T\mathbf{x}=c$). Since they are ...

4

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 comment deals with vertex and facet enumeration. Since it is a bit unclear what you mean by "discrete solutions", let us distinguish four cases. Finding a single ...

3

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 resource-consuming enumeration, and the list of facets will be very long, maybe too long. Yet, it may depend on your use case. In optimization practice, you almost ...

3

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$. In the first case, $x_2 = 2x_1$, so the ray will be either $(1, 2)$ or $(-1, -2)$. The first one is not feasible, so the winner is $(-1, -2)$. In the second ...

2

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". You will find characterizations based on cuts, which are the dual of flows in digraphs. This is linked to the famous max-flow min-cut theorem.

2

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 solve this problem: install.packages("rcdd") require(rcdd) scdd(makeH(rbind(-diag(3),c(1,1,0),c(0,1,1),c(1,0,1)),c(rep(0,3),rep(1,3))))

2

Generally I see on the papers, at first comparison according to number of variables and equations, after then experimental performance comparison on test problems.

2

The argument from the paper Geometric proofs for convex hull defining formulations, Operations Research Letters 44 (2016), 625-629, can be turned into a simple algorithm for writing a point in the stable set polytope for a chordal graph $G$ as a convex combination of incidence vectors of stable sets. Let the vertex set of $G$ be $\{1,\dots,n\}$, and let $x=(... 1 Here is a rough attempt at solving your problem. Let us denote the polytope$P = \operatorname{conv}(S)$(if I am to understand your OP correctly, we know that$P$is an integral polytope), and let$x \in P$be the point you want to find the convex combinators for. Further you mentioned in the comments that$P\$ is specified in H representation, so let us ...

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