Branch-and-Bound Methodology Within Algebraic Modelling Systems

摘要

Through the use of application-specific branch-and-bound directives it is possible to find solutions to combinatorial models that would otherwise be difficult or impossible to find by just using generic branch-and-bound techniques within the framework of mathematical programming. MINTO is an example of a system which offers the possibility to incorporate user-provided directives (written in C) to guide the branch-and-bound search. Its main focus, however, remains on mathematical programming models. The aim of this paper is to present a branch-and-bound methodology for particular combinatorial structures to be embedded inside an algebraic modeling language. One advantage is the increased scope of application. Another advantage is that directives are easier implemented at the modeling level at the programming level.