pith. sign in

arxiv: 1907.03162 · v1 · pith:VB7JU7M7new · submitted 2019-07-06 · 🧮 math.OC

Combinatorial separation algorithms for the continuous knapsack polyhedra with divisible capacities

Wei-Kun Chen , Yu-Hong Dai This is my paper

Pith reviewed 2026-05-25 01:27 UTC · model grok-4.3

classification 🧮 math.OC
keywords continuous knapsack polyhedronpartition inequalitiesseparation algorithmmixed integer programmingdivisible capacitiescombinatorial algorithmconvex hull
0
0 comments X

The pith

Combinatorial separation algorithms run in O(nm + m log m) time for the continuous knapsack polyhedra with divisible capacities.

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

The paper develops separation routines for two families of polyhedra that arise when modeling mixed-integer programs with a single knapsack constraint. It shows that the >=-partition inequalities can be separated combinatorially for the continuous >=-knapsack polyhedron in O(nm + m log m) time. For the <=-knapsack polyhedron it introduces complemented partition inequalities that dominate the original <=-partition inequalities and give a complete linear description of the convex hull, with the same polynomial separation complexity. The results supply explicit, efficient cutting-plane generators when the integer coefficients divide the capacity.

Core claim

For the continuous >=-knapsack polyhedron the >=-partition inequalities admit a combinatorial separation algorithm of complexity O(nm + m log m). For the continuous <=-knapsack polyhedron the complemented partition inequalities dominate the <=-partition inequalities and completely describe the polyhedron; the same combinatorial procedure separates this new family in O(nm + m log m) time.

What carries the argument

The >=-partition inequalities together with the complemented partition inequalities, which enforce the knapsack constraint by considering ordered partitions of the integer variables according to their divisible coefficients.

If this is right

  • Separation for these polyhedra no longer requires solving an auxiliary linear program.
  • Branch-and-cut solvers can generate the inequalities directly from the variable coefficients and bounds.
  • The <=-knapsack convex hull can be optimized exactly by adding only the complemented inequalities.
  • The same algorithmic skeleton applies to both the >= and <= directions once the complemented form is used.

Where Pith is reading between the lines

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

  • Specialized separators of this type could be embedded in commercial MIP solvers for problems whose capacities happen to be divisible.
  • The dominance of the complemented form over the original inequalities suggests a template for strengthening other partition-based cuts.
  • When coefficients fail to be divisible the routines lose their guarantee, indicating the need for alternative inequality families or general-purpose oracles.
  • The O(nm + m log m) bound is low enough that the method remains attractive even when called repeatedly inside a cutting-plane loop.

Load-bearing premise

The coefficients of the integer variables are integers that divide the right-hand side capacity.

What would settle it

A fractional point that satisfies every complemented partition inequality yet lies strictly outside the convex hull of the continuous <=-knapsack set would falsify the claim of a complete description.

read the original abstract

It is important to design separation algorithms of low computational complexity in mixed integer programming. We study the separation problems of the two continuous knapsack polyhedra with divisible capacities. The two polyhedra are the convex hulls of the sets which consist of $ n $ nonnegative integer variables, one unbounded continuous, $ m $ bounded continuous variables, and one linear constraint in either $ \geq $ or $ \leq $ form where the coefficients of integer variables are integer and divisible. Wolsey and Yaman (Math Program 156: 1--20, 2016) have shown that the polyhedra can be described by adding the two closely related families of partition inequalities. However, no combinatorial separation algorithm is known yet for the polyhedra. In this paper, for each polyhedron, we provide a combinatorial separation algorithm with the complexity of $ \mathcal{O}(nm+m\log m ) $. In particular, we solve the separation problem for the continuous $ \geq $-knapsack polyhedron by presenting a polynomial-time separation algorithm for the family of $ \geq $-partition inequalities. For the continuous $ \leq $-knapsack polyhedron, we derive the complemented partition inequalities, which dominate the $ \leq $-partition inequalities. The continuous $ \leq $-knapsack polyhedron is completely described with the addition of the proposed inequalities. We again show that the family of the proposed inequalities can be separated in polynomial time.

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 develops combinatorial separation algorithms of complexity O(nm + m log m) for the continuous >=-knapsack and <=-knapsack polyhedra whose integer-variable coefficients are integers and divisible. Building on the partition-inequality description of Wolsey and Yaman (2016), the authors give an explicit polynomial-time separation routine for the >=-partition inequalities; for the <= case they introduce a new family of complemented partition inequalities that dominate the original <=-partition inequalities, prove that these inequalities together with the earlier description yield a complete polyhedral characterization, and supply a matching O(nm + m log m) separation algorithm.

Significance. The contribution supplies the first combinatorial, polynomial-time separation procedures for these two families of polyhedra. Because the algorithms are combinatorial rather than LP-based and because the complemented inequalities strictly strengthen the known description for the <=-knapsack case, the results make the theoretical characterizations immediately usable inside branch-and-cut frameworks for mixed-integer programs containing continuous knapsack structures with divisible capacities.

minor comments (2)
  1. [§2] §2, Definition 1: the precise statement of the divisibility condition on the integer coefficients should be repeated verbatim when the two polyhedra are introduced, to avoid any ambiguity about the scope of the subsequent theorems.
  2. The running-time analysis in the separation procedures repeatedly invokes a sorting step of size m; a brief remark on whether this step can be amortized across multiple separation calls would be helpful for implementers.

Simulated Author's Rebuttal

0 responses · 0 unresolved

We thank the referee for the positive assessment of our manuscript and the recommendation to accept. The report contains no major comments requiring a point-by-point reply.

