Pith. sign in

REVIEW 5 major objections 5 minor 56 references

Automating Idealness Proofs for Binary Programs with Application to Rectangle Packing

T0 review · 5 major / 5 minor · reviewed 2026-08-03 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗

Pith's one-line read A new optimization-based framework automatically certifies when mixed-binary programs are 'ideal,' and applies it to settle four rectangle-packing formulations.

desk verdict A useful automation framework for idealness proofs with a checkable SB-L counterexample, but the positive computational theorems—especially SB-M—are not certified as stated; worth peer review with major-revision expectations. read the letter →

arxiv 2601.15252 v2 pith:C3H4WEW7 submitted 2026-01-21 math.OC

Jamie Fravel , Robert Hildebrand This is my paper
classification math.OC MSC 90C1190C2790C57
keywords idealformulationmixed-binarylinearprogramrectanglepackingpairwise-idealselectorfunctionmultilinearrelaxationcomputer-aidedproofdisjunctiveprogramming
verification ladder T0 review T1 audit T2 compute T3 formal

The pith

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

The reading

The paper is trying to replace the painstaking, page-after-page case analyses that usually accompany proofs that an integer program is ideal — meaning its continuous relaxation already equals the convex hull of its integer solutions, so the problem can be solved as a plain linear program. It builds a family of optimization models, Ideal O'Matic and its parametric version, that actively search for fractional extreme points; finding none certifies idealness. Applied to two-rectangle (pairwise) instances of rectangle packing, the framework gives computational proofs that the Standard Unary and Refined Unary formulations are pairwise-ideal, confirms that the logarithmic Hamming-selector binary formulation is not, and produces a new multilinear binary formulation that is. If the framework is sound, it turns idealness verification into a routine computational task instead of a research-level proof effort.

What carries the argument

The engine is a bilevel-style optimization formulation, IOM: indicators select nc+nb constraints to be tight, a rank constraint forces linear independence, and the objective maximizes phi(y)=sum(1-|2y_i-1|), zero only when all binary variables are integral. The parametric extension PIOM lets LB, UB and precedence margins P vary as variables, turning the proof into a nonconvex quadratically constrained program, with linear-dependence covers (circuits) added by a separation subroutine. The second key object is the selector function: replacing the one-hot unary encoding with a Hamming-distance selector destroys idealness, while the multilinear selector (a product of Bernoulli factors) restores

What would settle it

Run the parametric search with exact rational arithmetic and epsilon=0 on a parameter instance where P equals UB-LB (or, for RU, where the two strict inequalities vanish). Any fractional extreme point with positive penalty would refute the corresponding theorem; equivalently, for SB-L, the paper itself supplies a concrete fractional vertex at c=(9,1,9,1), delta=(1/2,1/2) on a 10x10 region with 2x2 rectangles — the same kind of explicit witness, if found for SU, RU, or SB-M at a boundary parameter, would settle the claim.

Watch

Extended reading notes

Core claim

The central claim is that idealness of a mixed-binary linear program can be verified by maximizing a fractionality penalty over points that are feasible and tight to a full set of linearly independent constraints; an optimal value of zero means every extreme point of the relaxation is integral. The parametric version lets the constraint data vary and searches over whole families of instances, proving pairwise-idealness for the rectangle-packing formulations SU and RU (under stated parameter inequalities), disproving it for SB-L via an explicit fractional extreme point, and establishing it for the new SB-M built from the multilinear selector. The same framework is used to model a novel cleara

Load-bearing premise

The load-bearing premise is that the finite lists of linear-dependence patterns in Lemmas 1–3 are exhaustive for every parameter value in the ranges considered; they are checked by direct computation on sampled data rather than proven, and the floating-point solver tolerance plus the epsilon=W/10 boundary exclusion means the certified region is slightly smaller than the stated theorems.

Editorial extensions

If this is right

  • If Theorem 1 and 2 are correct, two standard unary rectangle-packing formulations can be solved as continuous LPs for any two-rectangle instance meeting the stated inequalities, eliminating branch-and-bound at that scale.
  • Theorem 3 means the logarithmic two-binary-variable formulation based on the Hamming selector cannot be relied upon; its fractional extreme point is constructible for any instance, not just a special case.
  • Theorem 4 gives a pairwise-ideal formulation with only two binary variables per pair, using the multilinear selector and McCormick linearization, combining logarithmic size with idealness.
  • The paper's experiments indicate pairwise-idealness alone does not guarantee faster solving in practice; sequence-pair inequalities and branching priorities matter more, especially for binary formulations.
  • The clearance-aware model extends the same idealness analysis to layouts requiring buffer zones, so the proof framework applies beyond plain packing.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

  • Because Proposition 2 shows no linear selector can map interior hypercube points into the simplex, the failure of SB-L is likely structural; the multilinear selector is the unique exact polynomial extension, suggesting any ideal logarithmic formulation must be nonlinear or use a different encoding.
  • The epsilon=W/10 gap and reliance on floating-point solve means the theorems are proven on an open region; a natural next step is exact rational computation or symbolic vertex enumeration to close the boundary cases, especially for RU's 56-case parameter split.
  • The dependence-cover lists in Lemmas 1-3 are asserted comprehensive but only checked computationally; a reader wanting full rigor could verify exhaustiveness algebraically, and the same separation approach could be reused for other disjunctive formulations (e.g., multi-rectangle or higher-dimensional packing).
  • The negligible practical impact of pairwise-idealness hints that idealness is not the right sole predictor of solver performance; the framework could be used to benchmark other structural properties, such as sharpness or local idealness.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Referee Report

