Restrict-and-relax search for 0-1 mixed-integer programs

A highly desirable characteristic of methods for solving 0-1 mixed-integer programs is that they should be capable of producing high-quality solutions quickly. We introduce restrict-and-relax search, a branch-and-bound algorithm that explores the solution space not only by fixing variables (restrict...

Descripción completa

Guardado en:
Detalles Bibliográficos
Autores principales: Menal Guzelsoy, George Nemhauser, Martin Savelsbergh
Formato: article
Lenguaje:EN
Publicado: Elsevier 2013
Materias:
Acceso en línea:https://doaj.org/article/6fdea7c1ef364885894c59ddc5e27baa
Etiquetas: Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
Descripción
Sumario:A highly desirable characteristic of methods for solving 0-1 mixed-integer programs is that they should be capable of producing high-quality solutions quickly. We introduce restrict-and-relax search, a branch-and-bound algorithm that explores the solution space not only by fixing variables (restricting), but also by freeing, or unfixing, previously fixed variables (relaxing). Starting from a restricted 0-1 mixed-integer program, the branch-and-bound algorithm may, at any node of the search tree, selectively relax, or unfix, previously fixed variables, restrict, or fix, additional variables, or unfix and fix variables at the same time using dual or structural information (problem-specific information). This process yields a dynamic search that is likely to find high-quality feasible solutions more quickly than a traditional search and that is also capable of proving optimality. A proof-of-concept computational study demonstrates its potential. A straightforward generic implementation in SYMPHONY, an open source solver for mixed-integer programs, is shown to generate high-quality solutions for many MIPLIB instances as well as for large-scale multicommodity fixed-charge network flow instances much more quickly than SYMPHONY itself.