The DOI matches its Crossref record; 13 of the 13 references it cites were found in a registry or an index.
A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
Abstract
In this paper a reformulation technique is presented that takes a given linear zero-one programming problem, converts it into a zero-one polynomial programming problem, and then relinearizes it into an extended linear program. It is shown that the strength of the resulting reformulation depends on the degree of the terms used to produce the polynomial program at the intermediate step of this method. In fact, as this degree varies from one up to the number of variables in the problem, a hierarchy of sharper representations is obtained with the final relaxation representing the convex hull of feasible solutions. The reformulation technique readily extends to produce a similar hierarchy of linear relaxations for zero-one polynomial programming problems. A characterization of the convex hull in the original variable space is also available through a projection process. The structure of this convex hull characterization (or its other relaxations) can be exploited to generate strong or facetial valid inequalities through appropriate surrogates in a computational framework. The surrogation process can also be used to study various classes of facets for different combinatorial optimization problems. Some examples are given to illustrate this point.
Overview
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Run the check — free, no account needed. It reads the open-access text and checks the sources it cites.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
Maximum matching and a polyhedron with 0,1-vertices
Edmonds, J. (1965) · Journal of Research of the National Bureau of Standards Section B Mathematics and Mathematical Physics · doi:10.6028/jres.069b.013 · Cited by 1,712
Edmonds polytopes and a hierarchy of combinatorial problems
Chvátal, V. (1973) · Discrete Mathematics · doi:10.1016/0012-365x(73)90167-2 · Cited by 624
On the facial structure of set packing polyhedra
Padberg, M. W. (1973) · Mathematical Programming · doi:10.1007/bf01580121 · Cited by 596
Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
Glover, F., & Woolsey, E. (1974) · Operations Research · doi:10.1287/opre.22.1.180 · Cited by 404
The boolean quadric polytope: Some characteristics, facets and relatives
Padberg, M. W. (1989) · Mathematical Programming · doi:10.1007/bf01589101 · Cited by 356
Model Building in Mathematical Programming.
Bunday, B. D., & Williams, H. P. (1985) · Journal of the Royal Statistical Society. Series A (General) · doi:10.2307/2981914 · Cited by 356
Solving Large-Scale Symmetric Travelling Salesman Problems to Optimality
Crowder, H., & Padberg, M. W. (1980) · Management Science · doi:10.1287/mnsc.26.5.495 · Cited by 294
A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
Adams, W. P., & Sherali, H. D. (1986) · Management Science · doi:10.1287/mnsc.32.10.1274 · Cited by 255
Self-citationGlover, F., & Woolsey, E. (1973) · Operations Research · doi:10.1287/opre.21.1.156 · Cited by 130
Covering, Packing and Knapsack Problems
Padberg, M. W. (1979) · Annals of discrete mathematics · doi:10.1016/s0167-5060(08)70831-8 · Cited by 110
LP-Based Combinatorial Problem Solving
Hoffman, K., & Padberg, M. W. (1985) · Springer eBooks · doi:10.1007/978-3-642-82450-0_3 · Cited by 102
Trivial integer programs unsolvable by branch-and-bound
Jeroslow, R. G. (1974) · Mathematical Programming · doi:10.1007/bf01580225 · Cited by 90
Lp-based combinatorial problem solving
Hoffman, K., & Padberg, M. W. (1985) · Annals of Operations Research · doi:10.1007/bf02022040 · Cited by 66
Cited by
Semidefinite programming relaxations for semialgebraic problems
Parrilo, P. A. (2003) · Mathematical Programming · doi:10.1007/s10107-003-0387-5 · Cited by 1,527
A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
Laurent, M. (2003) · Mathematics of Operations Research · doi:10.1287/moor.28.3.470.16391 · Cited by 373
Two-stage fleet assignment model considering stochastic passenger demands
Sherali, H. D., & Zhu, X. (2008) · Operations Research · doi:10.1287/opre.1070.0476 · Cited by 56
Self-citationLearning dynamic polynomial proofs
Fawzi, A., Malinowski, M., Fawzi, H., & Fawzi, O. (2019) · arXiv · doi:10.48550/arxiv.1906.01681 · Cited by 8
Metadata
- Authors
- Sherali, H. D., & Adams, W. P.
- Venue
- SIAM Journal on Discrete Mathematics
- Published
- 1990-08
- Volume
- 3
- Issue
- 3
- Pages
- 411-430
- ISSN
- 0895-4801 (ISSN-L)
- 1095-7146
- OpenAlex
- W2049143039
- Cited by
- 931
- References
- 13
- FWCI
- 4.13
- Type
- journal article
- Language
- en
- Open access
- closed
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.