Name
Title | ||
|---|---|---|
Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices |
Abstract | ||
|---|---|---|
We present branching-on-hyperplane methods for solving mixed integer linear and mixed integer convex programs. In particular, we formulate the problem of finding a good branching hyperplane using a novel concept of adjoint lattice. We also reformulate the problem of rounding a continuous solution to a mixed integer solution. A worst case complexity of a Lenstra-type algorithm is established using an approximate log-barrier center to obtain an ellipsoidal rounding of the feasible set. The results for the mixed integer convex programming also establish a complexity result for the mixed integer second order cone programming and mixed integer semidefinite programming feasibility problems as a special case. Our results motivate an alternative reformulation technique and a branching heuristic using a generalized (e.g., ellipsoidal) norm reduced basis available at the root node. |
Year | DOI | Venue |
|---|---|---|
2011 | 10.1007/s10898-010-9554-4 | J. Global Optimization |
Keywords | Field | DocType |
Linear programming,Volumetric center,Analytic center,Interior point methods,Convex programming,Mixed integer programming,Lattice basis reduction | Discrete mathematics,Cutting-plane method,Mathematical optimization,Branch and cut,Branch and price,Integer points in convex polyhedra,Feasible region,Integer programming,Linear programming relaxation,Mathematics,Special ordered set | Journal |
Volume | Issue | ISSN |
49 | 4 | 0925-5001 |
Citations | PageRank | References |
4 | 0.44 | 21 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Sanjay Mehrotra | 1 | 521 | 77.18 |
| ZhiFeng Li | 2 | 1073 | 55.45 |