To launch the New Year, the Optimal Decision Analytics Blog is featuring a series of articles about research topics that are ripe for exploration, whether in the form of projects by seasoned researchers or in studies carried out as doctoral thesis investigations.
The articles will cut across the areas of metaheuristics and classical optimization, running a gamut of topics of interest to researchers and practitioners alike.
Subjects to be covered will range from mixed integer programming to data mining, with excursions into simulation, risk analysis, stochastic & nonlinear programming and black box optimization.
You are invited to respond with comments not only about the topic currently posted, but also about additional topics you would like to see covered.
The first topic examined falls in the area of metaheuristic strategies that may be used to enhance mixed integer programming methods.
Metaheuristic Multi-start Strategies for Mixed Integer Programming
Classical branch-and-bound and branch-and-cut strategies for mixed integer programming (MIP) have an intriguing relationship to multi-start (M-S) procedures that have emerged in metaheuristic optimization. Successes of metaheuristic strategies in a variety of settings have been attracting a growing number of researchers to give attention to these approaches. It is by now well known that, although they do not guarantee optimality, metaheuristics have found an important place in the quest to obtain high quality solutions for problems where certifiably optimal solutions are hard to come by, and where classical optimization methods have chalked up a less-than-spectacular performance record. Within the metaheuristic domain, multi-start strategies have carved out a well-earned place both as stand-alone methods and as supporting procedures to enhance the performance of other metaheuristics. The conspicuous relationship of mult-start methods to “forward phases” of tree search strategies embedded in classical MIP branch-and-bound and branch-and-cut methods stimulates the speculation that perhaps some of the multi-start ideas might be fruitfully transplanted to the MIP area.
Background and Suggestions for Combining Multi-Start and MIP Methods
There has been no dearth of attempts to marry metaheuristic optimization with classical optimization – in fact, the term “matheuristics” has been coined to give recognition to the burgeoning efforts in this realm – but so far relatively little attention has been devoted to broaching the domain of MIP problems formulated in their abstract form. For MIP problems that don’t readily lend themselves to more specialized formulations recourse almost inevitably is made to procedures that marry state-of-the-art linear programming (LP) solvers with tree search and cutting plane methods. Consequently, commercial MIP solvers have grown up hand-in-hand with the development of the leading LP solvers. Meanwhile, only scattered efforts have been made to embed metaheuristic strategies within such MIP solution machinery, focusing chiefly on isolated special cases. This is not surprising, given that metaheuristics perform best for problems exhibiting special structures that can be exploited by flexible and ingenious artifices, as opposed to problems that we only know how to express in abstract mathematical formulations.
Still, it’s hard to miss the fact that the tree search framework underlying branch-and-bound and branch-and-cut methods is well suited to be addressed by multi-start strategies developed in the metaheuristic domain. The formal classical approaches and the metaheuristic approaches both contend with the same challenge of executing sequential decision steps that build a solution in stages (performed in the MIP setting by progressively narrowing bounds imposed on integer variables). Both types of approaches interrupt the forward progression when a fully realized candidate solution is obtained, or when no feasible continuations exist, and then pick up again at some point in a previous sequence of steps. (Most M-S methods re-start from scratch after concluding their forward progression, but others – based on strategic oscillation – dismantle some subset of decisions underlying a current construction as a prelude to rebuilding.)
Consequently, the same schemes that have been invented to enable state-of-the-art LP solvers to be joined with decision strategies for MIP problems are susceptible to being used by M-S procedures. In addition, commercial MIP packages are becoming increasingly accessible to researchers who want to experiment with alternative decision strategies, thus paving the way for linking multi-start methods with these packages
Implementation challenges
The greatest limitation to implementing more general M-S procedures within the setting of current MIP solvers lies in the fact that tools have not been created for these solvers with an eye to flexibly dismantling solutions. This limitation most strongly affects the implementation of strategic oscillation approaches given that current solvers focus chiefly on decisions that involve forward steps, rather than considering the possibility of making “backward step” decisions that would modify sequences previously established in the forward direction. Consequently, M-S strategies for MIP must largely be confined at present to those that generate a forward decision sequence from scratch. Nevertheless, this still leaves room for innovative ideas and implementations that can be expanded as the “hooks” to operations within commercial solvers are made more comprehensive.
As in current multi-start procedures that invoke improvement methods to take over when the construction phase is completed, these MIP multi-start methods could make provision for a commercial MIP solver to continue exploration for a period after the M-S approach reaches the end of a forward pass (whether or not feasibility has been achieved).
But commercial MIP solvers are not the only option for providing the machinery for such a marriage. Conceivably, a good computer programmer might be able to “get inside” an open source MIP solver to create routines for an M-S method, making it possible to produce strategies that are more versatile than those produced by joining such a method with a commercial MIP code. The resulting software would not be able to compete in efficiency with the commercial solvers, but could be the basis for a proof-of-concept study that examines relative merits of different ways of combining multi-start strategies with current MIP methods.
Issues for Consideration
Several interesting questions arise when contemplating a marriage of multi-start and MIP methods:
- Can an M-S method prove useful in the role of providing a preliminary solution stage to accelerate the convergence of a standard MIP solver?
- To what extent should an MIP solver be employed at the conclusion of a pass of an M-S method to search for enhanced solutions before launching a new pass?
- Can an M-S solver be useful by itself as a means of obtaining good solutions (without seeking to establish convergence to optimality)?
- What types of memory can be useful for M-S strategies associated with memory-based methods such as strategic oscillation and tabu search?
Another interesting question involves the use of metaheuristic improvement approaches to supplement a multi-start procedure for MIP optimization. For example, studies of the GRASP multi-start approach have disclosed that significant improvements often result when the procedure is supplemented by path relinking. It would be an intriguing challenge to see whether current MIP machinery is sufficiently malleable to enable such a supplementary method to be implemented efficiently.
Additional crucial issues will be to determine if the branch-evaluation rules used by an MIP solver can be made available to allow a user to rank different branching decisions for an M-S method like GRASP, or to weight such decisions probabilistically for a method like probabilistic TS. In the case where different types of branch-evaluations are made available, another intriguing challenge will be to devise processes for integrating these evaluations (e.g., by some variant of a “voting” process) as a basis for choosing branches. In some types of M-S approaches – particularly those incorporating strategic oscillation or tabu search – it will be essential to differentiate branches that are forced (conditional upon branches previously made on a given path of a tree) and those that are freely selected. In any event, an initial study need not examine all of these issues. Focusing on a few key questions can yield valuable preliminary insights and set the stage for an ongoing stream of research investigations.
Point of Departure
The following references are suggested as basis for developing ideas that may provide a useful point of departure.
F. Glover (2000) "Multi-Start and Strategic Oscillation Methods - Principles to Exploit Adaptive Memory," Interfaces in Computer Science and Operations Research, M. Laguna and J.L. Gonzales Velarde, Eds., Kluwer, pp. 1-24.
M. Resende, C. Ribeiro, F. Glover and R. Marti (2010) “Scatter Search and Path Relinking: Fundamentals, Advances and Applications,” Handbook of Metaheuristics, M. Gendreau and J-Y. Potvin, eds., Kluwer.
M.G.C. Resende and C.C. Ribeiro (2010) “GRASP: Greedy Randomized Adaptive Search Procedures,” Search Methodologies, 2nd edition, E. Burke and G. Kendall (Eds.), Springer.
F. Glover and J-K. Hao (2011) “The Case for Strategic Oscillation,” Annals of Operations Research, Vol. 183, No. 1, pp. 163-173.
P. Festa and M.G.C. Resende (2011) “Hybridizations of GRASP with path-relinking,” Hybrid Metaheuristics, E-G. Talbi, Editor, Studies in Computational Intelligence, vol. 434, pp. 135-155, 2013, Springer
R. Martí, M.G.C. Resende, and C.C. Ribeiro (2012) “Multi-start methods for combinatorial optimization
Additional sources of useful information can be found in the references cited in these articles.