DROPS

Document

DOI: 10.4230/LIPIcs.SEA.2026.28

The Dual-Path Fixing Strategy and Its Application to the Set-Covering Problem

Authors: Paulo Michel F. Yamagishi, Marcia Fampa, and Jon Lee

Published in: LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026)

Abstract

We introduce the dual-path fixing strategy to exploit dual algorithms for solving relaxations of mixed-integer nonlinear-optimization problems. Such dual algorithms are naturally applied in the context of branch-and-bound, and eventual impact on the success of branch-and-bound is our strong motivation. Our fixing strategy aims to be more powerful than the common strategy of fixing variables based on a single dual-feasible solution (e.g., standard reduced-cost fixing for mixed-integer linear optimization), but to be much faster than "strong fixing", essentially requiring no more time than that of the dual algorithm that we exploit. We have successfully tested our ideas on mixed-integer linear-optimization set-covering instances from the literature, in the context of the dual-simplex method applied to the continuous relaxations.

Cite as

Paulo Michel F. Yamagishi, Marcia Fampa, and Jon Lee. The Dual-Path Fixing Strategy and Its Application to the Set-Covering Problem. In 24th International Symposium on Experimental Algorithms (SEA 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 371, pp. 28:1-28:18, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{yamagishi_et_al:LIPIcs.SEA.2026.28,
  author =	{Yamagishi, Paulo Michel F. and Fampa, Marcia and Lee, Jon},
  title =	{{The Dual-Path Fixing Strategy and Its Application to the Set-Covering Problem}},
  booktitle =	{24th International Symposium on Experimental Algorithms (SEA 2026)},
  pages =	{28:1--28:18},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-422-2},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{371},
  editor =	{Aum\"{u}ller, Martin and Finocchi, Irene},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.28},
  URN =		{urn:nbn:de:0030-drops-260329},
  doi =		{10.4230/LIPIcs.SEA.2026.28},
  annote =	{Keywords: integer programming, mixed-integer programming, variable fixing, reduced-cost fixing, strong fixing, dual-path fixing, set cover}
}

Search Results

Documents authored by Yamagishi, Paulo Michel F.

The Dual-Path Fixing Strategy and Its Application to the Set-Covering Problem

Abstract

Cite as

Thanks for your feedback!

Could not send message