5 major / 5 minor

Summary. The paper develops Ideal O'Matic (IOM) and its parametric variant PIOM, optimization-based frameworks for certifying idealness of mixed-binary linear programs. The verification problem is formulated as a linear program for fixed data and as a nonconvex quadratic program when the data are parametric. The framework is applied to rectangle packing formulations: the paper claims computational proofs that the Standard Unary (SU) and Refined Unary (RU) formulations are pairwise-ideal, gives a counterexample showing the linear Hamming-selector formulation SB-L is not pairwise-ideal, and introduces a new multilinear formulation SB-M that it claims is pairwise-ideal. A secondary contribution is a generalization of rectangle packing with edge clearances, plus computational experiments comparing the formulations. The main theorems are Theorems 1, 2, 3, and 4; Section 5.4 explicitly acknowledges numerical gaps in the proof framework.

Significance. The paper's core idea is attractive: replacing long analytic case analyses with optimization-based searches for fractional extreme points could be a useful tool in integer programming theory. The explicit counterexamples for SB-L and NU in Appendix C are checkable and appear correct, and the new SB-M formulation is a plausible contribution. The paper also ships code, model files, and data, and it honestly discloses the numerical limitations of its approach. However, the advertised computational proofs are not rigorous as stated: the acknowledged epsilon gap and floating-point tolerances, together with the nonzero PIOM bounds reported for SB-M, mean that Theorems 1, 2, and 4 are not established by the evidence provided. The value of the paper is real, but the proof claims need substantial revision or additional verification.

major comments (5)
  1. [§5.4, Theorems 1 and 2] The computational proofs use an epsilon = W/10 tolerance and a case matrix C that records only whether UB_js - P_ijs - LB_is is at least epsilon or exactly zero. Parameter values for which this difference lies in (0, epsilon) are not covered. Thus Theorems 1 and 2, stated for all non-trivial instances satisfying the given inequalities, are not proven. For Theorem 2 the same epsilon gap applies to the strict inequalities P_kls+LB_ks-LB_ls>0 and P_kls+UB_ks-UB_ls>0, and the paper itself notes that the full 56-case analysis is not performed. The authors should either close this gap with rigorous interval/rational methods or explicitly restate the results as epsilon-conditional computational evidence rather than proofs.
  2. [§5.3, Theorem 4] The reported PIOM results do not certify that the optimal objective value is zero. Eight cases are asterisked with dual bounds in [4.26e-7, 9.55e-7], and four cases list positive 'Optimum' values (7.99e-8, 9.13e-11, 2.52e-9, 1.12e-9). If any such positive value is feasible, it is a fractional extreme point contradicting Theorem 4; if it is numerical noise, then the solver has not proved the optimum is zero. The subsequent linear IOM checks only verify the discrete (LB,UB,P) points returned by PIOM, not the continuous parameter regions claimed by the theorem. Theorem 4 is therefore unproven as stated.
  3. [§5.1-§5.3, Lemmas 1-3] Each lemma asserts that the listed collections are a 'comprehensive set of dependence covers' and says that the dependencies can be verified by direct computation. For the zero-objective direction, nonexhaustiveness of the list would be conservative (omitting a valid cover relaxes IOM), so the load-bearing issue is whether every listed cover is a genuine linear dependence over the claimed parameter ranges. Please provide explicit algebraic combination certificates or machine-checkable proofs for each dependence, rather than relying solely on repository notebooks.
  4. [§2, Eq. (IOM.e) and §5.1] The big-M constant in constraint (IOM.e) is not specified. The text 'we set W=M=10' suggests that the container width is being used as the big-M value. If M is not sufficiently large, (IOM.e) can remove genuinely feasible points, including extreme points, and produce a spurious zero objective. The authors should state how M is chosen, prove that the chosen value is valid for the bounded variables in the model, and report the value used in each computation.
  5. [§8] The conclusion claims that the paper develops 'an algebraic vertex enumeration approach' that provides independent verification without floating-point optimization, but no such approach is presented in Sections 2-7. This is either a missing contribution or an erroneous claim. Please add the method and its verification, or delete the sentence.
