pith. sign in

arxiv: 1907.09242 · v1 · pith:7ZJASOFVnew · submitted 2019-07-22 · 💻 cs.DM · cs.DS

Robust Approach to Restricted Items Selection Problem

Maciej Drwal This is my paper

Pith reviewed 2026-05-24 17:55 UTC · model grok-4.3

classification 💻 cs.DM cs.DS
keywords robust optimizationitems selectioncut generationpolynomial hierarchyinterval uncertaintycombinatorial optimizationregret minimizationNP-hardness
0
0 comments X

The pith

The robust version of constrained items selection under interval uncertainty is hard for the second level of the polynomial hierarchy and is solved exactly by cut generation.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper examines the task of choosing one item from each set in a family while obeying restrictions on which items may be combined together. It first establishes that the deterministic version of this selection problem is NP-hard in general, although certain special cases admit polynomial-time solutions. It then turns to the robust version, where each parameter is known only to lie in an interval and the objective is to minimize the maximum regret relative to the best possible choice for each realized scenario. The robust problem is shown to be hard for the second level of the polynomial hierarchy. An exact algorithm that solves the resulting min-max regret model by iteratively generating cuts is presented and tested on instances.

Core claim

We prove NP-hardness of the deterministic restricted items selection problem and identify polynomially solvable special cases. For the robust version that minimizes maximum regret under independent interval uncertainty on the parameters, we establish hardness for the second level of the polynomial-time hierarchy. We develop an exact algorithm based on cut generation and report computational results.

What carries the argument

A cut-generation procedure that iteratively adds valid inequalities to an integer programming formulation of the min-max regret problem.

If this is right

  • The deterministic problem remains NP-hard except in identified special cases that admit direct polynomial algorithms.
  • Any exact method for the robust problem must in the worst case solve a problem complete for the second level of the polynomial hierarchy.
  • Cut generation produces a correct optimal solution for every finite instance of the robust problem.
  • The same algorithmic template can be applied to other robust combinatorial selection tasks that admit an integer-programming formulation.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • Practical implementations will need to manage the bilevel structure implicit in the regret objective.
  • The hardness result indicates that heuristic or approximation methods may be necessary for very large instances even when the cut-generation routine is available.
  • Relaxing the independence assumption on the intervals could alter both the complexity and the form of the cutting planes.

Load-bearing premise

Uncertainty is captured exactly by independent interval bounds on each parameter and regret is always measured against the optimal solution for the realized scenario.

What would settle it

A concrete family of instances on which the cut-generation algorithm returns a solution whose regret is strictly larger than the true minimum possible regret.

Figures

Figures reproduced from arXiv: 1907.09242 by Maciej Drwal.

