This thesis presents novel approaches that use interior point concepts in solving mixed integer programs. Particularly, we use the analytic center cutting plane method to improve three of the main components of the branch-and-bound algorithm: cutting planes, heuristics, and branching.
First, we present an interior point branch-and-cut algorithm for structured integer programs based on Benders decomposition. We explore using Benders decomposition in a branch-and-cut framework where the Benders cuts are generated using the analytic center cutting plane method. The algorithm is tested on two classes of problems: the capacitated facility
location problem and the multicommodity capacitated fixed charge network design
problem. For
the capacitated facility location problem, the proposed approach was on average
2.5 times faster than Benders-branch-and-cut and 11 times faster than classical
Benders decomposition. For the multicommodity capacitated fixed charge network
design problem, the proposed approach was 4 times faster than Benders-branch-and-cut while classical Benders decomposition failed to solve the
majority of the tested instances.
Second, we present a heuristic algorithm for mixed integer programs based on interior points. As integer solutions
are typically in the interior, we use the analytic center cutting plane method to search for integer feasible points within the interior
of the feasible set. The
algorithm searches along two line segments that connect
the weighted analytic center and two extreme points of the linear
programming relaxation. Candidate points are rounded and
tested for feasibility. Cuts aimed to improve the objective function
and restore feasibility are then added to displace the weighted
analytic center until a feasible integer solution is found. The algorithm is composed of three phases. In the first, points along
the two line segments are rounded gradually to find integer feasible
solutions. Then in an attempt to improve the quality of the solutions, the cut related to the bound constraint is updated
and a new weighted analytic center is found. Upon failing to find a
feasible integer solution, a second phase is started where cuts
related to the violated feasibility constraints are added. As a last resort, the
algorithm solves a minimum distance problem in a third phase. For all the tested instances, the algorithm finds good quality feasible solutions in the first two phases and the third phase is never called.
Finally, we present a new approach to generate good general branching constraints based on the shape of the polyhedron. Our approach is based on approximating the polyhedron using an inscribed ellipsoid. We use Dikin's ellipsoid which we calculate using the analytic center. We propose to use the disjunction that has a minimum width on the ellipsoid. We use the fact that the width of the ellipsoid in a given direction has a closed form solution in order to formulate a quadratic problem whose optimal solution is a thin direction of the ellipsoid. While solving a quadratic problem at each node of the branch-and-bound tree is impractical, we use a local search heuristic for its solution. Computational testing conducted on hard integer problems from MIPLIB and CORAL showed that the proposed approach outperforms classical branching.
| Identifer | oai:union.ndltd.org:WATERLOO/oai:uwspace.uwaterloo.ca:10012/6105 |
| Date | January 2011 |
| Creators | Naoum-Sawaya, Joe |
| Source Sets | University of Waterloo Electronic Theses Repository |
| Language | English |
| Detected Language | English |
| Type | Thesis or Dissertation |
Page generated in 0.0063 seconds