Heuristic and Exact Algorithms for the Interval Min–Max Regret Knapsack Problem

DOI10.1287/ijoc.2014.0632zbMath1329.90119OpenAlexW2142448022WikidataQ57659049 ScholiaQ57659049MaRDI QIDQ3466782

Manuel Iori, Silvano Martello, Fabio Furini, Mutsunori Yagiura

Publication date: 25 January 2016

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1287/ijoc.2014.0632

zbMATH Keywords

Lagrangian relaxationlocal searchknapsack problembranch and cutrobust optimizationinterval \(\min\)-\(\max\) regret

Mathematics Subject Classification ID

Minimax problems in mathematical programming (90C47) Combinatorial optimization (90C27)

Related Items

An Iterated Dual Substitution Approach for Binary Integer Programming Problems Under the Min-Max Regret Criterion, Knapsack problems -- an overview of recent advances. I: Single knapsack problems, A linear programming based heuristic framework for min-max regret combinatorial optimization problems with interval costs, The robust (minmax regret) assembly line worker assignment and balancing problem, Robust min-max regret covering problems, An Exact Algorithm for Large-Scale Continuous Nonlinear Resource Allocation Problems with Minimax Regret Objectives, Solution techniques for bi-level knapsack problems, Complexity results for common due date scheduling problems with interval data and minmax regret criterion, Combinatorial optimization problems with balanced regret, An exact approach for the bilevel knapsack problem with interdiction constraints and extensions, Fix-and-optimize metaheuristics for minmax regret binary integer programming problems under interval uncertainty, A branch and price algorithm for EOS constellation imaging and downloading integrated scheduling problem, Formulation and algorithms for the robust maximal covering location problem, A dynamic reformulation heuristic for generalized interdiction problems, A branch-and-cut algorithm for the edge interdiction clique problem, Robust min-max regret scheduling to minimize the weighted number of late jobs with interval processing times, Robust Postdonation Blood Screening Under Prevalence Rate Uncertainty, On the exact separation of cover inequalities of maximum-depth

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Unnamed Item
• The robust set covering problem with interval data
• General approximation schemes for min-max (regret) versions of some (pseudo-)polynomial problems
• Pinpointing the complexity of the interval min-max regret knapsack problem
• Exact and heuristic algorithms for the interval data robust assignment problem
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Partitioning procedures for solving mixed-variables programming problems
• Robust discrete optimization and network flows
• Robust solutions of linear programming problems contaminated with uncertain data
• The robust shortest path problem with interval data via Benders decomposition
• Dynamic Programming and Strong Bounds for the 0-1 Knapsack Problem
• Energy crop supply in France: a min-max regret approach
• The Price of Robustness
• Lectures on Stochastic Programming
• On the Max-Min 0-1 Knapsack Problem with Robust Optimization Applications
• Minmax regret combinatorial optimization problems: an Algorithmic Perspective
• On the complexity of a class of combinatorial optimization problems with uncertainty