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:	90C11 65K05 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
Acceso en línea:	https://doaj.org/article/6fdea7c1ef364885894c59ddc5e27baa
Etiquetas:	Agregar Etiqueta Sin Etiquetas, Sea el primero en etiquetar este registro!

id	oai:doaj.org-article:6fdea7c1ef364885894c59ddc5e27baa
record_format	dspace
spelling	oai:doaj.org-article:6fdea7c1ef364885894c59ddc5e27baa2021-12-02T05:00:36ZRestrict-and-relax search for 0-1 mixed-integer programs2192-440610.1007/s13675-013-0007-yhttps://doaj.org/article/6fdea7c1ef364885894c59ddc5e27baa2013-05-01T00:00:00Zhttp://www.sciencedirect.com/science/article/pii/S2192440621000186https://doaj.org/toc/2192-4406A 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.Menal GuzelsoyGeorge NemhauserMartin SavelsberghElsevierarticle90C1165K05Applied mathematics. Quantitative methodsT57-57.97Electronic computers. Computer scienceQA75.5-76.95ENEURO Journal on Computational Optimization, Vol 1, Iss 1, Pp 201-218 (2013)
institution	DOAJ
collection	DOAJ
language	EN
topic	90C11 65K05 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95
spellingShingle	90C11 65K05 Applied mathematics. Quantitative methods T57-57.97 Electronic computers. Computer science QA75.5-76.95 Menal Guzelsoy George Nemhauser Martin Savelsbergh Restrict-and-relax search for 0-1 mixed-integer programs
description	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.
format	article
author	Menal Guzelsoy George Nemhauser Martin Savelsbergh
author_facet	Menal Guzelsoy George Nemhauser Martin Savelsbergh
author_sort	Menal Guzelsoy
title	Restrict-and-relax search for 0-1 mixed-integer programs
title_short	Restrict-and-relax search for 0-1 mixed-integer programs
title_full	Restrict-and-relax search for 0-1 mixed-integer programs
title_fullStr	Restrict-and-relax search for 0-1 mixed-integer programs
title_full_unstemmed	Restrict-and-relax search for 0-1 mixed-integer programs
title_sort	restrict-and-relax search for 0-1 mixed-integer programs
publisher	Elsevier
publishDate	2013
url	https://doaj.org/article/6fdea7c1ef364885894c59ddc5e27baa
work_keys_str_mv	AT menalguzelsoy restrictandrelaxsearchfor01mixedintegerprograms AT georgenemhauser restrictandrelaxsearchfor01mixedintegerprograms AT martinsavelsbergh restrictandrelaxsearchfor01mixedintegerprograms
_version_	1718400835103227904

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

Ejemplares similares