Figure 1
Figure 1. Figure 1: Example of flow network illustrating case 2) of Theo [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: Illustration for Example 2, showing the construct [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
read the original 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.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

0 major / 2 minor

Summary. The manuscript studies the restricted items selection problem of choosing representatives from a family of sets subject to combination constraints. It proves NP-hardness of the deterministic version, identifies polynomially solvable special cases, establishes Σ₂ᵖ-hardness of the robust regret-minimization version under interval uncertainty, and presents an exact cut-generation algorithm together with computational experiments.

Significance. If the hardness reductions and cut-generation correctness proofs hold, the work contributes a complexity classification and a practical exact method for a class of robust combinatorial selection problems; the computational experiments provide initial evidence of tractability on moderate instances.

minor comments (2)
  1. [Abstract] Abstract states that computational experiments are presented, yet supplies no information on instance sizes, generation method, performance metrics, or baseline comparisons; a dedicated experimental section should include these details with tables or figures.
  2. [Model formulation (presumed §2)] The regret definition with respect to the scenario-optimal solution is standard but should be stated explicitly with notation in the model section to avoid ambiguity when the uncertainty set is an independent interval product.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of the manuscript, the recognition of its contributions to complexity classification and the exact algorithm for the robust problem, and the recommendation of minor revision. No major comments were raised in the report.

Circularity Check

0 steps flagged

No significant circularity

full rationale

The paper establishes NP-hardness for the deterministic restricted items selection problem and Σ₂ᵖ-hardness for its robust counterpart under interval uncertainty, then presents a cut-generation algorithm for the latter. These results rest on standard reductions from known hard problems and established integer-programming techniques; no parameter fitting, self-defined quantities, or load-bearing self-citations appear in the derivation chain. The modeling assumptions (interval bounds and regret) are stated explicitly as inputs rather than derived from the algorithm or hardness statements themselves.

Axiom & Free-Parameter Ledger

0 free parameters · 2 axioms · 0 invented entities

The paper relies on standard complexity-theoretic assumptions (NP and Sigma_2^p hardness reductions) and the modeling choice of interval uncertainty; no free parameters or invented entities are introduced in the abstract.

axioms (2)
  • standard math Standard assumptions of complexity theory suffice to establish NP-hardness and hardness for the second level of the polynomial hierarchy via reduction.
    The abstract states these hardness results without detailing the reductions.
  • domain assumption Interval uncertainty model and max-regret objective accurately represent the robust version of the problem.
    The robust formulation is defined with respect to interval parameters and regret.

pith-pipeline@v0.9.0 · 5607 in / 1298 out tokens · 29767 ms · 2026-05-24T17:55:40.820718+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Reference graph

Works this paper leans on

23 extracted references · 23 canonical work pages

  1. [1]

    Prentice Hall (1988)

    Ahuja, R.K., Magnanti, T.L., Orlin, J.B.: Network flows. Prentice Hall (1988)

    work page 1988

  2. [2]

    Operations Research Letters 33(6), 634–640 (2005)

    Aissi, H., Bazgan, C., Vanderpooten, D.: Complexity of t he min–max and min–max regret assignment problems. Operations Research Letters 33(6), 634–640 (2005)

    work page 2005

  3. [3]

    European Jour nal of Operational Research 197(2), 427–438 (2009)

    Aissi, H., Bazgan, C., Vanderpooten, D.: Min–max and min –max regret versions of com- binatorial optimization problems: A survey. European Jour nal of Operational Research 197(2), 427–438 (2009)

    work page 2009

  4. [4]

    Mathematical Programming 90(2), 263–272 (2001)

    A verbakh, I.: On the complexity of a class of combinatori al optimization problems with uncertainty. Mathematical Programming 90(2), 263–272 (2001)

    work page 2001

  5. [5]

    Discrete Applied Mathematics 138(3), 289–301 (2004)

    A verbakh, I., Lebedev, V.: Interval data minmax regret n etwork optimization problems. Discrete Applied Mathematics 138(3), 289–301 (2004)

    work page 2004

  6. [6]

    Mathematical programming 98(1-3), 49–71 (2003)

    Bertsimas, D., Sim, M.: Robust discrete optimization an d network flows. Mathematical programming 98(1-3), 49–71 (2003)

    work page 2003

  7. [7]

    Mathematical Programming 100(2), 345–353 (2004)

    Conde, E.: An improved algorithm for selecting p items wi th uncertain returns according to the minmax-regret criterion. Mathematical Programming 100(2), 345–353 (2004)

    work page 2004

  8. [8]

    4OR 11(3), 249–252 (2013)

    Deineko, V.G., Woeginger, G.J.: Complexity and in-appr oximability of a selection problem in robust optimization. 4OR 11(3), 249–252 (2013)

    work page 2013

  9. [9]

    4OR 10(2), 181–192 (2012)

    Dolgui, A., Kovalev, S.: Min–max and min–max (relative) regret approaches to representa- tives selection problem. 4OR 10(2), 181–192 (2012)

    work page 2012

  10. [10]

    Computers & Operations Research 91, 13–20 (2018) 12

    Drwal, M.: Robust scheduling to minimize the weighted n umber of late jobs with interval due-date uncertainty. Computers & Operations Research 91, 13–20 (2018) 12

    work page 2018

  11. [11]

    Opera tions Research Letters 44(3) (2016)

    Drwal, M., Rischke, R.: Complexity of interval minmax r egret scheduling on parallel iden- tical machines with total completion time criterion. Opera tions Research Letters 44(3) (2016)

    work page 2016

  12. [12]

    Garey, M., Johnson, D.: Computers and Intractability: A Guide to the Theory of NP- completeness. W.H. Freeman (2002)

    work page 2002

  13. [13]

    In: Algorithm engineering, pp

    Goerigk, M., Schöbel, A.: Algorithm engineering in rob ust optimization. In: Algorithm engineering, pp. 245–279. Springer (2016)

    work page 2016

  14. [14]

    Journal of Manufacturing Systems 31(2), 224 – 231 (2012)

    Jahromi, M., Tavakkoli-Moghaddam, R.: A novel 0-1 line ar integer programming model for dynamic machine-tool selection and operation allocation i n a flexible manufacturing system. Journal of Manufacturing Systems 31(2), 224 – 231 (2012)

    work page 2012

  15. [15]

    Springer (1994)

    Kall, P., Wallace, S.W., Kall, P.: Stochastic programm ing. Springer (1994)

    work page 1994

  16. [16]

    Springer (2008)

    Kasperski, A.: Discrete optimization with interval da ta: minmax regret and fuzzy approach. Springer (2008)

    work page 2008

  17. [17]

    Operations Research Letters 43(1), 16–19 (2015)

    Kasperski, A., Kurpisz, A., Zieliński, P.: Approximab ility of the robust representatives selection problem. Operations Research Letters 43(1), 16–19 (2015)

    work page 2015

  18. [18]

    Sequencing and Schedul- ing with Inaccurate Data

    Kasperski, A., Zielinski, P.: Minmax (regret) schedul ing problems. Sequencing and Schedul- ing with Inaccurate Data. Y. Sotskov F. Werner (eds.) pp. 159 –210 (2014)

    work page 2014

  19. [19]

    Computers & I ndustrial Engineering 45(1), 61 – 73 (2003)

    Lee, C.S., Kim, S.S., Choi, J.S.: Operation sequence an d tool selection in flexible manufac- turing systems under dynamic tool allocation. Computers & I ndustrial Engineering 45(1), 61 – 73 (2003)

    work page 2003

  20. [20]

    Computers & Operations Research 38(8), 1153–1163 (2011)

    Pereira, J., A verbakh, I.: Exact and heuristic algorit hms for the interval data robust assign- ment problem. Computers & Operations Research 38(8), 1153–1163 (2011)

    work page 2011

  21. [21]

    European Journal of Operational Research 200(3), 629–638 (2010)

    Roy, B.: Robustness in operational research and decisi on aiding: A multi-faceted issue. European Journal of Operational Research 200(3), 629–638 (2010)

    work page 2010

  22. [22]

    John Wiley & Sons (1998)

    Schrijver, A.: Theory of linear and integer programmin g. John Wiley & Sons (1998)

    work page 1998

  23. [23]

    The oretical Computer Science 3(1), 1–22 (1976) 13

    Stockmeyer, L.J.: The polynomial-time hierarchy. The oretical Computer Science 3(1), 1–22 (1976) 13

    work page 1976