DOI: 10.1007/bf02568608. A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem

A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem

10.1007/bf02568608

Crossref journal-article

Springer Science and Business Media LLC

Top (297)

Bibliography

Caprara, A., & GonzÃ¡lez, J. J. S. (1996). A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem. Top, 4(1), 135â163.

Authors 2

A. Caprara (first)
J. J. Salazar González (additional)

References 20 Referenced 18

Bilde, O. and J. Krarup (1977). “Sharp Lower Bounds and Efficient algorithms for the Simple Plant Location Problem”,Annals of Discrete Mathematics 1, 79–97. (10.1016/S0167-5060(08)70728-3) / Annals of Discrete Mathematics by O. Bilde (1977)
Balas, E. and M.W. Padberg (1976). “Set Partitioning: A survey”,SIAM Review 18, 710–760. (10.1137/1018115) / SIAM Review by E. Balas (1976)
Caprara, A. and M. Fischetti (1993). “Odd-Cut Sets, Odd Cycles, and 0–1/2 Chvátal-gomory cuts”, working paper, University of Bologna.
Caprara, A., M. Fischetti and D. Maio, (1995). “Exact and Approximate Algorithms for the Index Selection Problem in Physical Database Design”,IEEE Transactions on Knowledge and Data Engineering 7, 955–967. (10.1109/69.476501) / IEEE Transactions on Knowledge and Data Engineering by A. Caprara (1995)
Ceria, S. (1994). “Solving Mixed Integer Programs with General Cutting Planes”, talk presented at the workshopSolving Large and Complex Optimization Problems, Giens.
Cho, D.C., E.L. Johnson, M.W. Padberg and M.R. Rao, (1983). “On the Uncapacitated Plant Location Problem. I: valid Inequalities and Faces”,Mathematics of Operations Research 8, 579–589. (10.1287/moor.8.4.579) / Mathematics of Operations Research by D.C. Cho (1983)
Cho, D.C., M.W. Padberg and M.R. Rao, (1983) “On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems”,Mathematics of Operations Research 8, 590–612. (10.1287/moor.8.4.590) / Mathematics of Operations Research by D.C. Cho (1983)
Conn, A.R. and G. Cornuejols (1990). “A Projection Method for the Uncapacitated Facility Location Problem”,Mathematical Programming 46, 273–298. (10.1007/BF01585746) / Mathematical Programming by A.R. Conn (1990)
Cornuejols, G., G.L. Nemhauser and L.A. Wolsey (1991). “The Uncapacitated Facility Location Problem”, in P.B. Mirchandani, R.L. Francis.Discrete Location Theory, John Wiley.
Conuejols, G. and J.M. Thizy, (1982). “Some Facets of the Simple Plant Location Polytope”,Mathematical Programming 23, 50–74. (10.1007/BF01583779) / Mathematical Programming by G. Conuejols (1982)
Cornuejols, G. and J.M. Thizy (1982). “A Primal Approach to the Simple Plant Location Problem”,SIAM Journal on Algebraic and Discrete Methods 3, 504–510. (10.1137/0603051) / SIAM Journal on Algebraic and Discrete Methods by G. Cornuejols (1982)
Erlenkotter, D. (1978). “A Dual-Based Procedure for Uncapacitated Facility Location”.Operations Research 26, 992–1009. (10.1287/opre.26.6.992) / Operations Research by D. Erlenkotter (1978)
Finkelstein, S., M. Schkolnick and P. Tiberio (1988). “Physical Database Design for Relational Databases”,ACM Transactions on Database Systems 13, 91–128. (10.1145/42201.42205) / ACM Transactions on Database Systems by S. Finkelstein (1988)
Grötschel, M., L. Lovász and A. Schrijver (1988).Geometric Algorithms and Combinatorial Optimization, Springer-Verlag. (10.1007/978-3-642-97881-4)
Guignard, M. (1980). “Fractional Vertices, Cuts and Facets of the Simple Plant Location Problem”,Mathematical Programming Study 12, 150–162. (10.1007/BFb0120893) / Mathematical Programming Study by M. Guignard (1980)
Krarup, J. and P.M. Pruzan (1983). “The Simple Plant Location Problem: Survey and Synthesis”,European Journal of Operational Research 12, 36–81. (10.1016/0377-2217(83)90181-9) / European Journal of Operational Research by J. Krarup (1983)
Morris, J.G. (1978). “On the Extent to Which Certain Fixed-Charge Depot Location. Problems Can Be Solved by LP”,Journal of the Operational Research Society 29, 71–76. (10.1057/jors.1978.10) / Journal of the Operational Research Society by J.G. Morris (1978)
Nemhauser, G.L. and G. Sigismondi (1992). “A Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing”,Journal of Operational Research Society 43, 443–457. (10.1057/jors.1992.71) / Journal of Operational Research Society by G.L. Nemhauser (1992)
Padberg, M.W. (1973). “On the Facial Structure of Set Packing Problems”,Mathematical Programming 5, 199–215. (10.1007/BF01580121) / Mathematical Programming by M.W. Padberg (1973)
Padberg, M.W. and G. Rinaldi (1991). “A Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems”,SIAM Review 33, 60–100. (10.1137/1033004) / SIAM Review by M.W. Padberg (1991)

