DOI: 10.1007/bfb0120690. Lagrangean relaxation for integer programming

Lagrangean relaxation for integer programming

10.1007/bfb0120690

Crossref book-chapter

Springer Berlin Heidelberg

Mathematical Programming Studies (297)

Bibliography

Geoffrion, A. M. (1974). Lagrangean relaxation for integer programming. Approaches to Integer Programming, 82â114.

Authors 1

A. M. Geoffrion (first)

References 30 Referenced 1,015

R.D. Armstrong and P. Sinha, “Improved penalty calculations for a mixed integer branch-and-bound algorithm”, Mathematical Programming 6 (1974) 212–223. (10.1007/BF01580237) / Mathematical Programming by R.D. Armstrong (1974)
R. Brooks and A. Geoffrion, “Finding Everett’s Lagrange multipliers by linear programming”, Operations Research 14 (1966) 1149–1153. (10.1287/opre.14.6.1149) / Operations Research by R. Brooks (1966)
Dakin, R.J., “A free search algorithm for mixed integer programming problems”, Computer Journal, 8 (1965) 250–255. (10.1093/comjnl/8.3.250) / Computer Journal by R.J. Dakin (1965)
N.J. Driebeek, “An algorithm for the solution of mixed integer programming problems”, Management Science 12 (1966) 576–587. (10.1287/mnsc.12.7.576) / Management Science by N.J. Driebeek (1966)
Everett, H.M., “Generalized Lagrange multiplier method for solving problems of optimum allocation of resources”, Operations Research 11 (1966) 399–417. (10.1287/opre.11.3.399) / Operations Research by H.M. Everett (1966)
M.L. Fisher, “Optimal solution of scheduling problems using Lagrange multipliers: Part I”, Operations Research 21 (1973) 1114–1127. (10.1287/opre.21.5.1114) / Operations Research by M.L. Fisher (1973)
M.L. Fisher, “A dual algorithm for the one-machine scheduling problem”, Graduate School of Business Rept., University of Chicago, Chicago, Ill. (1974). / A dual algorithm for the one-machine scheduling problem / Graduate School of Business Rept. by M.L. Fisher (1974)
M.L. Fisher, W.D. Northup and J.F. Shapiro, “Using duality to solve discrete optimization problems: Theory and computational experience”, Working Paper OR 030-74, Operations Research Center, M.I.T. (1974).
M.L. Fisher and L. Schrage, “Using Lagrange multipliers to schedule elective hospital admissions”, Working Paper, University of Chicago, Chicago, Ill. (1972). / Using Lagrange multipliers to schedule elective hospital admissions / Working Paper by M.L. Fisher (1972)
M.L. Fisher and J.F. Shapiro, “Constructive duality in integer programming”, SIAM Journal on Applied Mathematics, to appear. (10.1137/0127003)
J.J.H. Forrest, J.P.H. Hirst and J.A. Tomlin, “Practical solution of large mixed integer programming problems with UMPIRE”, Management Science 20 (1974) 733–773. (10.1287/mnsc.20.5.736) / Management Science by J.J.H. Forrest (1974)
A.M. Geoffrion, “An improved implicit enumeration approach for integer programming”, Operations Research 17 (1969) 437–454. (10.1287/opre.17.3.437) / Operations Research by A.M. Geoffrion (1969)
A.M. Geoffrion, “Duality in nonlinear programming”, SIAM Review 13 (1971) 1–37. (10.1137/1013001) / SIAM Review by A.M. Geoffrion (1971)
A.M. Geoffrion and R.E. Marsten, “Integer programming algorithms: A framework and state-of-the-art survey”, Management Science 18 (1972) 465–491. (10.1287/mnsc.18.9.465) / Management Science by A.M. Geoffrion (1972)
A.M. Geoffrion and R.D. McBride, “The capacitated facility location problem with additional constraints”, paper presented to the Joint National Meeting of AIIE, ORSA, and TIMS, Atlantic City, November 8–10, 1972.
F. Glover, “A multiphase-dual algorithm for the zero-one integer programming problem”, Operations Research 13 (1965) 879–919. (10.1287/opre.13.6.879) / Operations Research by F. Glover (1965)
F. Glover, “Surrogate constraints”, Operations Research 16 (1968) 741–749. (10.1287/opre.16.4.741) / Operations Research by F. Glover (1968)
H.J. Greenberg and T.C. Robbins, “Finding Everett’s Lagrange multipliers by Generalized Linear Programming, Parts I, II, and III”, Tech. Rept. CP-70008, Computer Science/Operations Research Center, Southern Methodist University, Dallas, Tex. revised (June 1972). / Finding Everett’s Lagrange multipliers by Generalized Linear Programming, Parts I, II, and III / Tech. Rept. CP-70008 by H.J. Greenberg (1972)
W.C. Healy, Jr., “Multiple choice programming”, Operations Research 12 (1964) 122–138. (10.1287/opre.12.1.122) / Operations Research by W.C. Healy (1964)
M. Held and R.M. Karp, “The traveling salesman problem and minimum spanning trees”, Operations Research 18 (1970) 1138–1162. (10.1287/opre.18.6.1138) / Operations Research by M. Held (1970)
M. Held and R.M. Karp, “The traveling salesman problem and minimum spanning trees: Part II”, Mathematical Programming 1 (1971) 6–25. (10.1007/BF01584070) / Mathematical Programming by M. Held (1971)
M. Held, P. Wolfe and H.P. Crowder, “Validation of subgradient optimization”, Mathematical Sciences Department, IBM Watson Research Center, Yorktown Heights, N.Y. (August 1973). / Validation of subgradient optimization by M. Held (1973)
W.W. Hogan, R.E. Marsten and J.W. Blankenship, “The BOXSTEP method for large scale optimization”, Working Paper 660-73, Sloan School of Management, M.I.T. (December 1973).
R.E. Marsten, private communication (August 22, 1973).
G.L. Nemhauser and Z. Ullman, “A note on the generalized Lagrange multiplier solution to an integer programming problem”, Operations Research 16 (1968) 450–452. (10.1287/opre.16.2.450) / Operations Research by G.L. Nemhauser (1968)
G.T. Ross and R.M. Soland, “A branch and bound algorithm for the generalized assignment problem”, Mathematical Programming, to appear. (10.1007/BF01580430)
J.F. Shapiro, “Generalized Lagrange multipliers in integer programming”, Operations Research 19 (1971) 68–76. (10.1287/opre.19.1.68) / Operations Research by J.F. Shapiro (1971)
J.A. Tomlin, “An improved branch and bound method for integer programming”, Operations Research 19 (1971) 1070–1075. (10.1287/opre.19.4.1070) / Operations Research by J.A. Tomlin (1971)
J.A. Tomlin, “Branch and bound methods for integer and non-convex programming”, in: J. Abadie, ed., Integer and nonlinear programming (North-Holland, Amsterdam, 1970). / Integer and nonlinear programming by J.A. Tomlin (1970)
A.F. Veinott and G.B. Dantzig, “Integral extreme points”, SIAM Review 10 (1968) 371–372. (10.1137/1010063) / SIAM Review by A.F. Veinott (1968)