minor comments (5)
  1. [§1.2] 'Padburg' should be 'Padberg'.
  2. [§5.1] The phrase 'we set W=M=10 w.l.o.g.' needs a scaling justification. Setting two different quantities to the same value is not automatically without loss of generality unless all parameters and constraints scale appropriately.
  3. [Tables 5-7] Tables 5-7 appear misaligned: several entries are not clearly matched to column headers, and some cells contain extra numbers or percentages without a clear row/column correspondence. Please reformat these tables.
  4. [§5.3] There is a typo: 'Additionaly' should be 'Additionally'.
  5. [References] References [45] and [46] are duplicate entries for Vielma's 'Mixed Integer Linear Programming Formulation Techniques'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: IOM/PIOM is a direct counterexample search, not a derivation that assumes its conclusion.

full rationale

The paper's derivation chain is a faithful reformulation of the idealness definition. Definition 3 equates idealness with integrality of all extreme points, and IOM (Section 2) is constructed so that a feasible solution with positive objective is exactly a fractional extreme point; the optimal value is zero if and only if no such point exists (Proposition 1). This is a direct test of the definition, not a fitted parameter renamed as a prediction. Corollary 1 correctly notes that restricting IOM.g to a subset of dependence covers can only relax the model, so a zero objective on the restricted model still certifies idealness; omitted covers cannot create a false positive. The dependence covers in Lemmas 1–3 are used to strengthen the search, and their validity is checked by rank computations, not assumed. The paper's own Section 5.4 explicitly flags the real limitations: epsilon tolerances, floating-point Gurobi solves, and the unproven exhaustiveness of cover lists. These are correctness/rigor concerns, not circularity. There are no load-bearing self-citations (the authors cite external work such as [13], [29], [48]); no result is imported from the authors' prior work as a forced uniqueness theorem; and no known empirical pattern is renamed as a new derivation. Thus the central claim is self-contained with respect to its inputs, and any objections are about numerical certification, not about circular dependence.

Assumptions & free parameters 3 free parameters · 5 assumptions · 0 invented entities

No new physical or empirical entities are postulated. The SB-M formulation and selector functions are mathematical definitions whose properties are internally verifiable; the computational proofs rest instead on free numerical tolerances and unproven cover exhaustiveness, which are captured above.

free parameters (3)
  • epsilon tolerance (epsilon = W/10) = W/10 (1 in the W=10 experiments)
    Chosen to enforce strict inequality conditions and non-triviality in the parametric solver; leaves all parameter values with margin in (0, W/10) unproved (Sections 5.1, 5.4).
  • Big-M in IOM(e) and separation model (3) = W=M=10 in experiments; theoretical bound in Remark 1
    Needed to linearize tightness constraints; its finite value affects numerical behavior and solver tolerances.
  • Gurobi tolerances (FeasibilityTol, IntFeasTol, MIPGapAbs) = 1e-9 (MIPGapAbs 1e-9)
    Chosen to balance convergence with numerical stability; results depend on these values and are not exact (Section 5.4).
assumptions (5)
  • standard math A point of a polyhedron is a vertex iff it satisfies n_c+n_b linearly independent tight constraints (Definitions 2-3).
    Standard polyhedral fact underlying the IOM formulation.
  • ad hoc to paper The dependence cover lists in Lemmas 1, 2 and 3 are comprehensive over all parameter values considered.
    Asserted in Section 5.1 ('We will not formally prove Lemma 1 here... verified by direct computation') and similarly for the others; no proof of exhaustiveness is given.
  • domain assumption Gurobi's nonconvex QCP solver returns correct global optima within the reported tolerances.
    PIOM is a nonconvex quadratic program solved with Gurobi 13.0.0 using floating-point tolerances; Section 5.4 notes that rational/exact solvers for such programs are unavailable.
  • domain assumption Theorem 2 may restrict to instances with Pkls+LBks-LBls >= epsilon and Pkls+UBks-UBls >= epsilon.
    The paper excludes these degenerate conditions and conjectures they can be removed (Section 5.2, Theorem 2 statement).
  • ad hoc to paper Instances with boundary values (UB-LB in (0,epsilon) or P margins in (0,epsilon)) are treated as trivial or excluded by the epsilon tolerance in non-triviality.
    Definition 4 and the computational proofs enforce strict inequalities via epsilon; Section 5.4 calls this a 'glaring hole'.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Automating Idealness Proofs for Binary Programs with Application to Rectangle Packing." pith.science (2026). https://pith.science/paper/C3H4WEW7

@misc{pith2026260115252,
  author       = {Pith},
  title        = {Pith review of: Automating Idealness Proofs for Binary Programs with Application to Rectangle Packing},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/C3H4WEW7}},
  note         = {Machine review of arXiv:2601.15252}
}
read the original abstract

