Robust approach to restricted items selection problem

DOI10.1007/S11590-020-01626-8zbMATH Open1466.90063arXiv1907.09242OpenAlexW3048961104MaRDI QIDQ828685FDOQ828685

Authors: Maciej Drwal 

Publication date: 5 May 2021

Published in: Optimization Letters (Search for Journal in Brave)

Abstract: We consider the robust version of items selection problem, in which the goal is to choose representatives from a family of sets, preserving constraints on the allowed items' combinations. We prove NP-hardness of the deterministic version, and establish polynomially solvable special cases. Next, we consider the robust version in which we aim at minimizing the maximum regret of the solution under interval parameter uncertainty. We show that this problem is hard for the second level of polynomial-time hierarchy. We develop an exact solution algorithm for the robust problem, based on cut generation, and present the results of computational experiments.

Full work available at URL: https://arxiv.org/abs/1907.09242

Recommendations

• Robust recoverable and two-stage selection problems
• Restricted robust uniform matroid maximization under interval uncertainty
• On recoverable and two-stage robust selection problems with budgeted uncertainty
• Approximating the min-max (regret) selecting items problem
• Complexity and in-approximability of a selection problem in robust optimization

zbMATH Keywords

combinatorial optimizationrobust optimizationmixed integer programming

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Robustness in mathematical programming (90C17)

Cites Work

• Title not available (Why is that?)
• The Price of Robustness
• Robust solutions of uncertain linear programs
• Robust discrete optimization and network flows
• Vertex cover might be hard to approximate to within \(2 - \varepsilon \)
• Title not available (Why is that?)
• Min-max and min-max regret versions of combinatorial optimization problems: A survey
• Interval data minmax regret network optimization problems
• Title not available (Why is that?)
• On the complexity of a class of combinatorial optimization problems with uncertainty
• The polynomial-time hierarchy
• Robustness in operational research and decision aiding: a multi-faceted issue
• The concept of recoverable robustness, linear programming recovery, and railway applications
• Complexity of the min-max and min-max regret assignment problems
• Exact and heuristic algorithms for the interval data robust assignment problem
• An improved algorithm for selecting \(p\) items with uncertain returns according to the minmax-regret criterion
• Discrete optimization with interval data. Minmax regret and fuzzy approach
• Approximability of the robust representatives selection problem
• Min-max and min-max (relative) regret approaches to representatives selection problem
• Complexity and in-approximability of a selection problem in robust optimization
• Robust scheduling to minimize the weighted number of late jobs with interval due-date uncertainty
• Complexity of interval minmax regret scheduling on parallel identical machines with total completion time criterion

Cited In (6)

• A linear time algorithm for the robust recoverable selection problem
• On recoverable and two-stage robust selection problems with budgeted uncertainty
• Approximability of the robust representatives selection problem
• Robust recoverable and two-stage selection problems
• Restricted robust uniform matroid maximization under interval uncertainty
• Robustly assigning unstable items

This page was built for publication: Robust approach to restricted items selection problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q828685)