# Tag Info

13

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 gives the convex hull if and only if every cycle in $G$ has an even number of positive edges and an even number of odd edges (where an edge $ij$ is called ...

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

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

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

2

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 solver prefer larger values of $y$ over smaller values? (Again, this is problem dependent.) If so, you could eliminate the use of a binary variable and just use the ...

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