An integer program is called ideal if its continuous relaxation coincides with its convex hull allowing the problem to be solved as a continuous program and offering substantial computational advantages. Proving idealness analytically can be extraordinarily tedious -- even for small formulations -- such proofs often span many pages of intricate case analysis which motivates the development of automated verification methods. We develop a general-purpose framework for certifying idealness in Mixed Binary Linear Programs (MBLPs), formulating the verification problem as a linear program when the data is fixed and as a nonconvex quadratic program when the data is parametric. We apply this framework to study several formulations of the rectangle packing problem that are conjectured to be pairwise-ideal, obtaining computational proofs where analytic proofs were previously unknown or impractical. As our second contribution, we introduce and model a novel generalization of the rectangle packing problem that enforces edge clearances between selected rectangles. We present both existing and novel MBLP formulations which arise from different encodings of the underlying disjunctive constraints. We perform some computational experiments on these formulations under a strip-packing objective to determine the importance of pairwise-idealness in practice.

Figures

Figures reproduced from arXiv: 2601.15252 by the authors.

Figure 1
Figure 1. Some options for the penalty function ϕ. We use (a) as it can be encoded with linear constraints, whereas the quadratic version (b) introduces unnecessary nonlinearities. When looking for extreme points, it is important to remember that bounds 0 ≤ yi ≤ 1 on the integer variables exist and contribute to the nc + nb many tight constraints. However, such simple inequalities are often redundant to other, more complicate… view at source ↗
Figure 2
Figure 2. Examples of Clearance Occlusion Clearance is an important feature of many practical layout/packing problems: manufacturing machine layouts may require clearances to reduce vibrations in neighboring machines, adequately ventilate the workspace, provide access to maintenance panels, or simply to allow for manual op￾eration; circuit boards may require clearances to improve heat dissipation or mitigate crosstalk interfe… view at source ↗
Figure 3
Figure 3. Visualization of the parameters letters for these parameters to emphasize their composite nature. Given this notation, Model 5 collapses to _ cis ∈ [LBis, UBis] ∀ i ∈ [[N]], s ∈ {x, y} (6a) (k,l,s)∈Fij (cks + Pkls ≤ cls) ∀ (i, j) ∈ P. (6b) Conveniently, additional constraints on displacement between particular pairs of rectangles can be encoded by choosing precedence margins between said pair independent of their cl… view at source ↗
Figures from the paper (6 more)
Figure 4
Figure 4. Figure 4: The four disjunctive cases for non-overlapping rectangles [PITH_FULL_IMAGE:figures/full_fig_p011_4.png]
Figure 5
Figure 5. Figure 5: Two possible initial solutions to the N = 50 Strip Packing Problem. In Appendix C, we provide some additional details including a proof that NU is not ideal and some evidence that HU is. 6.5 Cuts and Heuristics Gurobi has a large number of cutting plane and heuristic r…
Figure 6
Figure 6. Figure 6: A symmetric solution. It is clear that i ↼x j, j ↼x k and i ↼y j which implies an indicator solution of δij = (0, 0), δjk = (0, 0) and δik = (1, 0) and violates SPB. Instead, SPB requires that δik = (0, 0) which implies i ↼x k—another valid solution. There also exists …
Figure 7
Figure 7. Figure 7: Selected convergence plots for the Cuts and Heuristics experiment [PITH_FULL_IMAGE:figures/full_fig_p027_7.png]
Figure 8
Figure 8. Figure 8: The effect of Cuts and Heuristics is reduced under the Branching Rule and Sequence Pair [PITH_FULL_IMAGE:figures/full_fig_p028_8.png]
Figure 9
Figure 9. Figure 9: Convergence plots from our experiment with Branching Rules and Sequence Pair Inequal [PITH_FULL_IMAGE:figures/full_fig_p028_9.png]

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

