An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion

Wei Wu (), Manuel Iori (), Silvano Martello () and Mutsunori Yagiura ()
Additional contact information
Wei Wu: Department of Engineering, Shizuoka University, Hamamatsu 432-8561, Japan
Manuel Iori: Department of Sciences and Methods for Engineering, University of Modena and Reggio Emilia, 42122 Reggio Emilia, Italy
Silvano Martello: DEI “Guglielmo Marconi”, Alma Mater Studiorum University of Bologna, 40126 Bologna, Italy
Mutsunori Yagiura: Department of Mathematical Informatics, Nagoya University, Nagoya 464-8601, Japan

INFORMS Journal on Computing, 2022, vol. 34, issue 5, 2523-2539

Abstract: We consider binary integer programming problems with the min-max regret objective function under interval objective coefficients. We propose a heuristic framework, the iterated dual substitution (iDS) algorithm, which iteratively invokes a dual substitution heuristic and excludes from the search space any solution already checked in previous iterations. In iDS, we use a best scenario–based lemma to improve performance. We apply iDS to four typical combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the generalized assignment problem, and the set covering problem. For the multidimensional knapsack problem, we compare the iDS approach with two algorithms widely used for problems with the min-max regret criterion: a fixed-scenario approach, and a branch-and-cut approach. The results of computational experiments on a broad set of benchmark instances show that the proposed iDS approach performs best on most tested instances. For the knapsack problem, the generalized assignment problem, and the set covering problem, we compare iDS with state-of-the-art results. The iDS algorithm successfully updates best-known records for a number of benchmark instances. Summary of Contribution: This paper proposes a heuristic framework for binary integer programming (BIP) problems with the min-max regret objective function under interval objective coefficients. We selected four representative NP-hard combinatorial optimization problems: the knapsack problem, the multidimensional knapsack problem, the set covering problem, and the generalized assignment problem. We show the effectiveness and efficiency of the approach by comparing with state-of-the-art results.

Keywords: combinatorial optimization; min-max regret; heuristics; iterated dual substitution (search for similar items in EconPapers)
Date: 2022
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.1189 (application/pdf)

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:inm:orijoc:v:34:y:2022:i:5:p:2523-2539

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().