PBAPSYST: Parallel Branch And Price SYSTem
A mixed integer program (MIP) is the problem of maximizing a linear function over linear constraints subject to integrality restrictions on some or all of the variables. A rich class of real world problems can be modeled as MIPs, so many advanced techniques have been developed for their solution. From a computational standpoint, some of the most effective algorithms are linear programming based branch and bound algorithms. It is these algorithms on which we will focus.
We study how to combine the power of linear programming based techniques for solving MIP with the power of parallel computing. In a wide range of scientific fields, the introduction of parallel computers consisting of many microprocessers has made possible the solutions of problems impossible to consider solving on a single processor. The field of Optimization should be no exception. This is a computationally oriented thesis, in which we build three separate parallel optimization codes. Each code solves a specific type of MIP and investigates issues related to the parallelization of sophisticated solution techniques for this particular problem type. The most interesting parallelization issues occur when the processors must communicate by message passing, so we focus our algorithm design for these architectures.
The first code developed (PARINO) is a branch-and-cut code for solving general MIPs. Many advanced techniques for solving such problems, such as reduced cost fixing, primal heuristics, pseudocosts, and cutting planes are incorporated in the code. The main issue addressed is to how to share among the processors globally useful information which helps guide the search for the optimal solution. There is a tradeoff between complete sharing of information between processors, requiring potentially significant overhead, and little sharing of information, where potentially valuable information is lost. For general MIP, the two main areas for which this topic must be addressed are cut management and branching. We suggest a dynamic scheme, where choices about cut sharing or pseudocost sharing are based on a variety of factors such as the type of cut generated, the time required to generate a cut or pseudocost, and the speed of the underlying communication network. We give evidence that supports our choices when addressing these issues and show impressive computational results for our particular computer architectures.
A research report on this work should be available soon. I made this statement some time ago, and yet there is still no research report. Funny how that works...
Thus, I am making my thesis available online. There are a few other
things in it besides PARINO that have since appeared in research
reports, so you probably want to skip those chapters. Click
HERE for a Postscipt
version of my thesis.
The second code (PSPS) is specialized to solve the Set Partitioning Problem (SPP). The SPP is a MIP with wide applicability in areas such as scheduling and routing. A variety of techniques have been developed in order to exploit the problem structure of SPP resulting in the ability to solve much larger instances of SPP than of MIP. Our implementation is carefully designed to exploit parallelism to greatest advantage in advanced techniques like preprocessing and probing, primal heuristics, and cut generation. In addition, a primal-dual subproblem algorithm is used for solving the linear programming relaxation. This method outperforms standard simplex algorithms, reduces memory requirements, and breaks the linear programming solution process into natural phases from which we can exploit information to find good solutions on the various processors. Using all these techniques allows us to obtain solutions to extremely large problems in a reasonable amount of computing time.
I gave an overview talk on this work at the INFORMS meeting
in Montreal. Click
HERE for a Postscipt
version of the slides.
The report is published. Click
HERE for a Postscipt
version of the technical report.
PBAPSYST: Parallel Branch And Price SYSTem
The final code is a parallel branch-and-price system. Often, a very tight relaxation to MIP is obtained by a linear formulation that has an enormous number of variables. To solve the LP relaxation of such problems, a technique called column generation is used. Branch- and-price refers to the technique of combining linear programming based branch and bound with column generation. We give emperical and theoretical evidence on the importance of sharing generated columns among the processors. As a case study, we show how to successfully use our parallel branch-and-price system to solve the Generalized Assignment Problem.
I gave a preliminary talk on this work at the INFORMS meeting
in Cincinnati. Mostly, I talked about the importance of sharing the
generated columns among the processors.
Click
HERE for a Postscipt
version of the slides.
I have done a little bit more work on this recently, and recently gave a talk at DO99 . For a postscript copy of the slides from that talk, click HERE.