56 extracted references · 21 canonical work pages

  1. [1]

    Symmetry-breaking constraints for packing identical rectangles within polyhedra

    Ricardo Andrade and Ernesto G Birgin. “Symmetry-breaking constraints for packing identical rectangles within polyhedra”. In:Optimization Letters7.2 (2013), pp. 375–405.doi:10.1007/ s11590-011-0425-9

    2013

  2. [2]

    Disjunctive programming: Properties of the convex hull of feasible points

    Egon Balas. “Disjunctive programming: Properties of the convex hull of feasible points”. In: Discrete Applied Mathematics89.1 (1998), pp. 3–44.issn: 0166-218X.doi:10.1016/S0166- 218X(98)00136-X

    doi:10.1016/s0166- 1998

  3. [3]

    Suresh Bolusani et al.The SCIP Optimization Suite 9.0. 2024. arXiv:2402.17702 [math.OC]. url:https://arxiv.org/abs/2402.17702. 30

    arXiv 2024

  4. [4]

    A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces

    Andreas Bortfeldt. “A genetic algorithm for the two-dimensional strip packing problem with rectangular pieces”. In:European Journal of Operational Research172.3 (2006), pp. 814–837. issn: 0377-2217.doi:10.1016/j.ejor.2004.11.016

    work page doi:10.1016/j.ejor.2004.11.016 2006

  5. [5]

    An epsilon-accurate model for optimal unequal-area block layout design

    Ignacio Castillo and Tapio Westerlund. “An epsilon-accurate model for optimal unequal-area block layout design”. In:Computers and Operations Research32.3 (2005), pp. 429–447.issn: 0305-0548.doi:10.1016/S0305-0548(03)00246-6

    work page doi:10.1016/s0305-0548(03)00246-6 2005

  6. [6]

    Atomic Decomposition by BasisPursuit

    Scott Shaobing Chen, David L. Donoho and Michael A. Saunders. “Atomic Decomposition by BasisPursuit”. In:SIAM Review43.1(2001),pp. 129–159.doi:10.1137/S003614450037906X

    doi:10.1137/s003614450037906x 2001

  7. [7]

    Verifying integer programming results

    Kevin KH Cheung, Ambros Gleixner and Daniel E Steffy. “Verifying integer programming results”. In:Integer Programming and Combinatorial Optimization: 19th International Con- ference, IPCO 2017, Waterloo, ON, Canada, June 26-28, 2017, Proceedings 19.Springer.2017, pp. 148–160.isbn: 978-3-319-59250-3.doi:10.1007/978-3-319-59250-3_13

    work page doi:10.1007/978-3-319-59250-3_13 2017

  8. [8]

    Michele Conforti, Gérard Cornuéjols and Giacomo Zambelli.Integer Programming. Vol. 271. Graduate Texts in Mathematics. Cham: Springer, 2014.isbn: 978-3-319-11007-3.doi:10 . 1007/978-3-319-11008-0

    2014