Dates

Type	When
Created	13 years, 6 months ago (Feb. 22, 2012, 4:55 p.m.)
Deposited	4 years, 8 months ago (Dec. 9, 2020, 4:59 p.m.)
Indexed	1 week, 3 days ago (Aug. 21, 2025, 2:12 p.m.)
Issued	51 years, 8 months ago (Jan. 1, 1974)
Published	51 years, 8 months ago (Jan. 1, 1974)
Published Online	16 years, 6 months ago (Feb. 23, 2009)
Published Print	51 years, 8 months ago (Jan. 1, 1974)

Funders 0

None

BibTeX

@inbook{Geoffrion_1974, title={Lagrangean relaxation for integer programming}, ISBN={9783642007408}, ISSN={0303-3929}, url={http://dx.doi.org/10.1007/bfb0120690}, DOI={10.1007/bfb0120690}, booktitle={Approaches to Integer Programming}, publisher={Springer Berlin Heidelberg}, author={Geoffrion, A. M.}, year={1974}, pages={82–114} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        8,
        21
      ]
    ],
    "date-time": "2025-08-21T18:12:25Z",
    "timestamp": 1755799945469
  },
  "publisher-location": "Berlin, Heidelberg",
  "reference-count": 30,
  "publisher": "Springer Berlin Heidelberg",
  "isbn-type": [
    {
      "type": "print",
      "value": "9783642007392"
    },
    {
      "type": "electronic",
      "value": "9783642007408"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1974
      ]
    ]
  },
  "DOI": "10.1007/bfb0120690",
  "type": "book-chapter",
  "created": {
    "date-parts": [
      [
        2012,
        2,
        22
      ]
    ],
    "date-time": "2012-02-22T21:55:51Z",
    "timestamp": 1329947751000
  },
  "page": "82-114",
  "source": "Crossref",
  "is-referenced-by-count": 1015,
  "title": "Lagrangean relaxation for integer programming",
  "prefix": "10.1007",
  "author": [
    {
      "given": "A. M.",
      "family": "Geoffrion",
      "sequence": "first",
      "affiliation": []
    }
  ],
  "member": "297",
  "published-online": {
    "date-parts": [
      [
        2009,
        2,
        23
      ]
    ]
  },
  "reference": [
    {
      "key": "4_CR1",
      "doi-asserted-by": "publisher",
      "first-page": "212",
      "DOI": "10.1007/BF01580237",
      "volume": "6",
      "author": "R.D. Armstrong",
      "year": "1974",
      "unstructured": "R.D. Armstrong and P. Sinha, \u201cImproved penalty calculations for a mixed integer branch-and-bound algorithm\u201d, Mathematical Programming 6 (1974) 212\u2013223.",
      "journal-title": "Mathematical Programming"
    },
    {
      "key": "4_CR2",
      "doi-asserted-by": "publisher",
      "first-page": "1149",
      "DOI": "10.1287/opre.14.6.1149",
      "volume": "14",
      "author": "R. Brooks",
      "year": "1966",
      "unstructured": "R. Brooks and A. Geoffrion, \u201cFinding Everett\u2019s Lagrange multipliers by linear programming\u201d, Operations Research 14 (1966) 1149\u20131153.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR3",
      "doi-asserted-by": "publisher",
      "first-page": "250",
      "DOI": "10.1093/comjnl/8.3.250",
      "volume": "8",
      "author": "R.J. Dakin",
      "year": "1965",
      "unstructured": "Dakin, R.J., \u201cA free search algorithm for mixed integer programming problems\u201d, Computer Journal, 8 (1965) 250\u2013255.",
      "journal-title": "Computer Journal"
    },
    {
      "key": "4_CR4",
      "doi-asserted-by": "publisher",
      "first-page": "576",
      "DOI": "10.1287/mnsc.12.7.576",
      "volume": "12",
      "author": "N.J. Driebeek",
      "year": "1966",
      "unstructured": "N.J. Driebeek, \u201cAn algorithm for the solution of mixed integer programming problems\u201d, Management Science 12 (1966) 576\u2013587.",
      "journal-title": "Management Science"
    },
    {
      "key": "4_CR5",
      "doi-asserted-by": "publisher",
      "first-page": "399",
      "DOI": "10.1287/opre.11.3.399",
      "volume": "11",
      "author": "H.M. Everett",
      "year": "1966",
      "unstructured": "Everett, H.M., \u201cGeneralized Lagrange multiplier method for solving problems of optimum allocation of resources\u201d, Operations Research 11 (1966) 399\u2013417.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR6",
      "doi-asserted-by": "publisher",
      "first-page": "1114",
      "DOI": "10.1287/opre.21.5.1114",
      "volume": "21",
      "author": "M.L. Fisher",
      "year": "1973",
      "unstructured": "M.L. Fisher, \u201cOptimal solution of scheduling problems using Lagrange multipliers: Part I\u201d, Operations Research 21 (1973) 1114\u20131127.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR7",
      "series-title": "Graduate School of Business Rept.",
      "volume-title": "A dual algorithm for the one-machine scheduling problem",
      "author": "M.L. Fisher",
      "year": "1974",
      "unstructured": "M.L. Fisher, \u201cA dual algorithm for the one-machine scheduling problem\u201d, Graduate School of Business Rept., University of Chicago, Chicago, Ill. (1974)."
    },
    {
      "key": "4_CR8",
      "unstructured": "M.L. Fisher, W.D. Northup and J.F. Shapiro, \u201cUsing duality to solve discrete optimization problems: Theory and computational experience\u201d, Working Paper OR 030-74, Operations Research Center, M.I.T. (1974)."
    },
    {
      "key": "4_CR9",
      "series-title": "Working Paper",
      "volume-title": "Using Lagrange multipliers to schedule elective hospital admissions",
      "author": "M.L. Fisher",
      "year": "1972",
      "unstructured": "M.L. Fisher and L. Schrage, \u201cUsing Lagrange multipliers to schedule elective hospital admissions\u201d, Working Paper, University of Chicago, Chicago, Ill. (1972)."
    },
    {
      "key": "4_CR10",
      "doi-asserted-by": "crossref",
      "unstructured": "M.L. Fisher and J.F. Shapiro, \u201cConstructive duality in integer programming\u201d, SIAM Journal on Applied Mathematics, to appear.",
      "DOI": "10.1137/0127003"
    },
    {
      "key": "4_CR11",
      "doi-asserted-by": "publisher",
      "first-page": "733",
      "DOI": "10.1287/mnsc.20.5.736",
      "volume": "20",
      "author": "J.J.H. Forrest",
      "year": "1974",
      "unstructured": "J.J.H. Forrest, J.P.H. Hirst and J.A. Tomlin, \u201cPractical solution of large mixed integer programming problems with UMPIRE\u201d, Management Science 20 (1974) 733\u2013773.",
      "journal-title": "Management Science"
    },
    {
      "key": "4_CR12",
      "doi-asserted-by": "publisher",
      "first-page": "437",
      "DOI": "10.1287/opre.17.3.437",
      "volume": "17",
      "author": "A.M. Geoffrion",
      "year": "1969",
      "unstructured": "A.M. Geoffrion, \u201cAn improved implicit enumeration approach for integer programming\u201d, Operations Research 17 (1969) 437\u2013454.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR13",
      "doi-asserted-by": "publisher",
      "first-page": "1",
      "DOI": "10.1137/1013001",
      "volume": "13",
      "author": "A.M. Geoffrion",
      "year": "1971",
      "unstructured": "A.M. Geoffrion, \u201cDuality in nonlinear programming\u201d, SIAM Review 13 (1971) 1\u201337.",
      "journal-title": "SIAM Review"
    },
    {
      "key": "4_CR14",
      "doi-asserted-by": "publisher",
      "first-page": "465",
      "DOI": "10.1287/mnsc.18.9.465",
      "volume": "18",
      "author": "A.M. Geoffrion",
      "year": "1972",
      "unstructured": "A.M. Geoffrion and R.E. Marsten, \u201cInteger programming algorithms: A framework and state-of-the-art survey\u201d, Management Science 18 (1972) 465\u2013491.",
      "journal-title": "Management Science"
    },
    {
      "key": "4_CR15",
      "unstructured": "A.M. Geoffrion and R.D. McBride, \u201cThe capacitated facility location problem with additional constraints\u201d, paper presented to the Joint National Meeting of AIIE, ORSA, and TIMS, Atlantic City, November 8\u201310, 1972."
    },
    {
      "key": "4_CR16",
      "doi-asserted-by": "publisher",
      "first-page": "879",
      "DOI": "10.1287/opre.13.6.879",
      "volume": "13",
      "author": "F. Glover",
      "year": "1965",
      "unstructured": "F. Glover, \u201cA multiphase-dual algorithm for the zero-one integer programming problem\u201d, Operations Research 13 (1965) 879\u2013919.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR17",
      "doi-asserted-by": "publisher",
      "first-page": "741",
      "DOI": "10.1287/opre.16.4.741",
      "volume": "16",
      "author": "F. Glover",
      "year": "1968",
      "unstructured": "F. Glover, \u201cSurrogate constraints\u201d, Operations Research 16 (1968) 741\u2013749.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR18",
      "series-title": "Tech. Rept. CP-70008",
      "volume-title": "Finding Everett\u2019s Lagrange multipliers by Generalized Linear Programming, Parts I, II, and III",
      "author": "H.J. Greenberg",
      "year": "1972",
      "unstructured": "H.J. Greenberg and T.C. Robbins, \u201cFinding Everett\u2019s Lagrange multipliers by Generalized Linear Programming, Parts I, II, and III\u201d, Tech. Rept. CP-70008, Computer Science/Operations Research Center, Southern Methodist University, Dallas, Tex. revised (June 1972)."
    },
    {
      "key": "4_CR19",
      "doi-asserted-by": "publisher",
      "first-page": "122",
      "DOI": "10.1287/opre.12.1.122",
      "volume": "12",
      "author": "W.C. Healy",
      "year": "1964",
      "unstructured": "W.C. Healy, Jr., \u201cMultiple choice programming\u201d, Operations Research 12 (1964) 122\u2013138.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR20",
      "doi-asserted-by": "publisher",
      "first-page": "1138",
      "DOI": "10.1287/opre.18.6.1138",
      "volume": "18",
      "author": "M. Held",
      "year": "1970",
      "unstructured": "M. Held and R.M. Karp, \u201cThe traveling salesman problem and minimum spanning trees\u201d, Operations Research 18 (1970) 1138\u20131162.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR21",
      "doi-asserted-by": "publisher",
      "first-page": "6",
      "DOI": "10.1007/BF01584070",
      "volume": "1",
      "author": "M. Held",
      "year": "1971",
      "unstructured": "M. Held and R.M. Karp, \u201cThe traveling salesman problem and minimum spanning trees: Part II\u201d, Mathematical Programming 1 (1971) 6\u201325.",
      "journal-title": "Mathematical Programming"
    },
    {
      "key": "4_CR22",
      "volume-title": "Validation of subgradient optimization",
      "author": "M. Held",
      "year": "1973",
      "unstructured": "M. Held, P. Wolfe and H.P. Crowder, \u201cValidation of subgradient optimization\u201d, Mathematical Sciences Department, IBM Watson Research Center, Yorktown Heights, N.Y. (August 1973)."
    },
    {
      "key": "4_CR23",
      "unstructured": "W.W. Hogan, R.E. Marsten and J.W. Blankenship, \u201cThe BOXSTEP method for large scale optimization\u201d, Working Paper 660-73, Sloan School of Management, M.I.T. (December 1973)."
    },
    {
      "key": "4_CR24",
      "unstructured": "R.E. Marsten, private communication (August 22, 1973)."
    },
    {
      "key": "4_CR25",
      "doi-asserted-by": "publisher",
      "first-page": "450",
      "DOI": "10.1287/opre.16.2.450",
      "volume": "16",
      "author": "G.L. Nemhauser",
      "year": "1968",
      "unstructured": "G.L. Nemhauser and Z. Ullman, \u201cA note on the generalized Lagrange multiplier solution to an integer programming problem\u201d, Operations Research 16 (1968) 450\u2013452.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR26",
      "doi-asserted-by": "crossref",
      "unstructured": "G.T. Ross and R.M. Soland, \u201cA branch and bound algorithm for the generalized assignment problem\u201d, Mathematical Programming, to appear.",
      "DOI": "10.1007/BF01580430"
    },
    {
      "key": "4_CR27",
      "doi-asserted-by": "publisher",
      "first-page": "68",
      "DOI": "10.1287/opre.19.1.68",
      "volume": "19",
      "author": "J.F. Shapiro",
      "year": "1971",
      "unstructured": "J.F. Shapiro, \u201cGeneralized Lagrange multipliers in integer programming\u201d, Operations Research 19 (1971) 68\u201376.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR28",
      "doi-asserted-by": "publisher",
      "first-page": "1070",
      "DOI": "10.1287/opre.19.4.1070",
      "volume": "19",
      "author": "J.A. Tomlin",
      "year": "1971",
      "unstructured": "J.A. Tomlin, \u201cAn improved branch and bound method for integer programming\u201d, Operations Research 19 (1971) 1070\u20131075.",
      "journal-title": "Operations Research"
    },
    {
      "key": "4_CR29",
      "volume-title": "Integer and nonlinear programming",
      "author": "J.A. Tomlin",
      "year": "1970",
      "unstructured": "J.A. Tomlin, \u201cBranch and bound methods for integer and non-convex programming\u201d, in: J. Abadie, ed., Integer and nonlinear programming (North-Holland, Amsterdam, 1970)."
    },
    {
      "key": "4_CR30",
      "doi-asserted-by": "publisher",
      "first-page": "371",
      "DOI": "10.1137/1010063",
      "volume": "10",
      "author": "A.F. Veinott",
      "year": "1968",
      "unstructured": "A.F. Veinott and G.B. Dantzig, \u201cIntegral extreme points\u201d, SIAM Review 10 (1968) 371\u2013372.",
      "journal-title": "SIAM Review"
    }
  ],
  "container-title": "Mathematical Programming Studies",
  "original-title": [],
  "link": [
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/BFb0120690.pdf",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2020,
        12,
        9
      ]
    ],
    "date-time": "2020-12-09T21:59:25Z",
    "timestamp": 1607551165000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://link.springer.com/10.1007/BFb0120690"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1974
      ]
    ]
  },
  "ISBN": [
    "9783642007392",
    "9783642007408"
  ],
  "references-count": 30,
  "URL": "http://dx.doi.org/10.1007/BFb0120690",
  "relation": {},
  "ISSN": [
    "0303-3929"
  ],
  "subject": [],
  "published": {
    "date-parts": [
      [
        1974
      ]
    ]
  }
}