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

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

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. Section 2.3 (Exploitation of symmetry) of the paper provides relevant details (your example is also mentioned). Edit: Here is the website where PANDA can be ...

3

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\leq 1$. Then $$\lambda X + (1-\lambda) Y = (\lambda x_1 + (1-\lambda)y_1,\ldots,\lambda x_M + (1-\lambda)y_M).$$ Since \begin{align}N_1x_1 + \ldots + N_Mx_M &...

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