DOI: 10.1002/nav.3800270310. On the generation of deep disjunctive cutting planes

On the generation of deep disjunctive cutting planes

10.1002/nav.3800270310

Crossref journal-article

Wiley

Naval Research Logistics Quarterly (311)

Abstract

AbstractIn this paper we address the question of deriving deep cuts for nonconvex disjunctive programs. These problems include logical constraints which restrict the variables to at least one of a finite number of constraint sets. Based on the works of Balas. Glover, and Jeroslow, we examine the set of valid inequalities or cuts which one may derive in this context, and defining reasonable criteria to measure depth of a cut we demonstrate how one may obtain the “deepest” cut. The analysis covers the case where each constraint set in the logical statement has only one constraint and is also extended for the case where each of these constraint sets may have more than one constraint.

Bibliography

Sherali, H. D., & Shetty, C. M. (1980). On the generation of deep disjunctive cutting planes. Naval Research Logistics Quarterly, 27(3), 453â475. Portico.

Authors 2

Hanif D. Sherali (first)
C. M. Shetty (additional)

References 20 Referenced 20

Balas E. “Intersection Cuts from Disjunctive Constraints ” Management Science Research Report No. 330 Carnegie‐Mellon University (1974).
{'key': 'e_1_2_1_3_2', 'volume-title': 'Disjunctive Programming: Cutting Planes from Logical Conditions in Nonlinear Programming', 'author': 'Balas E.', 'year': '1975'} / Disjunctive Programming: Cutting Planes from Logical Conditions in Nonlinear Programming by Balas E. (1975)
Balas E. “Disjunctive Programming: Facets of the Convex Hull of Feasible Points ” Management Science Research Report No. 348 Carnegie‐Mellon University (1974).
{'key': 'e_1_2_1_5_2', 'volume-title': 'Nonlinear Programming: Theory and Algorithms', 'author': 'Bazaraa M. S.', 'year': '1979'} / Nonlinear Programming: Theory and Algorithms by Bazaraa M. S. (1979)
10.1002/nav.3800240105
10.1002/nav.3800240106
{'key': 'e_1_2_1_8_2', 'first-page': '517', 'article-title': 'Seeking a Minimax on a Bounded Set', 'volume': '11', 'author': "Dem'janov V. F.", 'year': '1970', 'journal-title': 'Soviet Mathematics Doklady'} / Soviet Mathematics Doklady / Seeking a Minimax on a Bounded Set by Dem'janov V. F. (1970)
10.1016/0012-365X(73)90095-2
10.1007/BF02026599
10.1007/BF01681342
Glover F. D.KlingmanandJ.Stutz “The Disjunctive Facet Problem: Formulation and Solutions Techniques ” Management Science Research Report No. 72–10 University of Colorado (1972).
10.1007/BF01580223
{'key': 'e_1_2_1_14_2', 'volume-title': 'With an addendum', 'author': 'Jeroslow R. G.', 'year': '1974'} / With an addendum by Jeroslow R. G. (1974)
10.1016/S0167-5060(08)70741-6
{'key': 'e_1_2_1_16_2', 'volume-title': 'Mathematical Methods and Theory in Games, Programming and Economics', 'author': 'Karlin S.', 'year': '1959'} / Mathematical Methods and Theory in Games, Programming and Economics by Karlin S. (1959)
10.1016/0012-365X(74)90070-3
10.1007/BF00934290
{'key': 'e_1_2_1_19_2', 'first-page': '593', 'article-title': 'A General Method of Solving Extremum Problems', 'volume': '8', 'author': 'Poljak B. T.', 'year': '1967', 'journal-title': 'Soviet Mathematics Doklady'} / Soviet Mathematics Doklady / A General Method of Solving Extremum Problems by Poljak B. T. (1967)
10.1016/0041-5553(69)90061-5
10.1002/nav.3800240107

Dates

Type	When
Created	18 years, 3 months ago (May 9, 2007, 11:51 p.m.)
Deposited	1 year, 9 months ago (Nov. 21, 2023, 11:13 p.m.)
Indexed	3 months, 3 weeks ago (May 15, 2025, 1:45 p.m.)
Issued	45 years ago (Sept. 1, 1980)
Published	45 years ago (Sept. 1, 1980)
Published Online	18 years, 9 months ago (Nov. 21, 2006)
Published Print	45 years ago (Sept. 1, 1980)

Funders 0

None

BibTeX

