Name
Abstract | ||
|---|---|---|
We study the complexity of computing the mixed-integer hull conv(P∩(Zn×Rd)) of a polyhedron P. Given an inequality description, with one integer variable, the mixed-integer hull can have exponentially many vertices and facets in d. For n,d fixed, we give an algorithm to find the mixed-integer hull in polynomial time. Given a finite set V⊆Qn+d, with n fixed, we compute a vertex description of the mixed-integer hull of conv(V) in polynomial time and give bounds on the number of vertices of the mixed-integer hull. |
Year | DOI | Venue |
|---|---|---|
2015 | 10.1016/j.orl.2015.03.002 | Operations Research Letters |
Keywords | Field | DocType |
Mixed-integer hull,Polyhedron,Mixed-integer concave minimization | Integer,Discrete mathematics,Combinatorics,Mathematical optimization,Finite set,Tight span,Vertex (geometry),Polyhedron,Time complexity,Hull,Mathematics | Journal |
Volume | Issue | ISSN |
43 | 3 | 0167-6377 |
Citations | PageRank | References |
2 | 0.42 | 8 |
Authors | ||
3 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Robert Hildebrand | 1 | 69 | 7.82 |
| Timm Oertel | 2 | 29 | 5.06 |
| Robert Weismantel | 3 | 964 | 90.05 |