Show all 56 references
  1. [9]

    A computational status update for exact rational mixed integer programming

    Leon Eifler and Ambros Gleixner. “A computational status update for exact rational mixed integer programming”. In:Mathematical Programming197.2 (2023), pp. 793–812.doi:10. 1007/s10107-021-01749-5

    2023

  2. [10]

    A Safe Computational Framework for Integer Programming Applied to Chvátal’s Conjecture

    Leon Eifler, Ambros Gleixner and Jonad Pulaj. “A Safe Computational Framework for Integer Programming Applied to Chvátal’s Conjecture”. In:ACM Trans. Math. Softw.48.2 (May 2022).issn: 0098-3500.doi:10.1145/3485630

    2022 doi

  3. [11]

    A survey on the cutting and packing problems

    Loris Faina. “A survey on the cutting and packing problems”. In:Bollettino dell’Unione Matematica Italiana13.4 (Aug. 2020), pp. 567–572.issn: 2198-2759.doi:10.1007/s40574- 020-00253-6

    2020 doi

  4. [12]

    An Exact Formulation for Multi-Workshop Facility Layout Problem with Clearance Bounds

    Chao Guan, Zeqiang Zhang and Silu Liu. “An Exact Formulation for Multi-Workshop Facility Layout Problem with Clearance Bounds”. In:2019 IEEE International Conference on Indus- trial Engineering and Engineering Management (IEEM). 2019, pp. 1583–1587.doi:10.1109/ IEEM44572.2019.8978631

    2019

  5. [14]

    A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints

    Joey Huchette and Juan Pablo Vielma. “A Combinatorial Approach for Small and Strong Formulations of Disjunctive Constraints”. In:Mathematics of Operations Research44.3 (2019), pp. 793–820.doi:10.1287/moor.2018.0946

    2019

  6. [15]

    Fixed and flexible shape facility layout problems using biogeography-based optimisation algorithm

    Supriya Ingole and Dinesh Singh. “Fixed and flexible shape facility layout problems using biogeography-based optimisation algorithm”. In:International Journal of Industrial and Sys- tems Engineering37.1 (2021), p. 84.issn: 1748-5045.doi:10.1504/ijise.2021.112469

    2021

  7. [16]

    Unequal-area, fixed-shape facility layout problems using the firefly algorithm

    Supriya Ingole and Dinesh Singh. “Unequal-area, fixed-shape facility layout problems using the firefly algorithm”. In:Engineering Optimization49.7 (2017), pp. 1097–1115.doi:10.1080/ 0305215X.2016.1235327. [17]IPOPT Documentation. Accessed: 2025-06-10.url:https://coin- or.githu...

    2017

  8. [18]

    Modelling with integer variables

    R. G. Jeroslow and J. K. Lowe. “Modelling with integer variables”. In:Mathematical Program- ming at Oberwolfach II. Ed. by Bernhard Korte and Klaus Ritter. Berlin, Heidelberg: Springer Berlin Heidelberg, 1984, pp. 167–184.isbn: 978-3-642-00915-0.doi:10.1007/BFb0121015

    1984 doi

  9. [19]

    On verifiable sufficient conditions for sparse signal recovery via L1 minimization

    Anatoli Juditsky and Arkadi Nemirovski. “On verifiable sufficient conditions for sparse signal recovery via L1 minimization”. In:Mathematical programming127 (2011), pp. 57–88.doi: 10.1007/s10107-010-0417-z

    2011 doi

  10. [20]

    A biased random-key genetic algorithm using dotted board model for solving two-dimensional irregular strip packing problems

    Bonfim Amaro Junior et al. “A biased random-key genetic algorithm using dotted board model for solving two-dimensional irregular strip packing problems”. In:2020 IEEE Congress on Evolutionary Computation (CEC). 2020.doi:10.1109/CEC48606.2020.9185794

    2020

  11. [21]

    Construction heuristics for the single row layout problem with machine-spanning clearances

    B. Keller. “Construction heuristics for the single row layout problem with machine-spanning clearances”. In:INFOR: Information Systems and Operational Research57.1 (2019), pp. 32– 55.doi:10.1080/03155986.2017.1393729

    2019

  12. [22]

    Integer-Programming Bounds on Pebbling Numbers of Cartesian-ProductGraphs

    Franklin Kenter and Daphne Skipper. “Integer-Programming Bounds on Pebbling Numbers of Cartesian-ProductGraphs”.In:Combinatorial Optimization and Applications.Ed.byDonghyun Kim, R. N. Uma and Alexander Zelikovsky. Cham: Springer International Publishing, 2018, pp. 681–695.doi:...

    2018 doi

  13. [23]

    Using Integer Programming to Search for Counterexamples: A Case Study

    Giuseppe Lancia, Eleonora Pippia and Franca Rinaldi. “Using Integer Programming to Search for Counterexamples: A Case Study”. In:Mathematical Optimization Theory and Operations Research. Ed. by Alexander Kononov et al. Cham: Springer International Publishing, 2020, pp. 69–84.i...

    2020 doi

  14. [24]

    Visual nesting system for irregular cutting-stock problem based on rubber band packing algorithm

    Xiaoping Liao et al. “Visual nesting system for irregular cutting-stock problem based on rubber band packing algorithm”. In:Advances in Mechanical Engineering8.6 (2016).doi: 10.1177/1687814016652080

    2016 doi

  15. [25]

    Two-dimensional packing problems: A survey

    Andrea Lodi, Silvano Martello and Michele Monaci. “Two-dimensional packing problems: A survey”. In:European Journal of Operational Research141.2 (2002), pp. 241–252.issn: 0377- 2217.doi:https://doi.org/10.1016/S0377-2217(02)00123-6

    2002 doi

  16. [26]

    An Application of an Unequal-Area Facilities Layout Problem with Fixed-Shape Facilities

    Alan McKendall and Artak Hakobyan. “An Application of an Unequal-Area Facilities Layout Problem with Fixed-Shape Facilities”. In:Algorithms14.11 (2021).issn: 1999-4893.doi:10. 3390/a14110306

    2021

  17. [27]

    Applying the sequence-pair represen- tation to optimal facility layout designs

    Russell D. Meller, Weiping Chen and Hanif D. Sherali. “Applying the sequence-pair represen- tation to optimal facility layout designs”. In:Operations Research Letters35.5 (2007), pp. 651– 659.issn: 0167-6377.doi:10.1016/j.orl.2006.10.007

    2007 doi

  18. [28]

    A biased random key genetic algorithm for open dimension nesting problems using no-fit raster

    Leandro R. Mundim, Marina Andretta and Thiago Alves de Queiroz. “A biased random key genetic algorithm for open dimension nesting problems using no-fit raster”. In:Expert Systems with Applications81 (2017), pp. 358–371.issn: 0957-4174.doi:10.1016/j.eswa.2017.03. 059

    2017 doi

  19. [29]

    On the degree of Boolean functions as real polynomials

    Noam Nisan and Mario Szegedy. “On the degree of Boolean functions as real polynomials”. In:Computational complexity4.4 (1994), pp. 301–313.doi:10.1007/BF01263419

    1994 doi

  20. [30]

    Manfred Padberg.Linear Optimization and Extensions. Vol. 12. Algorithms and Combina- torics. Springer Science & Business Media, 1999.isbn: 978-3-540-65833-7.doi:10.1007/978- 3-662-12273-0. 32

    1999 doi

  21. [31]

    Locally Ideal LP Formulations I

    Manfred Padberg and Minendra P. Rijal. “Locally Ideal LP Formulations I”. In:Location, Scheduling, Design and Integer Programming. Vol. 3. International Series in Operations Re- search & Management Science. Boston, MA: Springer, 1996.isbn: 978-1-4613-1379-3.doi: 10.1007/978-1-...

    1996 doi

  22. [32]

    SOLVING IRREGULAR STRIP PACKING PROBLEMS WITH FREE ROTATIONS USING SEPARATION LINES

    Jeinny Peralta, Marina Andretta and José Fernando Oliveira. “SOLVING IRREGULAR STRIP PACKING PROBLEMS WITH FREE ROTATIONS USING SEPARATION LINES”. In:Pesquisa Operacional38.2 (2018), pp. 195–214.issn: 0101-7438.doi:10 . 1590 / 0101 - 7438.2018.038.02.0195

    2018

  23. [33]

    Cutting planes for families implying Frankl’s conjecture

    Jonad Pulaj. “Cutting planes for families implying Frankl’s conjecture”. In:Mathematics of Computation89.322 (2020), pp. 829–857.doi:10.1090/mcom/3461

    2020 doi

  24. [34]

    A clique covering MIP model for the irregular strip packing problem

    Marcos Okamura Rodrigues and Franklina M.B. Toledo. “A clique covering MIP model for the irregular strip packing problem”. In:Computers & Operations Research87 (2017), pp. 221– 234.issn: 0305-0548.doi:10.1016/j.cor.2016.11.006

    2017 doi

  25. [35]

    Solving an extended multi-row facility layout problem with fuzzy clearances using GA

    Soroush Safarzadeh and Hamidreza Koosha. “Solving an extended multi-row facility layout problem with fuzzy clearances using GA”. In:Applied Soft Computing61 (2017), pp. 819–831. issn: 1568-4946.doi:https://doi.org/10.1016/j.asoc.2017.09.003

    2017 doi

  26. [36]

    A study in pairwise clustering for bi-dimensional irregular strip packing using the dotted board model

    André Kubagawa Sato et al. “A study in pairwise clustering for bi-dimensional irregular strip packing using the dotted board model”. In:IFAC-PapersOnLine51.11 (2018), pp. 284–289. doi:10.1016/j.ifacol.2018.08.297

    2018 doi

  27. [37]

    Alexander Schrijver.Theory of linear and integer programming. en. Wiley Series in Discrete Mathematics & Optimization. Chichester, England: John Wiley & Sons, Apr. 1998.isbn: 978-0-4708-6059-5

    1998

  28. [38]

    Enhanced Model Formu- lations for Optimal Facility Layout

    Hanif D. Sherali, Barbara M. P. Fraticelli and Russell D. Meller. “Enhanced Model Formu- lations for Optimal Facility Layout”. In:Operations Research51.4 (2003), pp. 629–644.doi: 10.1287/opre.51.4.629.16096

    2003 doi

  29. [39]

    2DCPackGen: A problem generator for two-dimensional rectangular cutting and packing problems

    Elsa Silva, José F. Oliveira and Gerhard Wäscher. “2DCPackGen: A problem generator for two-dimensional rectangular cutting and packing problems”. In:European Journal of Oper- ational Research237.3 (2014), pp. 846–856.issn: 0377-2217.doi:10.1016/j.ejor.2014. 02 . 059.url:https ...

    2014 doi

  30. [40]

    Cutting and packing problems for irregular objects with continuous rotations: mathematical modelling and non-linear op- timization

    Yuriy Stoyan, Alexander Pankratov and Tatiana Romanova. “Cutting and packing problems for irregular objects with continuous rotations: mathematical modelling and non-linear op- timization”. In:Journal of the Operational Research Society67.5 (2016), pp. 786–800.doi: 10.1057/jor...

    2016 doi

  31. [41]

    Computing the spark: mixed-integer programming for the (vector) matroid girth problem

    Andreas M. Tillmann. “Computing the spark: mixed-integer programming for the (vector) matroid girth problem”. In:Computational Optimization and Applications74.2 (June 2019), pp. 387–441.issn: 1573-2894.doi:10.1007/s10589-019-00114-9

    2019 doi

  32. [42]

    The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing

    Andreas M. Tillmann and Marc E. Pfetsch. “The Computational Complexity of the Restricted Isometry Property, the Nullspace Property, and Related Concepts in Compressed Sensing”. In:IEEE Transactions on Information Theory60.2 (2014), pp. 1248–1259.doi:10.1109/ TIT.2013.2290112

    2014

  33. [43]

    Zoning Constrained Machine Layout Problem with Mutual Clearances

    Zeynep Uruk and Nevra Akbilek. “Zoning Constrained Machine Layout Problem with Mutual Clearances”. In:Scientia Iranica0.0 (2022).issn: 2345-3605.doi:10 . 24200 / sci . 2022 . 57877.5453. 33

    2022

  34. [44]

    Embedding formulations and complexity for unions of polyhedra

    Juan Pablo Vielma. “Embedding formulations and complexity for unions of polyhedra”. In: Management Science64.10 (2018), pp. 4721–4734.doi:10.1287/mnsc.2017.2856

    2018

  35. [46]

    Mixed Integer Linear Programming Formulation Techniques

    Juan Pablo Vielma. “Mixed Integer Linear Programming Formulation Techniques”. In:SIAM Review57.1 (2015), pp. 3–57.doi:10.1137/130915303

    2015 doi

  36. [47]

    Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints

    Juan Pablo Vielma and George L. Nemhauser. “Modeling Disjunctive Constraints with a Logarithmic Number of Binary Variables and Constraints”. In:Mathematical Programming 128.1–2 (2011), pp. 49–72.doi:10.1007/s10107-009-0295-4

    2011 doi

  37. [48]

    Wolsey.Integer Programming

    Laurence A. Wolsey.Integer Programming. 2nd. Hoboken, NJ: John Wiley & Sons, 2020.isbn: 978-1-119-60647-5

    2020

  38. [49]

    A hybrid multiobjective GRASP for a multi-row facility layout problem with extra clearances

    Xiaodong Li Xing Wan Xingquan Zuo and Xinchao Zhao. “A hybrid multiobjective GRASP for a multi-row facility layout problem with extra clearances”. In:International Journal of Production Research60.3 (2022), pp. 957–976.doi:10.1080/00207543.2020.1847342

    2022

  39. [50]

    A tabu search heuristic for the single row layoutproblemwithsharedclearances

    Meng Yu, Xingquan Zuo and Chase C. Murray. “A tabu search heuristic for the single row layoutproblemwithsharedclearances”.In:2014 IEEE Congress on Evolutionary Computation (CEC). 2014, pp. 819–825.doi:10.1109/CEC.2014.6900353

    2014

  40. [51]

    Sharing clearances to improve machine layout

    X. Q. Zuo, C. C. Murray and A. E. Smith. “Sharing clearances to improve machine layout”. In:International Journal of Production Research54.14 (2016), pp. 4272–4285.doi:10.1080/ 00207543.2016.1142134. 34 Appendices A An Analytic Proof of Theorem 1 This proof is largely a copy o...

    2016

  41. [52]

    A fractional ˆδˆsnecessitates a fractional extreme point in the projected system (16) which is a contradiction as we have already demonstrated that (16) has no fractional extreme points

  42. [53]

    We have already shown that this is a contradiction

    If (16g) is not tight in direction ˆt, then a fractional ˆδˆt implies a fractional ˆδˆsby equality constraint (SU.d). We have already shown that this is a contradiction

  43. [54]

    However, (SU.d) is linearly dependent with a tight (16g) in the directionˆtand tight (16h) and (16i) in the direction ofˆs

    On the other hand, if (16g) is tight in the directionˆt, then a fractionalˆδˆt implies that neither (16h) nor (16i) is tight in the directionˆtwhile both are tight in the direction ofˆs. However, (SU.d) is linearly dependent with a tight (16g) in the directionˆtand tight (16h)...

  44. [55]

    But the projected system (16) has only four variables and cannot support five or more linearly independent, tight constraints

    Finally, if ˆthas fewer than three of the tight inequalities; thenˆsmust have at least five. But the projected system (16) has only four variables and cannot support five or more linearly independent, tight constraints. 41 B Additional Tables and Plots Table 8: Additional resu...

  45. [56]

    Notice that the SB constraints{(a ijx),(a ijy ),(b ijx),(b jix),(c ijx),(c ijy )}withς←ς U, are given by:   0 1 0 0 2 2 0 0 0 1−2 2 −1 0 0 0 2 2 0 0−1 0−2 2 −1 1 0 1 10 10 0 0−1 1−10 10     c1x c2x c1y c2y δ12 δ21   ≥   3 1 −7 −9 2 −8  ...

  46. [57]

    Thus, SB-L is not generally pairwise-ideal

    The above solution is feasible to the other constraints and so is a fractional extreme point of the relaxation. Thus, SB-L is not generally pairwise-ideal. In fact, this collection of constraintsalwaysinduces aδ 12 =δ 21 = 1 2 solution regardless of problem instance. SeeCounte...

  47. [58]

    Thus,N Uis not generally pairwise-ideal

    The above solution is feasible to the other constraints and is therefore a fractional extreme point of the relaxation. Thus,N Uis not generally pairwise-ideal. SeeCounterexampleNU.nbin our repository (footnote 2) for more evidence and a slight generalization of this counterexa...

  48. [59]

    SeeCounterexampleSU.nbin our repository (footnote 2) for complete evidence

    The above solution is feasible to the other constraints and is therefore a fractional extreme point of the relaxation. SeeCounterexampleSU.nbin our repository (footnote 2) for complete evidence. 45

Pith tools

Reviewed August 3, 2026 · model on record in the stance chip above.