(463a) A Branch and Bound Algorithm for the Solution of MIP Models Using Parallel Computing

Sara Zenner and Christos T. Maravelias

Department of Chemical and Biological Engineering, University of Wisconsin – Madison

1415 Engineering Dr., Madison, WI 53706, USA

Exploiting multiple cores in a computer or on a grid of computers can reduce the time required to solve a mixed-integer programming (MIP). The original MIP can be decomposed into several smaller problems, provided that the union of the feasible regions of the subproblems is the same as the feasible region of the original problem so that no solutions are removed. If such a partition is available, then each subproblem can be solved independently on a single core of a computer. However, for many classes of MIP model, simply decomposing and solving using multiple cores is not effective due to the combinatorial nature of these problems. Instead, problem specific information should be used to generate the subproblems (Ferris et al., 2009).

Accordingly, we develop a method for decomposing and solving hard MIP models using domain specific knowlege. The technique for decomposing and solving an MIP is based on a customized branch-and-bound method. We start by dividing the original problem into several problems by fixing or bounding some key integer variables that are chosen using knowledge about the problem. Next, we solve each of these MIP subproblems in parallel for a fixed amount of time. As in the branch-and-bound algorithm, the solutions to these problems provide bounds on the objective value, and problems are pruned when their best bound is worse than the best objective value found so far. Problems that are not solved to optimality and cannot be pruned are dynamically divided further. We use the GAMS grid computing facility to submit multiple problems to solve simultaneously and collect the solutions of solved problems. We also use the GAMS Branch-and-Cut-and-Heuristic (BCH) facility to share integer solutions among all subproblems as soon as they are found, which allows problems to be pruned sooner.

We apply the decomposition method to a chemical production scheduling problem using the discrete-time model of Shah et al. (1993). We consider a process consisting of a series of tasks that produce a set of final products. The optimization decisions include when to carry out each task, which piece of equipment to use, and how much material to process in order to satisfy customer orders at the lowest cost. In each level of the decomposition tree, we fix or bound the total number of batches for a particular task in a particular unit. The LP-relaxation of the original problem gives an estimate of the number of times a job will run in a good solution; in each level of decomposition, we create several subproblems with the number of batches fixed near this value. The order in which the jobs are fixed is based on specific information about the problem. For example, we can estimate how much time each unit is in use from the solution to the LP-relaxation and fix the number of batches in the bottleneck units first, since those will likely be the most difficult to schedule. We explore how different options for the algorithm and for decomposing the problem affect the overall solution time. Using this method, we are able to solve several problems in under 10 minutes that were not solved within an hour either by using a single core or with the CPLEX parallel option.

M.C. Ferris, C.T. Maravelias, and A. Sundaramoorthy, Simultaneous Batching and Scheduling Using Dynamic Decomposition on a Grid, INFORMS Journal on Computing, 2009, 21, 398-410.

N. Shah, C.C. Pantelides, and R.W.H. Sargent, A General Algorithm for short-term scheduling of batch operations--II.  Computational Issues, Computers & Chemical Engineering, 1993, 17, 229-244.