Dates

Type	When
Created	18 years, 5 months ago (March 22, 2007, 1:48 p.m.)
Deposited	6 years, 3 months ago (May 19, 2019, 6:44 p.m.)
Indexed	1 month ago (July 25, 2025, 6:33 a.m.)
Issued	29 years, 2 months ago (June 1, 1996)
Published	29 years, 2 months ago (June 1, 1996)
Published Print	29 years, 2 months ago (June 1, 1996)

Funders 0

None

BibTeX

@article{Caprara_1996, title={A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem}, volume={4}, ISSN={1863-8279}, url={http://dx.doi.org/10.1007/bf02568608}, DOI={10.1007/bf02568608}, number={1}, journal={Top}, publisher={Springer Science and Business Media LLC}, author={Caprara, A. and González, J. J. Salazar}, year={1996}, month=jun, pages={135–163} }

JSON

{
  "indexed": {
    "date-parts": [
      [
        2025,
        7,
        25
      ]
    ],
    "date-time": "2025-07-25T10:33:08Z",
    "timestamp": 1753439588116
  },
  "reference-count": 20,
  "publisher": "Springer Science and Business Media LLC",
  "issue": "1",
  "license": [
    {
      "start": {
        "date-parts": [
          [
            1996,
            6,
            1
          ]
        ],
        "date-time": "1996-06-01T00:00:00Z",
        "timestamp": 833587200000
      },
      "content-version": "tdm",
      "delay-in-days": 0,
      "URL": "http://www.springer.com/tdm"
    }
  ],
  "content-domain": {
    "domain": [],
    "crossmark-restriction": false
  },
  "published-print": {
    "date-parts": [
      [
        1996,
        6
      ]
    ]
  },
  "DOI": "10.1007/bf02568608",
  "type": "journal-article",
  "created": {
    "date-parts": [
      [
        2007,
        3,
        22
      ]
    ],
    "date-time": "2007-03-22T17:48:33Z",
    "timestamp": 1174585713000
  },
  "page": "135-163",
  "source": "Crossref",
  "is-referenced-by-count": 18,
  "title": "A branch-and-cut algorithm for a generalization of the Uncapacitated Facility Location Problem",
  "prefix": "10.1007",
  "volume": "4",
  "author": [
    {
      "given": "A.",
      "family": "Caprara",
      "sequence": "first",
      "affiliation": []
    },
    {
      "given": "J. J. Salazar",
      "family": "Gonz\u00e1lez",
      "sequence": "additional",
      "affiliation": []
    }
  ],
  "member": "297",
  "reference": [
    {
      "key": "BF02568608_CR1",
      "doi-asserted-by": "crossref",
      "first-page": "79",
      "DOI": "10.1016/S0167-5060(08)70728-3",
      "volume": "1",
      "author": "O. Bilde",
      "year": "1977",
      "unstructured": "Bilde, O. and J. Krarup (1977). \u201cSharp Lower Bounds and Efficient algorithms for the Simple Plant Location Problem\u201d,Annals of Discrete Mathematics 1, 79\u201397.",
      "journal-title": "Annals of Discrete Mathematics"
    },
    {
      "key": "BF02568608_CR2",
      "doi-asserted-by": "crossref",
      "first-page": "710",
      "DOI": "10.1137/1018115",
      "volume": "18",
      "author": "E. Balas",
      "year": "1976",
      "unstructured": "Balas, E. and M.W. Padberg (1976). \u201cSet Partitioning: A survey\u201d,SIAM Review 18, 710\u2013760.",
      "journal-title": "SIAM Review"
    },
    {
      "key": "BF02568608_CR3",
      "unstructured": "Caprara, A. and M. Fischetti (1993). \u201cOdd-Cut Sets, Odd Cycles, and 0\u20131/2 Chv\u00e1tal-gomory cuts\u201d, working paper, University of Bologna."
    },
    {
      "key": "BF02568608_CR4",
      "doi-asserted-by": "crossref",
      "first-page": "955",
      "DOI": "10.1109/69.476501",
      "volume": "7",
      "author": "A. Caprara",
      "year": "1995",
      "unstructured": "Caprara, A., M. Fischetti and D. Maio, (1995). \u201cExact and Approximate Algorithms for the Index Selection Problem in Physical Database Design\u201d,IEEE Transactions on Knowledge and Data Engineering 7, 955\u2013967.",
      "journal-title": "IEEE Transactions on Knowledge and Data Engineering"
    },
    {
      "key": "BF02568608_CR5",
      "unstructured": "Ceria, S. (1994). \u201cSolving Mixed Integer Programs with General Cutting Planes\u201d, talk presented at the workshopSolving Large and Complex Optimization Problems, Giens."
    },
    {
      "key": "BF02568608_CR6",
      "doi-asserted-by": "crossref",
      "first-page": "579",
      "DOI": "10.1287/moor.8.4.579",
      "volume": "8",
      "author": "D.C. Cho",
      "year": "1983",
      "unstructured": "Cho, D.C., E.L. Johnson, M.W. Padberg and M.R. Rao, (1983). \u201cOn the Uncapacitated Plant Location Problem. I: valid Inequalities and Faces\u201d,Mathematics of Operations Research 8, 579\u2013589.",
      "journal-title": "Mathematics of Operations Research"
    },
    {
      "key": "BF02568608_CR7",
      "doi-asserted-by": "crossref",
      "first-page": "590",
      "DOI": "10.1287/moor.8.4.590",
      "volume": "8",
      "author": "D.C. Cho",
      "year": "1983",
      "unstructured": "Cho, D.C., M.W. Padberg and M.R. Rao, (1983) \u201cOn the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems\u201d,Mathematics of Operations Research 8, 590\u2013612.",
      "journal-title": "Mathematics of Operations Research"
    },
    {
      "key": "BF02568608_CR8",
      "doi-asserted-by": "crossref",
      "first-page": "273",
      "DOI": "10.1007/BF01585746",
      "volume": "46",
      "author": "A.R. Conn",
      "year": "1990",
      "unstructured": "Conn, A.R. and G. Cornuejols (1990). \u201cA Projection Method for the Uncapacitated Facility Location Problem\u201d,Mathematical Programming 46, 273\u2013298.",
      "journal-title": "Mathematical Programming"
    },
    {
      "key": "BF02568608_CR9",
      "unstructured": "Cornuejols, G., G.L. Nemhauser and L.A. Wolsey (1991). \u201cThe Uncapacitated Facility Location Problem\u201d, in P.B. Mirchandani, R.L. Francis.Discrete Location Theory, John Wiley."
    },
    {
      "key": "BF02568608_CR10",
      "doi-asserted-by": "crossref",
      "first-page": "50",
      "DOI": "10.1007/BF01583779",
      "volume": "23",
      "author": "G. Conuejols",
      "year": "1982",
      "unstructured": "Conuejols, G. and J.M. Thizy, (1982). \u201cSome Facets of the Simple Plant Location Polytope\u201d,Mathematical Programming 23, 50\u201374.",
      "journal-title": "Mathematical Programming"
    },
    {
      "key": "BF02568608_CR11",
      "doi-asserted-by": "crossref",
      "first-page": "504",
      "DOI": "10.1137/0603051",
      "volume": "3",
      "author": "G. Cornuejols",
      "year": "1982",
      "unstructured": "Cornuejols, G. and J.M. Thizy (1982). \u201cA Primal Approach to the Simple Plant Location Problem\u201d,SIAM Journal on Algebraic and Discrete Methods 3, 504\u2013510.",
      "journal-title": "SIAM Journal on Algebraic and Discrete Methods"
    },
    {
      "key": "BF02568608_CR12",
      "doi-asserted-by": "crossref",
      "first-page": "992",
      "DOI": "10.1287/opre.26.6.992",
      "volume": "26",
      "author": "D. Erlenkotter",
      "year": "1978",
      "unstructured": "Erlenkotter, D. (1978). \u201cA Dual-Based Procedure for Uncapacitated Facility Location\u201d.Operations Research 26, 992\u20131009.",
      "journal-title": "Operations Research"
    },
    {
      "key": "BF02568608_CR13",
      "doi-asserted-by": "crossref",
      "first-page": "91",
      "DOI": "10.1145/42201.42205",
      "volume": "13",
      "author": "S. Finkelstein",
      "year": "1988",
      "unstructured": "Finkelstein, S., M. Schkolnick and P. Tiberio (1988). \u201cPhysical Database Design for Relational Databases\u201d,ACM Transactions on Database Systems 13, 91\u2013128.",
      "journal-title": "ACM Transactions on Database Systems"
    },
    {
      "key": "BF02568608_CR14",
      "doi-asserted-by": "crossref",
      "unstructured": "Gr\u00f6tschel, M., L. Lov\u00e1sz and A. Schrijver (1988).Geometric Algorithms and Combinatorial Optimization, Springer-Verlag.",
      "DOI": "10.1007/978-3-642-97881-4"
    },
    {
      "key": "BF02568608_CR15",
      "doi-asserted-by": "crossref",
      "first-page": "150",
      "DOI": "10.1007/BFb0120893",
      "volume": "12",
      "author": "M. Guignard",
      "year": "1980",
      "unstructured": "Guignard, M. (1980). \u201cFractional Vertices, Cuts and Facets of the Simple Plant Location Problem\u201d,Mathematical Programming Study 12, 150\u2013162.",
      "journal-title": "Mathematical Programming Study"
    },
    {
      "key": "BF02568608_CR16",
      "doi-asserted-by": "crossref",
      "first-page": "36",
      "DOI": "10.1016/0377-2217(83)90181-9",
      "volume": "12",
      "author": "J. Krarup",
      "year": "1983",
      "unstructured": "Krarup, J. and P.M. Pruzan (1983). \u201cThe Simple Plant Location Problem: Survey and Synthesis\u201d,European Journal of Operational Research 12, 36\u201381.",
      "journal-title": "European Journal of Operational Research"
    },
    {
      "key": "BF02568608_CR17",
      "doi-asserted-by": "crossref",
      "first-page": "71",
      "DOI": "10.1057/jors.1978.10",
      "volume": "29",
      "author": "J.G. Morris",
      "year": "1978",
      "unstructured": "Morris, J.G. (1978). \u201cOn the Extent to Which Certain Fixed-Charge Depot Location. Problems Can Be Solved by LP\u201d,Journal of the Operational Research Society 29, 71\u201376.",
      "journal-title": "Journal of the Operational Research Society"
    },
    {
      "key": "BF02568608_CR18",
      "doi-asserted-by": "crossref",
      "first-page": "443",
      "DOI": "10.1057/jors.1992.71",
      "volume": "43",
      "author": "G.L. Nemhauser",
      "year": "1992",
      "unstructured": "Nemhauser, G.L. and G. Sigismondi (1992). \u201cA Strong Cutting Plane/Branch-and-Bound Algorithm for Node Packing\u201d,Journal of Operational Research Society 43, 443\u2013457.",
      "journal-title": "Journal of Operational Research Society"
    },
    {
      "key": "BF02568608_CR19",
      "doi-asserted-by": "crossref",
      "first-page": "199",
      "DOI": "10.1007/BF01580121",
      "volume": "5",
      "author": "M.W. Padberg",
      "year": "1973",
      "unstructured": "Padberg, M.W. (1973). \u201cOn the Facial Structure of Set Packing Problems\u201d,Mathematical Programming 5, 199\u2013215.",
      "journal-title": "Mathematical Programming"
    },
    {
      "key": "BF02568608_CR20",
      "doi-asserted-by": "crossref",
      "first-page": "60",
      "DOI": "10.1137/1033004",
      "volume": "33",
      "author": "M.W. Padberg",
      "year": "1991",
      "unstructured": "Padberg, M.W. and G. Rinaldi (1991). \u201cA Branch-and-Cut Algorithm for the Resolution of Large-Scale Symmetric Traveling Salesman Problems\u201d,SIAM Review 33, 60\u2013100.",
      "journal-title": "SIAM Review"
    }
  ],
  "container-title": "Top",
  "original-title": [],
  "language": "en",
  "link": [
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/BF02568608.pdf",
      "content-type": "application/pdf",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "http://link.springer.com/article/10.1007/BF02568608/fulltext.html",
      "content-type": "text/html",
      "content-version": "vor",
      "intended-application": "text-mining"
    },
    {
      "URL": "http://link.springer.com/content/pdf/10.1007/BF02568608",
      "content-type": "unspecified",
      "content-version": "vor",
      "intended-application": "similarity-checking"
    }
  ],
  "deposited": {
    "date-parts": [
      [
        2019,
        5,
        19
      ]
    ],
    "date-time": "2019-05-19T22:44:03Z",
    "timestamp": 1558305843000
  },
  "score": 1,
  "resource": {
    "primary": {
      "URL": "http://link.springer.com/10.1007/BF02568608"
    }
  },
  "subtitle": [],
  "short-title": [],
  "issued": {
    "date-parts": [
      [
        1996,
        6
      ]
    ]
  },
  "references-count": 20,
  "journal-issue": {
    "issue": "1",
    "published-print": {
      "date-parts": [
        [
          1996,
          6
        ]
      ]
    }
  },
  "alternative-id": [
    "BF02568608"
  ],
  "URL": "http://dx.doi.org/10.1007/BF02568608",
  "relation": {},
  "ISSN": [
    "1134-5764",
    "1863-8279"
  ],
  "subject": [],
  "container-title-short": "Top",
  "published": {
    "date-parts": [
      [
        1996,
        6
      ]
    ]
  }
}