@article{Sherali_1980, title={On the generation of deep disjunctive cutting planes}, volume={27}, ISSN={1931-9193}, url={http://dx.doi.org/10.1002/nav.3800270310}, DOI={10.1002/nav.3800270310}, number={3}, journal={Naval Research Logistics Quarterly}, publisher={Wiley}, author={Sherali, Hanif D. and Shetty, C. M.}, year={1980}, month=sep, pages={453–475} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        5,
        15
      ]
    ],
    "date-time": "2025-05-15T17:45:31Z",
    "timestamp": 1747331131308
  },
  "reference-count": 20,
  "publisher": "Wiley",
  "issue": "3",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            2006,
            11,
            21
          ]
        ],
        "date-time": "2006-11-21T00:00:00Z",
        "timestamp": 1164067200000
      },
      "content-version": "vor",
      "delay-in-days": 9577,
      "URL": "http://onlinelibrary.wiley.com/termsAndConditions#vor"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1980,
        9
      ]
    ]
  },
  "abstract": "<jats:title>Abstract</jats:title><jats:p>In this paper we address the question of deriving deep cuts for nonconvex disjunctive programs. These problems include logical constraints which restrict the variables to at least one of a finite number of constraint sets. Based on the works of Balas. Glover, and Jeroslow, we examine the set of valid inequalities or cuts which one may derive in this context, and defining reasonable criteria to measure depth of a cut we demonstrate how one may obtain the \u201cdeepest\u201d cut. The analysis covers the case where each constraint set in the logical statement has only one constraint and is also extended for the case where each of these constraint sets may have more than one constraint.</jats:p>",
  "DOI": "10.1002/nav.3800270310",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2007,
        5,
        10
      ]
    ],
    "date-time": "2007-05-10T03:51:47Z",
    "timestamp": 1178769107000
  },
  "page": "453-475",
  "source": "Crossref",
  "is-referenced-by-count": 20,
  "title": "On the generation of deep disjunctive cutting planes",
  "prefix": "10.1002",
  "volume": "27",
  "author": [
    {
      "given": "Hanif D.",
      "family": "Sherali",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "C. M.",
      "family": "Shetty",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "311",
  "published-online": {
    "date-parts": [
      [
        2006,
        11,
        21
      ]
    ]
  },
  "reference": [
    {
      "key": "e_1_2_1_2_2",
      "unstructured": "Balas E. \u201cIntersection Cuts from Disjunctive Constraints \u201d Management Science Research Report No. 330 Carnegie\u2010Mellon University (1974)."
    },
    {
      "key": "e_1_2_1_3_2",
      "volume-title": "Disjunctive Programming: Cutting Planes from Logical Conditions in Nonlinear Programming",
      "author": "Balas E.",
      "year": "1975"
    },
    {
      "key": "e_1_2_1_4_2",
      "unstructured": "Balas E. \u201cDisjunctive Programming: Facets of the Convex Hull of Feasible Points \u201d Management Science Research Report No. 348 Carnegie\u2010Mellon University (1974)."
    },
    {
      "key": "e_1_2_1_5_2",
      "volume-title": "Nonlinear Programming: Theory and Algorithms",
      "author": "Bazaraa M. S.",
      "year": "1979"
    },
    {
      "key": "e_1_2_1_6_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1002/nav.3800240105"
    },
    {
      "key": "e_1_2_1_7_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1002/nav.3800240106"
    },
    {
      "key": "e_1_2_1_8_2",
      "first-page": "517",
      "article-title": "Seeking a Minimax on a Bounded Set",
      "volume": "11",
      "author": "Dem'janov V. F.",
      "year": "1970",
      "journal-title": "Soviet Mathematics Doklady"
    },
    {
      "key": "e_1_2_1_9_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0012-365X(73)90095-2"
    },
    {
      "key": "e_1_2_1_10_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF02026599"
    },
    {
      "key": "e_1_2_1_11_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01681342"
    },
    {
      "key": "e_1_2_1_12_2",
      "unstructured": "Glover F. D.KlingmanandJ.Stutz \u201cThe Disjunctive Facet Problem: Formulation and Solutions Techniques \u201d Management Science Research Report No. 72\u201310 University of Colorado (1972)."
    },
    {
      "key": "e_1_2_1_13_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF01580223"
    },
    {
      "key": "e_1_2_1_14_2",
      "volume-title": "With an addendum",
      "author": "Jeroslow R. G.",
      "year": "1974"
    },
    {
      "key": "e_1_2_1_15_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/S0167-5060(08)70741-6"
    },
    {
      "key": "e_1_2_1_16_2",
      "volume-title": "Mathematical Methods and Theory in Games, Programming and Economics",
      "author": "Karlin S.",
      "year": "1959"
    },
    {
      "key": "e_1_2_1_17_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0012-365X(74)90070-3"
    },
    {
      "key": "e_1_2_1_18_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1007/BF00934290"
    },
    {
      "key": "e_1_2_1_19_2",
      "first-page": "593",
      "article-title": "A General Method of Solving Extremum Problems",
      "volume": "8",
      "author": "Poljak B. T.",
      "year": "1967",
      "journal-title": "Soviet Mathematics Doklady"
    },
    {
      "key": "e_1_2_1_20_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1016/0041-5553(69)90061-5"
    },
    {
      "key": "e_1_2_1_21_2",
      "doi-asserted-by": "publisher",
      "DOI": "10.1002/nav.3800240107"
    }
  ],
  "container-title": "Naval Research Logistics Quarterly",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "https://api.wiley.com/onlinelibrary/tdm/v1/articles/10.1002%2Fnav.3800270310",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "https://onlinelibrary.wiley.com/doi/pdf/10.1002/nav.3800270310",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2023,
        11,
        22
      ]
    ],
    "date-time": "2023-11-22T04:13:39Z",
    "timestamp": 1700626419000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "https://onlinelibrary.wiley.com/doi/10.1002/nav.3800270310"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1980,
        9
      ]
    ]
  },
  "references-count": 20,
  "journal-issue": {
    "issue": "3",
    "published-print": {
      "date-parts": [
        [
          1980,
          9
        ]
      ]
    }
  },
  "alternative-id": [
    "10.1002/nav.3800270310"
  ],
  "URL": "http://dx.doi.org/10.1002/nav.3800270310",
  "relation": {},
  "ISSN": [
    "0028-1441",
    "1931-9193"
  ],
  "subject": [],
  "container-title-short": "Naval Research Logistics",
  "published": {
    "date-parts": [
      [
        1980,
        9
      ]
    ]
  }
}