Recovery of primal solutions from dual subgradient methods for mixed binary linear programming; a branch-and-bound approach

Abstract

The main objective of this thesis is to implement and evaluate a Lagrangian heuristic and a branch-and-bound algorithm for solving a class of mathematical optimization problems called mixed binary linear programs. The tests are performed on two different types of mixed binary linear programs: the set covering problem and the (uncapacitated as well as capacitated) facility location problem. The purpose is to investigate a concept rather than trying to achieve good runtime performance. The concept involves ergodic iterates, which are convex combinations of all Lagrangian subproblem solutions found so far. The ergodic iterates are constructed from the Lagrangian subproblem solutions with different convexity weight rules. In the Lagrangian heuristic, Lagrangian relaxation is utilized to obtain lower bounds on the optimal objective value and the ergodic iterates are used to create feasible solutions, and whence, to obtain upper bounds on the optimal objective value. The branch-and-bound algorithm uses the Lagrangian heuristic in each node and the ergodic iterates for branching decisions. The investigated concept of this thesis is ergodic iterates constructed by different convexity weight rules, where the different rules are to weigh the Lagrangian subproblem solutions as follows: put all the weight on the last one (the traditional Lagrangian heuristic), use equal weights on all, and put a successively higher weight on the later ones. The result obtained shows that a convexity weight rule that puts more weight on later Lagrangian subproblem solutions, without putting all the weight on the last one, is preferable.