Circularity Check

0 steps flagged

No significant circularity identified

full rationale

The paper explicitly cites Wolsey and Yaman (2016) for the polyhedral description of both continuous knapsack polyhedra under the stated divisible-coefficients hypothesis, then supplies independent combinatorial separation routines of complexity O(nm + m log m) together with a new family of complemented partition inequalities shown to dominate the <=-partition inequalities. No equation or derivation step reduces the claimed algorithms or completeness result to a fitted parameter, self-definition, or self-citation chain; the divisibility assumption is stated at the outset and the separation procedures are derived directly from the cited description without circular reduction.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the prior polyhedral description by Wolsey and Yaman together with the divisibility assumption on coefficients; no free parameters or invented entities appear.

axioms (1)
  • domain assumption The polyhedra are the convex hulls of the sets consisting of n nonnegative integer variables, one unbounded continuous variable, m bounded continuous variables and one linear constraint with divisible integer coefficients.
    This defines the objects whose separation problems are solved.

pith-pipeline@v0.9.0 · 5783 in / 1367 out tokens · 33864 ms · 2026-05-25T01:27:03.687130+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

18 extracted references · 18 canonical work pages

  1. [1]

    Mathematical Programming 123(2):315–338

    Atamt¨ urk A, G¨ unl¨ uk O (2010) Mingling: Mixed-integer roundin g with bounds. Mathematical Programming 123(2):315–338

    work page 2010

  2. [2]

    Mathematical Prog ramming 92(2):315–333

    Atamt¨ urk A, Rajan D (2002) On splittable and unsplittable flow ca - pacitated network design arc-set polyhedra. Mathematical Prog ramming 92(2):315–333

    work page 2002

  3. [3]

    INFORMS Journal on Computing 8(3) :243– 259

    Bienstock D, G¨ unl¨ uk O (1996) Capacitated network designpo lyhedral structure and computation. INFORMS Journal on Computing 8(3) :243– 259

    work page 1996

  4. [4]

    Discrete Applied Mathematics 85(3):165–192

    Chopra S, Gilboa I, Sastry S (1998) Source sink flows with capacit y in- stallation in batches. Discrete Applied Mathematics 85(3):165–192

    work page 1998

  5. [5]

    Math- ematical Programming 155(1):471–496

    Dash S, G¨ unl¨ uk O, Wolsey LA (2016) The continuous knapsackset. Math- ematical Programming 155(1):471–496

    work page 2016

  6. [6]

    SIAM Journal on Optimization 21(4):1594–1613

    Di Summa M, Wolsey L (2011) Mixing sets linked by bidirected paths. SIAM Journal on Optimization 21(4):1594–1613

    work page 2011

  7. [7]

    Combinatorica 1(2):16 9–197

    Gr¨ otschel M, Lov´ asz L, Schrijver A (1981) The ellipsoid metho d and its consequences in combinatorial optimization. Combinatorica 1(2):16 9–197

    work page 1981

  8. [8]

    Mathematical Programming 86(1):17–39

    G¨ unl¨ uk O (1999) A branch-and-cut algorithm for capacitate d network design problems. Mathematical Programming 86(1):17–39

    work page 1999

  9. [9]

    Hartmann M (1994) Cutting Planes and the Sequential Knapsack Prob- lem. Tech. rep., University of North Carolina Technical Report TR94 /10

    work page 1994

  10. [10]

    Discrete Applied M athe- matics 160(10):1567–1582

    Kianfar K (2012) On n-step MIR and partition inequalities for inte ger knapsack and single-node capacitated flow sets. Discrete Applied M athe- matics 160(10):1567–1582

    work page 2012

  11. [11]

    Mathematical Progra mming 60(1-3):233–250

    Magnanti TL, Mirchandani P, Vachani R (1993) The convex hu ll of two core capacitated network design problems. Mathematical Progra mming 60(1-3):233–250

    work page 1993

  12. [12]

    Operations Rese arch 43(1):142–157

    Magnanti TL, Mirchandani P, Vachani R (1995) Modeling and so lving the two-facility capacitated network loading problem. Operations Rese arch 43(1):142–157

    work page 1995

  13. [13]

    Operations Research 49(3):363–371

    Marchand H, Wolsey LA (2001) Aggregation and mixed integer ro unding to solve MIPs. Operations Research 49(3):363–371

    work page 2001

  14. [14]

    Math- ematical Programming 33(1):82–92

    Marcotte O (1985) The cutting stock problem and integer roun ding. Math- ematical Programming 33(1):82–92

    work page 1985

  15. [15]

    Mathematical Programming 4 6(1- 3):379–390

    Nemhauser GL, Wolsey LA (1990) A recursive procedure to gen erate all cuts for 0-1 mixed integer programs. Mathematical Programming 4 6(1- 3):379–390

    work page 1990

  16. [16]

    SIAM Journal on Optimization 8(1):248–264

    Pochet Y, Weismantel R (1998) The sequential knapsack polyt ope. SIAM Journal on Optimization 8(1):248–264

    work page 1998

  17. [17]

    Discrete A pplied Mathematics 59(1):57–74

    Pochet Y, Wolsey LA (1995) Integer knapsack and flow covers with divisi- ble coefficients: polyhedra, optimization and separation. Discrete A pplied Mathematics 59(1):57–74

    work page 1995

  18. [18]

    Mathematical Programming 156(1-2):1–20

    Wolsey LA, Yaman H (2016) Continuous knapsack sets with divisib le ca- pacities. Mathematical Programming 156(1-2):1–20

    work page 2016