Improving set partitioning problem solutions by zooming around an improving direction

Abdelouahab Zaghrouti (), Issmail El Hallaoui () and François Soumis ()
Additional contact information
Abdelouahab Zaghrouti: Polytechnique Montréal and GERAD
Issmail El Hallaoui: Polytechnique Montréal and GERAD
François Soumis: Polytechnique Montréal and GERAD

Annals of Operations Research, 2020, vol. 284, issue 2, No 9, 645-671

Abstract: Abstract In this paper, we introduce a general framework for vector space decompositions that decompose the set partitioning problem into a reduced problem, defined in the vector subspace generated by the columns corresponding to nonzero variables in the current integer solution, and a complementary problem, defined in the complementary vector subspace. We show that the integral simplex using decomposition algorithm (ISUD) developed in Zaghrouti et al. (Oper Res 62:435–449, 2014. https://doi.org/10.1287/opre.2013.1247) uses a particular decomposition, in which integrality is handled mainly in the complementary problem, to find a sequence of integer solutions with decreasing objective values leading to an optimal solution. We introduce a new algorithm using a new dynamic decomposition where integrality is handled only in the reduced problem, and the complementary problem is only used to provide descent directions, needed to update the decomposition. The new algorithm improves, at each iteration, the current integer solution by solving a reduced problem very small compared the original problem, that we define by zooming around the descent direction (provided by the complementary problem). This zooming algorithm is superior than ISUD on set partitioning instances from the transportation industry. It rapidly reaches optimal or near-optimal solutions for all instances including those considered very difficult for both ISUD and CPLEX.

Keywords: Integral simplex; Decomposition methods; Integer programming; Set partitioning problems; Vehicle and crew scheduling (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10479-018-2868-1 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:284:y:2020:i:2:d:10.1007_s10479-018-2868-1

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1007/s10479-018-2868-1

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().