2026-09-22T19:40:36Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:26032 2026-09-05T19:35:03Z ddc:004 open_access

The Dual-Path Fixing Strategy and Its Application to the Set-Covering Problem Yamagishi, Paulo Michel F. Fampa, Marcia Lee, Jon integer programming mixed-integer programming variable fixing reduced-cost fixing strong fixing dual-path fixing set cover 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. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Paulo Michel F. Yamagishi and Marcia Fampa and Jon Lee 2026 Is Part Of LIPIcs, Volume 371, 24th International Symposium on Experimental Algorithms (SEA 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.SEA.2026.28 urn:nbn:de:0030-drops-260329 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.SEA.2026.28 eng https://creativecommons.org/licenses/by/4.0/legalcode