13 votes
Accepted

When is the McCormick envelope exact?

For a function $f:[0,1]^n\to\mathbb{R}$ of the form $f(x_1,\dots,x_n)=\sum_{ij\in E}a_{ij}x_ix_j$, where $E$ is the edge set of a graph $G$ on the vertex set $\{1,\dots,n\}$, the McCormick envelope ...
Thomas Kalinowski'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
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
  • 38.8k
4 votes

Can we remove symmetry from polytopes for analyzing them?

Have a look at PANDA. It's a new alternative to porta/polymake with some improvements. One of the features it has is the possibility for specifying symmetry properties to accelerate the computation. ...
rasul's user avatar
  • 2,140
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
  • 38.8k
3 votes
Accepted

How to prove the following statement about convex hulls?

I think it should be possible. Firstly, let us see if we can establish that $A$ is convex. Take \begin{align}X &= (x_1,\ldots,x_M)\in A\\Y&=(y_1,\ldots,y_M)\in A.\end{align} Let $0\leq\lambda\...
Prahalad Venkateshan's user avatar
2 votes

How to transform these conditional constraints to linear integer ones in a more efficient way?

I don't think you can improve on A1 (which looks correct), other than perhaps tightening the bounds $M$ and $m$ (which would be dependent on the specifics of the problem). Regarding B, would the ...
prubin's user avatar
  • 38.8k
1 vote
Accepted

A tighter relaxation of the mix logical constraints

Yes, (3) through (7) yield a correct linearization of the original implication. But you don’t need to enforce $\iff$ for the $w$ variables, and so you can omit (5) and (7).
RobPratt's user avatar
  • 31.5k

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