Skip to main content
Disciplines
Automotive Business IT + Informatics Construction + Real Estate Electrical Engineering + Electronics Energy + Sustainability Insurance + Risk Finance + Banking Management + Leadership Marketing + Sales Mechanical Engineering + Materials
Events
DE
EN
Books
Journals
Topic Page
Marketing
Start single access now
Access for companies
EXTENDED SEARCH
Log in
Top
Published in:
Getting Started Read chapter Read first chapter

2014 | OriginalPaper | Chapter

7. Valid Inequalities for Structured Integer Programs

Authors : Michele Conforti, Gérard Cornuéjols, Giacomo Zambelli

Published in: Integer Programming

Publisher: Springer International Publishing

Log in

Activate our intelligent search to find suitable subject content or patents.

search-config
loading …

Abstract

In Chaps. 5 and 6 we have introduced several classes of valid inequalities that can be used to strengthen integer programming formulations in a cutting plane scheme. All these valid inequalities are “general purpose,” in the sense that their derivation does not take into consideration the structure of the specific problem at hand. Many integer programs have an underlying combinatorial structure, which can be exploited to derive “strong” valid inequalities, where the term “strong” typically refers to the fact that the inequality is facet-defining for the convex hull of feasible solutions.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

inform now
previous chapter Intersection Cuts and Corner Polyhedra
next chapter Reformulations and Relaxations
Literature
[1]
K. Aardal, R.E. Bixby, C.A.J. Hurkens, A.K. Lenstra, J.W. Smeltink, Market split and basis reduction: towards a solution of the Cornuéjols–Dawande instances. INFORMS J. Comput. 12, 192–202 (2000)MATHMathSciNet
[2]
K. Aardal, A.K. Lenstra, Hard equality constrained integer knapsacks. Math. Oper. Res. 29, 724–738 (2004); Erratum: Math. Oper. Res. 31, 846 (2006)
[3]
K. Aardal, C. Hurkens, A.K. Lenstra, Solving a system of diophantine equations with lower and upper bounds on the variables. Math. Oper. Res. 25, 427–442 (2000)MATHMathSciNet
[4]
K. Aardal, R. Weismantel, L.A. Wolsey, Non-standard approaches to integer programming. Discrete Appl. Math. 123, 5–74 (2002)MATHMathSciNet
[5]
T. Achterberg, Constraint Integer Programming. Ph.D. thesis, ZIB, Berlin, 2007
[6]
[7]
[8]
[9]
M. Ajtai, The shortest vector problem in L2 is NP-hard for randomized reductions, in Proceedings of the 30th Annual ACM Symposium on Theory of Computing (STOC-98), (1998), pp. 10–19
[10]
F. Alizadeh, Interior point methods in semidefinite programming with applications to combinatorial optimization. SIAM J. Optim. 5, 13–51 (1995)MATHMathSciNet
[11]
K. Andersen, G. Cornuéjols, Y. Li, Split closure and intersection cuts. Math. Program. A 102, 457–493 (2005)MATH
[12]
K. Andersen, Q. Louveaux, R. Weismantel, L.A. Wolsey, Inequalities from two rows of a simplex tableau, in Proceedings of IPCO XII, Ithaca, NY. Lecture Notes in Computer Science, vol. 4513 (2007), pp. 1–15MathSciNet
[13]
D. Applegate, R.E. Bixby, V. Chvátal, W.J. Cook, The Traveling Salesman Problem. A Computational Study (Princeton University Press, Princeton, 2006)
[14]
S. Arora, B. Barak, Complexity Theory: A Modern Approach (Cambridge University Press, Cambridge, 2009)
[15]
A. Atamtürk, Strong formulations of robust mixed 0–1 programming. Math. Program. 108, 235–250 (2006)MATHMathSciNet
[16]
A. Atamtürk, G.L. Nemhauser, M.W.P. Savelsbergh, Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121, 40–55 (2000)MATH
[17]
R.K. Ahuja, T.L. Magnanti, J.B. Orlin, Network Flows (Prentice Hall, New Jersey, 1993)MATH
[18]
G. Averkov, On maximal S-free sets and the Helly number for the family of S-convex sets. SIAM J. Discrete Math. 27(3), 1610–1624 (2013)MATHMathSciNet
[19]
G. Averkov, A. Basu, On the unique lifting property, IPCO 2014, Bonn, Germany, Lecture Notes in Computer Science, 8494, 76–87 (2014)
[20]
D. Avis, K. Fukuda, A pivoting algorithm for convex hulls and vertex enumeration of arrangements and polyhedra. Discrete Comput. Geom. 8, 295–313 (1992)MATHMathSciNet
[21]
A. Bachem, R. von Randow, Integer theorems of Farkas lemma type, in Operations Research Verfahren/ Methods of Operations Research 32, III Symposium on Operations Research, Mannheim 1978, ed. by W. Oettli, F. Steffens (Athenäum, Königstein, 1979), pp. 19–28
[22]
E. Balas, Intersection cuts—a new type of cutting planes for integer programming. Oper. Res. 19, 19–39 (1971)MATHMathSciNet
[23]
E. Balas, Integer programming and convex analysis: intersection cuts from outer polars. Math. Program. 2 330–382 (1972)MATHMathSciNet
[24]
E. Balas, Disjunctive programming: properties of the convex hull of feasible points, GSIA Management Science Research Report MSRR 348, Carnegie Mellon University (1974); Published as invited paper in Discrete Appl. Math. 89, 1–44 (1998)
[25]
[26]
E. Balas, Disjunctive programming and a hierarchy of relaxations for discrete optimization problems. SIAM J. Algebr. Discrete Methods 6, 466–486 (1985)MATHMathSciNet
[27]
[28]
E. Balas, P. Bonami, Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants. Math. Program. Comput. 1, 165–199 (2009)MATHMathSciNet
[29]
E. Balas, S. Ceria, G. Cornuéjols, A lift-and-project cutting plane algorithm for mixed 0–1 programs. Math. Program. 58, 295–324 (1993)MATH
[30]
E. Balas, S. Ceria, G. Cornuéjols, R.N. Natraj, Gomory cuts revisited. Oper. Res. Lett. 19, 1–9 (1996)MATHMathSciNet
[31]
E. Balas, R. Jeroslow, Strengthening cuts for mixed integer programs. Eur. J. Oper. Res. 4, 224–234 (1980)MATHMathSciNet
[32]
E. Balas, M. Perregaard, A precise correspondence between lift-and-project cuts, simple disjunctive cuts and mixed integer Gomory cuts for 0–1 programming. Math. Program. B 94, 221–245 (2003)MATHMathSciNet
[33]
E. Balas, W.R. Pulleyblank, The perfectly matchable subgraph polytope of an arbitrary graph. Combinatorica 9, 321–337 (1989)MATHMathSciNet
[34]
[35]
W. Banaszczyk, A.E. Litvak, A. Pajor, S.J. Szarek, The flatness theorem for nonsymmetric convex bodies via the local theory of Banach spaces. Math. Oper. Res. 24 728–750 (1999)MATHMathSciNet
[36]
F. Barahona, R. Anbil, The volume algorithm: producing primal solutions with a subgradient method. Math. Program. 87, 385–399 (2000)MATHMathSciNet
[37]
I. Barany, T.J. Van Roy, L.A. Wolsey, Uncapacitated lot-sizing: the convex hull of solutions. Math. Program. 22, 32–43 (1984)MATH
[38]
A. Barvinok, A polynomial time algorithm for counting integral points in polyhedra when the dimension is fixed. Math. Oper. Res. 19, 769–779 (1994)MATHMathSciNet
[39]
A. Barvinok, A Course in Convexity. Graduate Studies in Mathematics, vol. 54 (American Mathematical Society, Providence, 2002)
[40]
A. Basu, M. Campelo, M. Conforti, G. Cornuéjols, G. Zambelli, On lifting integer variables in minimal inequalities. Math. Program. A 141, 561–576 (2013)MATH
[41]
A. Basu, M. Conforti, G. Cornuéjols, G. Zambelli, Maximal lattice-free convex sets in linear subspaces. Math. Oper. Res. 35, 704–720 (2010)MATHMathSciNet
[42]
A. Basu, M. Conforti, G. Cornuéjols, G. Zambelli, Minimal inequalities for an infinite relaxation of integer programs. SIAM J. Discrete Math. 24, 158–168 (2010)MATHMathSciNet
[43]
A. Basu, R. Hildebrand, M. Köppe, M. Molinaro, A (k+1)-Slope Theorem for the k-Dimensional Infinite Group Relaxation. SIAM J. Optim. 23(2), 1021–1040 (2013)MATHMathSciNet
[44]
A. Basu, R. Hildebrand, M. Köppe, Equivariant perturbation in Gomory and Johnson infinite group problem III. Foundations for the k-dimensional case with applications to the case k = 2. www.​optimization-online.​org (2014)
[45]
D.E. Bell, A theorem concerning the integer lattice. Stud. Appl. Math. 56, 187–188 (1977)MATH
[46]
R. Bellman, Dynamic Programming (Princeton University Press, Princeton, 1957)MATH
[47]
J.F. Benders, Partitioning procedures for solving mixed variables programming problems. Numerische Mathematik 4, 238–252 (1962)MATHMathSciNet
[48]
M. Bénichou, J.M. Gauthier, P. Girodet, G. Hentges, G. Ribière, O. Vincent, Experiments in mixed-integer linear programming. Math. Program. 1, 76–94 (1971)MATH
[49]
A. Ben-Tal, A.S. Nemirovski, Lectures on Modern Convex Optimization: Analysis, Algorithms, and Engineering Applications. MPS/SIAM Series in Optimization (SIAM, Philadelphia, 2001)
[50]
[51]
D. Bertsimas, R. Weismantel, Optimization over Integers (Dynamic Ideas, Belmont, 2005)
[52]
D. Bienstock, M. Zuckerberg, Subset algebra lift operators for 0–1 integer programming. SIAM J. Optim. 15, 63–95 (2004)MATHMathSciNet
[53]
L.J. Billera, A. Sarangarajan, All 0,1 polytopes are traveling salesman polytopes. Combinatorica 16, 175–188 (1996)MATHMathSciNet
[54]
S. Binato, M.V.F. Pereira, S. Granville, A new Benders decomposition approach to solve power transmission network design problems. IEEE Trans. Power Syst. 16, 235–240 (2001)
[55]
J. R. Birge, F. Louveaux, Introduction to Stochastic Programming (Springer, New York, 2011)MATH
[56]
R.E. Bixby, S. Ceria, C.M. McZeal, M.W.P. Savelsbergh, An updated mixed integer programming library: MIPLIB 3.0. Optima 58, 12–15 (1998)
[57]
R.E. Bixby, M. Fenelon, Z. Gu, E. Rothberg, R. Wunderling, Mixed integer programming: a progress report, in The Sharpest Cut: The Impact of Manfred Padberg and His Work, ed. by M. Grötschel. MPS/SIAM Series in Optimization (2004), pp. 309–326
[58]
P. Bonami, On optimizing over lift-and-project closures. Math. Program. Comput. 4, 151–179 (2012)MATHMathSciNet
[59]
P. Bonami, M. Conforti, G. Cornuéjols, M. Molinaro, G. Zambelli, Cutting planes from two-term disjunctions. Oper. Res. Lett. 41, 442–444 (2013)MATHMathSciNet
[60]
P. Bonami, G. Cornuéjols, S. Dash, M. Fischetti, A. Lodi, Projected Chvátal-Gomory cuts for mixed integer linear programs. Math. Program. 113, 241–257 (2008)MATHMathSciNet
[61]
P. Bonami, F. Margot, Cut generation through binarization, IPCO 2014, eds. by J. Lee, J. Vygen. LNCS, vol 8494 (2014) pp. 174–185
[62]
J.A. Bondy, U.S.R. Murty, Graph Theory (Springer, New York, 2008)MATH
[63]
V. Borozan, G. Cornuéjols, Minimal valid inequalities for integer constraints. Math. Oper. Res. 34, 538–546 (2009)MATHMathSciNet
[64]
O. Briant, C. Lemaréchal, Ph. Meurdesoif, S. Michel, N. Perrot, F. Vanderbeck, Comparison of bundle and classical column generation. Math. Program. 113, 299–344 (2008)MATHMathSciNet
[65]
C.A. Brown, L. Finkelstein, P.W. Purdom, Backtrack Searching in the Presence of Symmetry, Nordic Journal of Computing 3, 203–219 (1996)MathSciNet
[66]
S. Burer, D. Vandenbussche, Solving lift-and-project relaxations of binary integer programs. SIAM J. Optim. 16, 726–750 (2006)MATHMathSciNet
[67]
A. Caprara, M. Fischetti, \(\{0, \frac{1} {2}\}\) Chvátal–Gomory cuts. Math. Program. 74, 221–235 (1996)
[68]
A. Caprara, A.N. Letchford, On the separation of split cuts and related inequalities. Math. Program. B 94, 279–294 (2003)MATHMathSciNet
[69]
R.D. Carr, G. Konjevod, G. Little, V. Natarajan, O. Parekh, Compacting cuts: new linear formulation for minimum cut. ACM Trans. Algorithms 5, 27:1–27:6 (2009)
[70]
E. Chlamtac, M. Tulsiani, Convex relaxations and integrality gaps, in Handbook on Semidefinite, Conic and Polynomial Optimization, International Series in Operations Research and Management Science, Springer, vol. 166 (2012), pp. 139–169MathSciNet
[71]
M. Chudnovsky, G. Cornuéjols, X. Liu, P. Seymour, K. Vusković, Recognizing Berge graphs. Combinatorica 25, 143–186 (2005)MATHMathSciNet
[72]
M. Chudnovsky, N. Robertson, P. Seymour, R. Thomas, The strong perfect graph theorem. Ann. Math. 164, 51–229 (2006)MATHMathSciNet
[73]
V. Chvátal, Edmonds polytopes and a hierarchy of combinatorial optimization. Discrete Math. 4, 305–337 (1973)MATHMathSciNet
[74]
V. Chvátal, On certain polytopes associated with graphs. J. Combin. Theory B 18, 138–154 (1975)MATH
[75]
V. Chvátal, W. Cook, M. Hartmann, On cutting-plane proofs in combinatorial optimization. Linear Algebra Appl. 114/115, 455–499 (1989)
[76]
[77]
M. Conforti, G. Cornuéjols, G. Zambelli, A geometric perspective on lifting. Oper. Res. 59, 569–577 (2011)MATHMathSciNet
[78]
M. Conforti, G. Cornuéjols, G. Zambelli, Equivalence between intersection cuts and the corner polyhedron. Oper. Res. Lett. 38, 153–155 (2010)MATHMathSciNet
[79]
M. Conforti, G. Cornuéjols, G. Zambelli, Extended formulations in combinatorial optimization. 4OR 8, 1–48 (2010)
[80]
M. Conforti, G. Cornuéjols, G. Zambelli, Corner polyhedron and intersection cuts. Surv. Oper. Res. Manag. Sci. 16, 105–120 (2011)
[81]
M. Conforti, M. Di Summa, F. Eisenbrand, L.A. Wolsey, Network formulations of mixed-integer programs. Math. Oper. Res. 34, 194–209 (2009)MATHMathSciNet
[82]
M. Conforti, L.A. Wolsey, Compact formulations as unions of polyhedra. Math. Program. 114, 277–289 (2008)MATHMathSciNet
[83]
M. Conforti, L.A. Wolsey, G. Zambelli, Split, MIR and Gomory inequalities (2012 submitted)
[84]
S.A. Cook, The complexity of theorem-proving procedures, in Proceedings 3rd STOC (Association for Computing Machinery, New York, 1971), pp. 151–158
[85]
W.J. Cook, Fifty-plus years of combinatorial integer programming, in 50 Years of Integer Programming 1958–2008, ed. by M. Jünger et al. (Springer, Berlin, 2010), pp. 387–430
[86]
W.J. Cook, In Pursuit of the Traveling Salesman: Mathematics at the Limits of Computation (Princeton University Press, Princeton, 2012)
[87]
W.J. Cook, W.H. Cunningham, W.R. Pulleyblank, A. Schrijver, Combinatorial Optimization (Wiley, New York, 1998)MATH
[88]
W.J. Cook, S. Dash, R. Fukasawa, M. Goycoolea, Numerically accurate Gomory mixed-integer cuts. INFORMS J. Comput. 21, 641–649 (2009)MATHMathSciNet
[89]
W.J. Cook, J. Fonlupt, A. Schrijver, An integer analogue of Carathéodory’s theorem. J. Combin. Theory B 40, 63–70 (1986)MATHMathSciNet
[90]
W.J. Cook, R. Kannan, A. Schrijver, Chvátal closures for mixed integer programming problems. Math. Program. 47, 155–174 (1990)MATHMathSciNet
[91]
W.J. Cook, T. Rutherford, H.E. Scarf, D. Shallcross, An implementation of the generalized basis reduction algorithm for integer programming. ORSA J. Comput. 5, 206–212 (1993)MATHMathSciNet
[92]
G. Cornuéjols, Combinatorial Optimization: Packing and Covering. SIAM Monograph, CBMS-NSF Regional Conference Series in Applied Mathematics, vol. 74 (2001)
[93]
G. Cornuéjols, M.L. Fisher, G.L. Nemhauser, Location of bank accounts to optimize float: an analytic study of exact and approximate algorithms. Manag. Sci. 23, 789–810 (1977)MATH
[94]
G. Cornuéjols, Y. Li, On the rank of mixed 0,1 polyhedra. Math. Program. A 91, 391–397 (2002)MATH
[95]
G. Cornuéjols, Y. Li, A connection between cutting plane theory and the geometry of numbers. Math. Program. A 93, 123–127 (2002)MATH
[96]
G. Cornuéjols, R. Tütüncü, Optimization Methods in Finance (Cambridge University Press, Cambridge, 2007)MATH
[97]
A.M. Costa, A survey on Benders decomposition applied to fixed-charge network design problems. Comput. Oper. Res. 32, 1429–1450 (2005)MathSciNet
[98]
H. Crowder, M.W. Padberg, Solving large-scale symmetric travelling salesman problems to optimality. Manag. Sci. 26, 495–509 (1980)MATHMathSciNet
[99]
H. Crowder, E. Johnson, M.W. Padberg, Solving large scale zero-one linear programming problems. Oper. Res. 31, 803–834 (1983)MATH
[100]
R.J. Dakin, A tree-search algorithm for mixed integer programming problems. Comput. J. 8, 250–255 (1965)MATHMathSciNet
[101]
E. Danna, E. Rothberg, C. Le Pape, Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. A 102, 71–90 (2005)MATH
[102]
G.B. Dantzig, Maximization of a linear function of variables subject to linear inequalities, in Activity Analysis of Production and Allocation, ed. by T.C. Koopmans (Wiley, New York, 1951), pp. 339–347
[103]
G. Dantzig. R. Fulkerson, S. Johnson, Solution of a large-scale traveling-salesman problem. Oper. Res. 2, 393–410 (1954)MathSciNet
[104]
G.B. Dantzig, P. Wolfe, Decomposition principle for linear programs. Oper. Res. 8, 101–111 (1960)MATH
[105]
L. Danzer, B. Grünbaum, V. Klee, Helly’s theorem and its relatives, in Convexity, ed. by V. Klee (American Mathematical Society, Providence, 1963), pp. 101–180
[106]
S. Dash, S.S. Dey, O. Günlük, Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra. Math. Program. 135, 221–254 (2012)MATHMathSciNet
[107]
S. Dash, O. Günlük, A. Lodi, in On the MIR Closure of Polyhedra, IPCO 2007, ed. by M. Fischetti, D.P. Williamson. LNCS, Springer vol. 4513 (2007), pp. 337–351
[108]
R. Dechter, Constraint Processing (Morgan Kaufmann, San Francisco, 2003)
[109]
J.A. De Loera, J. Lee, P.N. Malkin, S. Margulies, Computing infeasibility certificates for combinatorial problems through Hilbert’s Nullstellensatz. J. Symb. Comput. 46, 1260–1283 (2011)MATH
[110]
J.A. De Loera, R. Hemmecke, M. Köppe, Algebraic and Geometric Ideas in the Theory of Discrete Optimization. MOS-SIAM Series on Optimization, vol. 14 (2012)
[111]
R. de Wolf, Nondeterministic quantum query and communication complexities. SIAM J. Comput. 32, 681–699 (2003)MATHMathSciNet
[112]
A. Del Pia, R. Weismantel, Relaxations of mixed integer sets from lattice-free polyhedra. 4OR 10, 221–244 (2012)
[113]
A. Del Pia, R. Weismantel, On convergence in mixed integer programming. Math. Program. 135, 397–412 (2012)MATHMathSciNet
[114]
J. Desrosiers, F. Soumis, M. Desrochers, Routing with time windows by column generation. Networks 14, 545–565 (1984)MATH
[115]
S.S. Dey, Q. Louveaux, Split rank of triangle and quadrilateral inequalities. Math. Oper. Res. 36, 432–461 (2011)MATHMathSciNet
[116]
S. S. Dey, D.A. Morán, On maximal S-free convex sets. SIAM J. Discrete Math. 25(1), 379–393 (2011)MATHMathSciNet
[117]
S.S. Dey, J.-P.P. Richard, Y. Li, L.A. Miller, On the extreme inequalities of infinite group problems. Math. Program. A 121, 145–170 (2010)MATHMathSciNet
[118]
S.S. Dey, L.A. Wolsey, Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles, IPCO 2008, Bertinoro, Italy. Lecture Notes in Computer Science, Springer, vol. 5035 (2008), pp. 463–475MathSciNet
[119]
S.S. Dey, L.A. Wolsey, Constrained infinite group relaxations of MIPs. SIAM J. Optim. 20, 2890–2912 (2010)MATHMathSciNet
[120]
E.A. Dinic, Algorithm for solution of a problem of maximum flow in networks with power estimation. Soviet Math. Dokl. 11, 1277–1280 (1970)
[121]
[122]
M. Dyer, A. Frieze, R. Kannan, A random polynomial-time algorithm for approximating the volume of convex bodies. J. ACM 38, 1–17 (1991)MATHMathSciNet
[123]
[124]
J. Edmonds, Maximum matching and a polyhedron with 0,1-vertices. J. Res. Natl. Bur. Stand. B 69, 125–130 (1965)MATHMathSciNet
[125]
J. Edmonds, Systems of distinct representatives and linear algebra. J. Res. Natl. Bur. Stand. B 71, 241–245 (1967)MATHMathSciNet
[126]
J. Edmonds, Submodular functions, matroids, and certain polyhedra, in Combinatorial Structures and Their Applications, ed. by R. Guy, H. Hanani, N. Sauer, J. Schönheim. (Gordon and Breach, New York, 1970), pp. 69–87
[127]
[128]
J. Edmonds, R. Giles, A min-max relation for submodular functions on graphs. Ann. Discrete Math. 1, 185–204 (1977)MathSciNet
[129]
J. Edmonds, R.M. Karp, Theoretical improvements in algorithmic efficiency for network flow problems. J. ACM 19, 248–264 (1972)MATH
[130]
F. Eisenbrand, On the membership problem for the elementary closure of a polyhedron. Combinatorica 19, 297–300 (1999)MATHMathSciNet
[131]
F. Eisenbrand, G. Shmonin, Carathéodory bounds on integer cones. Oper. Res. Lett. 34, 564–568 (2006)MATHMathSciNet
[132]
F. Eisenbrand, A.S. Schulz, Bounds on the Chvátal rank of polytopes in the 0/1 cube. Combinatorica 23, 245–261 (2003)MATHMathSciNet
[133]
D. Erlenkotter, A dual-based procedure for uncapacitated facility location. Oper. Res. 26, 992–1009 (1978)MATHMathSciNet
[134]
T. Fahle, S. Shamberger, M. Sellmann, Symmetry Breaking, CP 2001. LNCS, vol. 2239 (2001), pp. 93–107
[135]
Gy. Farkas, On the applications of the mechanical principle of Fourier, Mathematikai és Természettudományi Értesotö 12, 457–472 (1894)
[136]
S. Fiorini, S. Massar, S. Pokutta, H.R. Tiwary, R. de Wolf, Linear vs. semidefinite extended formulations: exponential separation and strong lower bounds, in STOC 2012 (2012)
[137]
S. Fiorini, V. Kaibel, K. Pashkovich, D.O. Theis Combinatorial bounds on the nonnegative rank and extended formulations. Discrete Math. 313, 67–83 (2013)MATHMathSciNet
[138]
M.L. Fischer, The Lagrangian relaxation method for solving integer programming problems. Manag. Sci. 27, 1–18 (1981)
[139]
[140]
[141]
M. Fischetti, A. Lodi, Optimizing over the first Chvátal closure. Math. Program. 110, 3–20 (2007)MATHMathSciNet
[142]
M. Fischetti, A. Lodi, A. Tramontani, On the separation of disjunctive cuts. Math. Program. A 128, 205–230 (2011)MATHMathSciNet
[143]
M. Fischetti, D. Salvagnin, C. Zanette, A note on the selection of Benders’ cuts. Math. Program. B 124, 175–182 (2010)MATHMathSciNet
[144]
R. Fortet, Applications de l’algèbre de Boole en recherche opérationnelle. Revue Française de Recherche Opérationnelle 4, 17–26 (1960)
[145]
J.B.J. Fourier, Solution d’une question particulière du calcul des inégalités. Nouveau Bulletin des Sciences par la Société Philomatique de Paris (1826), pp. 317–319
[146]
[147]
L.R. Ford Jr., D.R. Fulkerson, Flows in Networks (Princeton University Press, Princeton, 1962)MATH
[148]
A. Frank, Connections in combinatorial optimization, in Oxford Lecture Series in Mathematics and Its Applications, vol. 38 (Oxford University Press, Oxford, 2011)
[149]
A. Frank, E. Tardos, An application of simultaneous Diophantine approximation in combinatorial optimization. Combinatorica 7, 49–65 (1987)MATHMathSciNet
[150]
R. M. Freund, J.B. Orlin, On the complexity of four polyhedral set containment problems. Math. Program. 33, 139–145 (1985)MATHMathSciNet
[151]
A.M. Frieze, M. Jerrum, Improved approximation algorithms for MAX k-CUT and MAX BISECTION. Algorithmica 18, 67–81 (1997)MATHMathSciNet
[152]
K. Fukuda, Frequently Asked Questions in Polyhedral Computation. Research Report, Department of Mathematics, and Institute of Theoretical Computer Science ETH Zurich, available online (2013)
[153]
K. Fukuda, Lecture: Polyhedral Computation. Research Report, Department of Mathematics, and Institute of Theoretical Computer Science ETH Zurich, available online (2004)
[154]
[155]
[156]
D.R Fulkerson, Blocking polyhedra, B Harris (Ed.), Graph Theory and Its Applications, Academic Press, New York 93–112 (1970)
[157]
D.R. Fulkerson, G.L. Nemhauser, L.E. Trotter, Two computationally difficult set covering problems that arise in computing the 1-width of incidence matrices of Steiner triples. Math. Program. Study 2, 72–81 (1974)
[158]
M.R. Garey, D.S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness (W.H. Freeman and Co., New York, 1979)MATH
[159]
R.S. Garfinkel, G. Nemhauser, Integer Programming (Wiley, New York, 1972)MATH
[160]
C.F. Gauss, Theoria Motus Corporum Coelestium in Sectionibus Conicis Solem Ambientium (F. Perthes & J.H. Besser, Hamburg, 1809)
[161]
[162]
A.M. Geoffrion, Lagrangean relaxation for integer programming. Math. Program. Study 2, 82–114 (1974)MathSciNet
[163]
A.M. Geoffrion, G.W. Graves, Multicommodity distribution design by Benders’ decomposition. Manag. Sci. 20, 822–844 (1974)MATHMathSciNet
[164]
A.M.H. Gerards, A short proof of Tutte’s characterization of totally unimodular matrices. Linear Algebra Appl. 114/115, 207–212 (1989)
[165]
A. Ghouila-Houri, Caractérisation des matrices totalement unimodulaires. Comptes Rendus Hebdomadaires des Scéances de l’Académie des Sciences (Paris) 254, 1192–1194 (1962)MATHMathSciNet
[166]
F.R. Giles, W.R. Pulleyblank, Total dual integrality and integer polyhedra. Linear Algebra Appl. 25, 191–196 (1979)MATHMathSciNet
[167]
P.C. Gilmore, Families of sets with faithful graph representation. IBM Research Note N.C., vol. 184 (Thomas J. Watson Research Center, Yorktown Heights, 1962)
[168]
P.C. Gilmore, R.E. Gomory, A linear programming approach to the cutting-stock problem. Oper. Res. 9, 849–859 (1961)MATHMathSciNet
[169]
M.X. Goemans, Worst-case comparison of valid inequalities for the TSP. Math. Program. 69, 335–349 (1995)MATHMathSciNet
[170]
M.X. Goemans, Smallest compact formulation for the permutahedron. Math. Program. Ser. A DOI 10.1007/s101007-014-0757-1 (2014)
[171]
M.X. Goemans, T. Rothvoß, Polynomiality for bin packing with a constant number of item types. arXiv:1307.5108 [cs.DS] (2013)
[172]
M.X. Goemans, L. Tunçel, When does the positive semidefiniteness constraint help in lifting procedures. Math. Oper. Res. 26, 796–815 (2001)MATHMathSciNet
[173]
M.X. Goemans, D.P. Williamson, Improved approximation algorithms for maximum cut and satisfiability problems using semidefinite programming. J. ACM 42, 1115–1145 (1995)MATHMathSciNet
[174]
J.L. Goffin, Variable metric relaxation methods, part II: the ellipsoid method. Math. Program. 30, 147–162 (1984)MATHMathSciNet
[175]
R.E. Gomory, Outline of an algorithm for integer solutions to linear programs. Bull. Am. Math. Soc. 64, 275–278 (1958)MATHMathSciNet
[176]
R.E. Gomory, An algorithm for the mixed integer problem. Tech. Report RM-2597 (The Rand Corporation, 1960)
[177]
R.E. Gomory, An algorithm for integer solutions to linear programs, in Recent Advances in Mathematical Programming, ed. by R.L. Graves, P. Wolfe (McGraw-Hill, New York, 1963), pp. 269–302
[178]
R.E. Gomory, Some polyhedra related to combinatorial problems. Linear Algebra Appl. 2, 451–558 (1969)MATHMathSciNet
[179]
R.E. Gomory, E.L. Johnson, Some continuous functions related to corner polyhedra I. Math. Program. 3, 23–85 (1972)MATHMathSciNet
[180]
[181]
J. Gouveia, P. Parrilo, R. Thomas, Theta bodies for polynomial ideals. SIAM J. Optim. 20, 2097–2118 (2010)MATHMathSciNet
[182]
J. Gouveia, P. Parrilo, R. Thomas, Lifts of convex sets and cone factorizations. Math. Oper. Res. 38, 248–264 (2013)MATHMathSciNet
[183]
M. Grötschel, Polyedrische Charackterisierungen kombinatorischer Optimierungsprobleme (Anton Hain, Meisenheim/Glan, 1977)
[184]
M. Grötschel, On the symmetric travelling salesman problem: solution of a 120-city problem. Math. Program. Study 12, 61–77 (1980)MATH
[185]
M. Grötschel, M. Jünger, G. Reinelt, A cutting plane algorithm for the linear ordering problem. Oper. Res. 32, 1195–1220 (1984)MATHMathSciNet
[186]
M. Grötschel, L. Lovász, A. Schrijver, The ellipsoid method and its consequences in combinatorial optimization. Combinatorica 1, 169–197 (1981)MATHMathSciNet
[187]
M. Grötschel, L. Lovász, A. Schrijver, Geometric methods in combinatorial optimization, in Progress in Combinatorial Optimization, ed. by W.R. Pulleyblank (Academic, Toronto, 1984), pp. 167–183
[188]
M. Grötschel, L. Lovász, A. Schrijver, Geometric Algorithms and Combinatorial Optimization (Springer, New York, 1988)MATH
[189]
M. Grötschel, M.W. Padberg, On the symmetric travelling salesman problem I: inequalities. Math. Program. 16, (1979) 265–280MATH
[190]
B. Grünbaum, Convex Polytopes (Wiley-Interscience, London, 1967)MATH
[191]
Z. Gu, G.L. Nemhauser, M.W.P. Savelsbergh, Lifted flow covers for mixed 0–1 integer programs. Math. Program. 85, 439–467 (1999)MATHMathSciNet
[192]
Z. Gu, G.L. Nemhauser, M.W.P. Savelsbergh, Sequence independent lifting in mixed integer programming. J. Combin. Optim. 1, 109–129 (2000)MathSciNet
[193]
C. Guéret, C. Prins, M. Servaux, Applications of Optimization with Xpress (Dash Optimization Ltd., London, 2002)
[194]
M. Guignard, S. Kim, Lagrangean decomposition for integer programming: theory and applications. RAIRO 21, 307–323 (1987)MATHMathSciNet
[195]
[196]
[197]
M. Held, R.M. Karp, The traveling-salesman problem and minimum spanning trees. Oper. Res. 18, 1138–1162 (1970)MATHMathSciNet
[198]
M. Held, R.M. Karp, The traveling-salesman problem and minimum spanning trees: part II. Math. Program. 1, 6–25 (1971)MATHMathSciNet
[199]
I. Heller, C.B. Tompkins, An extension of a theorem of Dantzig’s, in Linear Inequalities and Related Systems, ed. by H.W. Kuhn, A.W. Tucker (Princeton University Press, Princeton, 1956), pp. 247–254
[200]
Ch. Hermite, Extraits de lettres de M. Ch. Hermite à M. Jacobi sur différents objets de la théorie des nombres. Journal für dei reine und angewandte Mathematik 40, 261–277 (1850)MATH
[201]
J.-B. Hiriart-Urruty, C. Lemaréchal. Fundamentals of Convex Analysis (Springer, New York, 2001)MATH
[202]
D.S. Hirschberg, C.K. Wong, A polynomial algorithm for the knapsack problem in two variables. J. ACM 23, 147–154 (1976)MATHMathSciNet
[203]
A.J. Hoffman, A generalization of max-flow min-cut. Math. Program. 6, 352–259 (1974)MATH
[204]
A.J. Hoffman, J.B. Kruskal, Integral boundary points of polyhedra, in Linear Inequalities and Related Systems, ed. by H.W. Kuhn, A.W. Tucker (Princeton University Press, Princeton, 1956), pp. 223–246
[205]
J.N. Hooker, Needed: an empirical science of algorithms. Oper. Res. 42, 201–212 (1994)MATH
[206]
J. Hooker, Integrated Methods for Optimization. International Series in Operations Research and Management Science (Springer, New York, 2010)
[207]
R.A. Horn, C.R. Johnson, Matrix Analysis (Cambridge University Press, Cambridge, 2013)MATH
[208]
[209]
S. Iwata, L. Fleischer, S. Fujishige, A combinatorial, strongly polynomial-time algorithm for minimizing submodular functions. J. ACM 48, 761–777 (2001)MATHMathSciNet
[210]
R.G. Jeroslow, There cannot be any algorithm for integer programming with quadratic constraints. Oper. Res. 21, 221–224 (1973)MATHMathSciNet
[211]
R.G. Jeroslow, Representability in mixed integer programming, I: characterization results. Discrete Appl. Math. 17, 223–243 (1987)MATHMathSciNet
[212]
R.G Jeroslow, On defining sets of vertices of the hypercube by linear inequalities. Discrete Math. 11, 119–124 (1975)MATHMathSciNet
[213]
R.G Jeroslow, J.K. Lowe, Modelling with integer variables. Math. Program. Stud. 22, 167–184 (1984)MATHMathSciNet
[214]
F. John, Extremum problems with inequalities as subsidiary conditions, in Studies and Essays Presented to R. Courant on his 60th Birthday, January 8, 1948 (Interscience Publishers, New York, 1948), pp. 187–204
[215]
E.L. Johnson, On the group problem for mixed integer programming. Math. Program. Study 2, 137–179 (1974)
[216]
E.L. Johnson, Characterization of facets for multiple right-hand choice linear programs. Math. Program. Study 14, 112–142 (1981)MATH
[217]
M. Jünger, T. Liebling, D. Naddef, G. Nemhauser, W. Pulleyblank, G. Reinelt, G. Rinaldi, L. Wolsey (eds.), 50 Years of Integer Programming 1958–2008 (Springer, Berlin, 2010)MATH
[218]
M. Jünger, D. Naddef (eds.), Computational Combinatorial Optimization. Optimal or provably near-optimal solutions. Lecture Notes in Computer Science, vol. 2241 (Springer, Berlin, 2001)
[219]
V. Kaibel, Extended formulations in combinatorial optimization. Optima 85, 2–7 (2011)
[220]
V. Kaibel, K. Pashkovich, Constructing extended formulations from reflection relations, in Proceedings of IPCO XV O. Günlük, ed. by G. Woeginger. Lecture Notes in Computer Science, vol. 6655 (Springer, Berlin, 2011), pp. 287–300
[221]
V. Kaibel, K. Pashkovich, D.O. Theis, Symmetry matters for sizes of extended formulations. SIAM J. Discrete Math. 26(3), 1361–1382 (2012)MATHMathSciNet
[222]
[223]
V. Kaibel, S. Weltge, A short proof that the extension complexity of the correlation polytope grows exponentially. arXiv:1307.3543 (2013)
[224]
V. Kaibel, S. Weltge, Lower bounds on the sizes of integer programs without additional variables. arXiv:1311.3255 (2013)
[225]
R. Kannan, A polynomial algorithm for the two-variable integer programming problem. J. ACM 27, 118–122 (1980)MATH
[226]
R. Kannan, Improved algorithms for integer programming and related problems, in Proceedings of the 15th Annual ACM Symposium on Theory of Computing (STOC-83) (1983), pp. 193–206
[227]
R. Kannan, Minkowski’s convex body theorem and integer programming. Math. Oper. Res. 12, 415–440 (1987)MATHMathSciNet
[228]
R. Kannan, A. Bachem, Polynomial algorithms for computing the Smith and Hermite normal forms of an integer matrix. SIAM J. Comput. 8, 499–507 (1979)MATHMathSciNet
[229]
N. Karmarkar, A new polynomial-time algorithm for linear programming. Combinatorica 4, 373–395 (1984)MATHMathSciNet
[230]
D.R. Karger, Global min-cuts in RNC, and other ramifications of a simple min-cut algorithm, in Proceedings of SODA (1993), pp. 21–30
[231]
D.R. Karger, R. Motwani, M. Sudan, Approximate graph coloring by semidefinite programming. J. ACM 45, 246–265 (1998)MATHMathSciNet
[232]
R.M. Karp, Reducubility among combinatorial problems, in Complexity of Computer Computations (Plenum Press, New York, 1972), pp. 85–103
[233]
R.M. Karp, C.H. Papadimitriou, On linear characterizations of combinatorial optimization problems. SIAM J. Comput. 11, 620–632 (1982)MATHMathSciNet
[234]
H. Kellerer, U. Pferschy, D. Pisinger, Knapsack Problems (Springer, Berlin, 2004)MATH
[235]
L.G. Khachiyan, A polynomial algorithm in linear programming. Soviet Math. Dokl. 20, 191–194 (1979)MATH
[236]
L. Khachiyan, E. Boros, K. Borys, K. Elbassioni, V. Gurvich, Generating all vertices of a polyhedron is hard. Discrete Comput. Geom. 39, 174–190 (2008)MATHMathSciNet
[237]
A. Khinchine, A quantitative formulation of Kronecker’s theory of approximation (in russian). Izvestiya Akademii Nauk SSR Seriya Matematika 12, 113–122 (1948)
[238]
F. Kilinc-Karzan, G.L. Nemhauser, M.W.P. Savelsbergh, Information-based branching schemes for binary linear mixed integer problems. Math. Program. Comput. 1, 249–293 (2009)MathSciNet
[239]
D. Klabjan, G.L. Nemhauser, C. Tovey, The complexity of cover inequality separation. Oper. Res. Lett. 23, 35–40 (1998)MATHMathSciNet
[240]
V. Klee, G.J. Minty, How good is the simplex algorithm? in Inequalities, III, ed. by O. Shisha (Academic, New York, 1972), pp. 159–175
[241]
M. Köppe, Q. Louveaux, R. Weismantel, Intermediate integer programming representations using value disjunctions. Discrete Optim. 5, 293–313 (2008)MATHMathSciNet
[242]
M. Köppe, R. Weismantel, A mixed-integer Farkas lemma and some consequences. Oper. Res. Lett. 32, 207–211 (2004)MATHMathSciNet
[243]
B. Korte, J. Vygen, Combinatorial Optimization: Theory and Algorithms (Springer, Berlin/Hidelberg, 2000)
[244]
J.B. Kruskal Jr., On the shortest spanning subtree of a graph and the traveling salesman problem. Proc. Am. Math. Soc. 7, 48–50 (1956)MATHMathSciNet
[245]
H.W. Kuhn, The Hungarian method for the assignment problem. Naval Res. Logistics Q. 2, 83–97 (1955)
[246]
A.H. Land, A.G. Doig, An automatic method of solving discrete programming problems. Econometrica 28, 497–520 (1960)MATHMathSciNet
[247]
J.B. Lasserre, An Explicit Exact SDP Relaxation for Nonlinear 0–1 Programs. Lecture Notes in Computer Science, vol. 2081 (2001), pp. 293–303MathSciNet
[248]
J.B. Lasserre, Global optimization with polynomials and the problem of moments. SIAM J. Optim. 11, 796–817 (2001)MATHMathSciNet
[249]
M. Laurent, A comparison of the Sherali-Adams, Lovász-Schrijver and Lasserre relaxations for 0–1 programming. SIAM J. Optim. 28, 345–375 (2003)
[250]
M. Laurent, F. Rendl, Semidefinite programming and integer programming, in Handbook on Discrete Optimization, ed. by K. Aardal, G.L. Nemhauser, R. Weimantel (Elsevier, Amsterdam, 2005), pp. 393–514
[251]
E. L. Lawler, Covering problems: duality relations and a method of solution. SIAM J. Appl. Math. 14, 1115–1132 (1966)MATHMathSciNet
[252]
E. L. Lawler, Combinatorial Optimization: Networks and Matroids (Holt, Rinehart and Winston, New York, 1976)MATH
[253]
E.L. Lawler, J.K. Lenstra, A.H.G. Rinnooy Kan, D.B. Shmoys (eds.), The Traveling Salesman Problem: A Guided Tour of Combinatorial Optimization (Wiley, New York, 1985)MATH
[254]
[255]
A.K. Lenstra, H.W. Lenstra, L. Lovász, Factoring polynomials with rational coefficients. Math. Ann. 261, 515–534 (1982)MATHMathSciNet
[256]
H.W. Lenstra, Integer programming with a fixed number of variables. Math. Oper. Res. 8, 538–548 (1983)MATHMathSciNet
[257]
J.T. Linderoth, M.W.P. Savelsbergh, A computational study of search strategies for mixed integer programming. INFORMS J. Comput. 11, 173–187 (1999)MATHMathSciNet
[258]
Q. Louveaux, L.A. Wolsey, Lifting, superadditivity, mixed integer rounding and single node flow sets revisited. 4OR 1, 173–207 (2003)
[259]
L. Lovász, Normal hypergraphs and the perfect graph conjecture. Discrete Math. 2, 253–267 (1972)MATHMathSciNet
[260]
L. Lovász, On the Shannon capacity of a graph. IEEE Trans. Inf. Theory 25, 1–7 (1979)MATH
[261]
L. Lovász, Geometry of numbers and integer programming, in Mathematical Programming: Recent Developments and Applications, ed. by M. Iri, K. Tanabe (Kluwer, Dordrecht, 1989), pp. 177–201
[262]
L. Lovász, M.D. Plummer, Matching Theory (Akadémiai Kiadó, Budapest, 1986) [Also: North Holland Mathematics Studies, vol. 121 (North Holland, Amsterdam)]MATH
[263]
L. Lovász, H.E. Scarf, The generalized basis reduction algorithm. Math. Oper. Res. 17, 751–764 (1992)MATHMathSciNet
[264]
L. Lovász, A. Schrijver, Cones of matrices and set-functions and 0–1 optimization. SIAM J. Optim. 1, 166–190 (1991)MATHMathSciNet
[265]
T.L. Magnanti, R.T. Wong, Accelerated Benders decomposition: algorithmic enhancement and model selection criteria. Oper. Res. 29, 464–484 (1981)MATHMathSciNet
[266]
H. Marchand, L.A. Wolsey, Aggregation and mmixed integer rounding to solve MIPs. Oper. Res. 49, 363–371 (2001)MATHMathSciNet
[267]
[268]
S. Martello, P. Toth, Knapsack Problems: Algorithms and Computer Implementations (Wiley, Chichester, 1990)MATH
[269]
R.K. Martin, Generating alternative mixed integer programming models using variable definition. Oper. Res. 35, 820–831 (1987)MATHMathSciNet
[270]
R.K. Martin, Using separation algorithms to generate mixed integer model reformulations. Oper. Res. Lett. 10(3), 119–128 (1991)MATHMathSciNet
[271]
R.K. Martin, R.L. Rardin, B.A. Campbell, Polyhedral characterization of discrete dynamic programming. Oper. Res. 38, 127–138 (1990)MATHMathSciNet
[272]
J.F. Maurras, Bon algorithmes, vieilles idées, Note E.d.F. HR 32.0320 (1978)
[273]
J.F. Maurras, K. Truemper, M. Agkül, Polynomial algorithms for a class of linear programs. Math. Program. 21, 121–136 (1981)MATH
[274]
C.C. McGeogh, Experimental analysis of algorithms. Notices Am. Math. Assoc. 48, 204–311 (2001)
[275]
[276]
R.R. Meyer, On the existence of optimal solutions to integer and mixed integer programming problems. Math. Program. 7, 223–235 (1974)MATH
[277]
D. Micciancio, The shortest vector in a lattice is hard to approximate to within some constant, in Proceedings of the 39th Annual Symposium on Foundations of Computer Science (FOCS-98) (1998), pp. 92–98
[278]
C.E. Miller, A.W. Tucker, R.A. Zemlin, Integer programming formulation of traveling salesman problems. J. ACM 7, 326–329 (1960)MATHMathSciNet
[279]
H. Minkowski, Geometrie der Zahlen (Erste Lieferung) (Teubner, Leipzig, 1896)
[280]
T.S. Motzkin, H. Raiffa, G.L. Thompson, R.M. Thrall, The double description method, in Contributions to Theory of Games, vol. 2, ed. by H.W. Kuhn, A.W. Tucker (Princeton University Press, Princeton, 1953)
[281]
[282]
H. Nagamochi, T. Ibaraki, Computing edge-connectivity in multiple and capacitated graphs. SIAM J. Discrete Math. 5, 54–66 (1992)MATHMathSciNet
[283]
G.L. Nemhauser, L.E. Trotter Jr., Properties of vertex packing and independence system polyhedra. Math. Program. 6, 48–61 (1974)MATHMathSciNet
[284]
G.L. Nemhauser, L.E. Trotter Jr., Vertex packings: structural properties and algorithms. Math. Program. 8, 232–248 (1975)MATHMathSciNet
[285]
G.L. Nemhauser, L.A. Wolsey, Integer and Combinatorial Optimization (Wiley, New York, 1988)MATH
[286]
G.L. Nemhauser, L.A. Wolsey, A recursive procedure to generate all cuts for 0–1 mixed integer programs. Math. Program. 46, 379–390 (1990)MATHMathSciNet
[287]
[288]
Y.E. Nesterov, Semidefinite relaxation and nonconvex quadratic optimization. Optim. Methods Softw. 12, 1–20 (1997)MathSciNet
[289]
Y.E. Nesterov, A.S. Nemirovski, Self-concordant functions and polynomial time methods in convex programming. Technical report, Central Economical and Mathematical Institute, U.S.S.R (Academy of Science, Moscow, 1990)
[290]
Y.E. Nesterov, A.S. Nemirovski, Conic formulation of a convex programming problem and duality. Optim. Methods Softw. 1, 95–115 (1992)
[291]
Y.E. Nesterov, A.S. Nemirovski, Interior Point Polynomial Algorithms in Convex Programming (SIAM, Philadelphia, 1994)MATH
[292]
J. Ostrowski, J.T. Linderoth, F. Rossi, S. Smriglio, Solving large Steiner triple covering problems. Oper. Res. Lett. 39, 127–131 (2011)MATHMathSciNet
[293]
J. Ostrowski, J. Linderoth, F. Rossi, S. Smriglio, Orbital branching. Math. Program. 126, 147–178 (2011)MATHMathSciNet
[294]
J.H. Owen, S. Mehrotra, A disjunctive cutting plane procedure for general mixed-integer linear programs. Math. Program. A 89, 437–448 (2001)MATHMathSciNet
[295]
J.H. Owen, S. Mehrotra, On the value of binary expansions for general mixed-integer linear programs. Oper. Res. 50, 810–819 (2002)MATHMathSciNet
[296]
J. Oxley, Matroid Theory (Oxford University Press, New York, 2011)MATH
[297]
[298]
[299]
M.W. Padberg, M.R. Rao, The Russian method for linear programming III: bounded integer programming. Research Report 81-39, Graduate School of Business Administration, New York University (1981)
[300]
[301]
M.W. Padberg, G. Rinaldi, Optimization of a 532-city symmetric traveling salesman problem by branch and cut. Oper. Res. Lett. 6, 1–7 (1987)MATHMathSciNet
[302]
M.W. Padberg, G. Rinaldi, A branch-and-cut algorithm for the resolution of large-scale symmetric traveling salesman problems. SIAM Rev. 33, 60–100 (1991)MATHMathSciNet
[303]
M. Padberg, T.J. Van Roy, L.A. Wolsey, Valid linear inequalities for fixed charge problems. Oper. Res. 33, 842–861 (1985)MATHMathSciNet
[304]
[305]
[306]
J. Patel, J.W. Chinneck, Active-constraint variable ordering for faster feasibility of mixed integer linear programs. Math. Program. 110, 445–474 (2007)MATHMathSciNet
[307]
J. Petersen, Die Theorie der regulären graphs. Acta Matematica 15, 193–220 (1891)MATH
[308]
Y. Pochet, L.A. Wolsey, Polyhedra for lot-sizing with Wagner–Whitin costs. Math. Program. 67, 297–324 (1994)MATHMathSciNet
[309]
Y. Pochet, L.A. Wolsey, Production Planning by Mixed-Integer Programming. Springer Series in Operations Research and Financial Engineering (Springer, New York, 2006)
[310]
B.T. Poljak, A general method for solving extremum problems. Soviet Math. Dokl. 8, 593–597 (1967)
[311]
C.H. Papadimitriou, M. Yannakakis, On recognizing integer polyhedra. Combinatorica 10, 107–109 (1990)MATHMathSciNet
[312]
M. Queyranne, A.S. Schulz, Polyhedral approaches to machine scheduling. Preprint (1994)
[313]
A. Razborov, On the distributional complexity of disjointness. Theor. Comput. Sci. 106(2), 385–390 (1992)MATHMathSciNet
[314]
J. Renegar, A polynomial-time algorithm based on Newton’s method for linear programming. Math. Program. 40, 59–93 (1988)MATHMathSciNet
[315]
J.-P.P. Richard, S.S. Dey (2010). The group-theoretic approach in mixed integer programming, in 50 Years of Integer Programming 1958–2008, ed. by M. Jünger, T. Liebling, D. Naddef, G. Nemhauser, W. Pulleyblank, G. Reinelt, G. Rinaldi, L. Wolsey (Springer, New York, 2010), pp. 727–801
[316]
R.T. Rockafellar, Convex Analysis (Princeton University Press, Princeton, 1969)
[317]
T. Rothvoß, Some 0/1 polytopes need exponential size extended formulations. Math. Program. A 142, 255–268 (2012)
[318]
T. Rothvoß, The matching polytope has exponential extension complexity, in Proceedings of the 46th Annual ACM Symposium on Theory of Computing (STOC 2014), (2014), pp. 263–272
[319]
T. Rothvoß, L. Sanitá, 0 − 1 polytopes with quadratic Chvátal rank, in Proceedings of the 16th IPCO Conference. Lecture Notes in Computer Science, vol. 7801 (Springer, New York, 2013)
[320]
J.-S. Roy, Reformulation of bounded integer variables into binary variables to generate cuts. Algorithmic Oper. Res. 2, 810–819 (2007)
[321]
M.P.W. Savelsbergh, Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6, 445–454 (1994)MATHMathSciNet
[322]
H.E. Scarf, An observation on the structure of production sets with indivisibilities. Proc. Natl. Acad. Sci. USA 74, 3637–3641 (1977)MATHMathSciNet
[323]
[324]
[325]
A. Schrijver, Theory of Linear and Integer Programming (Wiley, New York, 1986)MATH
[326]
A. Schrijver, A combinatorial algorithm minimizing submodular functions in strongly polynomial time. J. Combin. Theory Ser. B 80, 346–355 (2000)MATHMathSciNet
[327]
A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (Springer, Berlin, 2003)
[328]
Á. Seress, Permutation Group Algorithms, Cambridge Tracts in Mathematics, vol. 152 (Cambridge University Press, Cambridge, 2003)
[329]
[330]
H. Sherali, W. Adams, A hierarchy of relaxations between the continuous and convex hull representations for zero-one programming problems. SIAM J. Discrete Math. 3, 311–430 (1990)MathSciNet
[331]
H. Sherali, W. Adams, A Reformulation-Linearization Technique for Solving Discrete and Continuous Nonconvex Problems, Chap. 4 (Kluwer Academic Publishers, Norwell, 1999)
[332]
N. Z. Shor, Cut-off method with space extension in convex programming problems. Cybernetics 13, 94–96 (1977)
[333]
[334]
E. Tardos, A strongly polynomial algorithm to solve combinatorial linear programs. Oper. Res. 34, 250–256 (1986)MATHMathSciNet
[335]
[336]
S. Tayur, R.R. Thomas, N.R. Natraj, An algebraic geometry algorithm for scheduling in presence of setups and correlated demands. Math. Program. 69, 369–401 (1995)MATHMathSciNet
[337]
P. Toth, D. Vigo, The Vehicle Routing Problem. Monographs on Discrete Mathematics and Applications (SIAM, Philadelphia, 2001)
[338]
K. Truemper, Matroid Decomposition (Academic, Boston, 1992)MATH
[339]
W.T. Tutte, A homotopy theorem for matroids I, II. Trans. Am. Math. Soc. 88, 905–917 (1958)MathSciNet
[340]
T.J. Van Roy, L.A. Wolsey, Solving mixed integer programming problems using automatic reformulation. Oper. Res. 35, 45–57 (1987)MATHMathSciNet
[341]
[342]
F. Vanderbeck, L.A. Wolsey, Reformulation and decomposition of integer programs, in 50 Years of Integer Programming 1958–2008, ed. by M. Jünger, T. Liebling, D. Naddef, G. Nemhauser, W. Pulleyblank, G. Reinelt, G. Rinaldi, L. Wolsey (Springer, New York, 2010), pp. 431–502
[343]
R.J. Vanderbei, Linear Programming: Foundations and Extentions, 3rd edn. (Springer, New York, 2008)
[344]
S. Vavasis, On the complexity of nonnegative matrix factorization. SIAM J. Optim. 20, 1364–1377 (2009)MATHMathSciNet
[345]
V.V. Vazirani, Approximation Algorithms (Springer, Berlin, 2003)
[346]
J.P. Vielma, A constructive characterization of the split closure of a mixed integer linear program. Oper. Res. Lett. 35, 29–35 (2007)MATHMathSciNet
[347]
J.P. Vielma, Mixed integer linear programming formulation techniques to appear in SIAM Review (2014)
[348]
H. Weyl, The elementary theory of convex polyhedra, in Contributions to the Theory of Games I, ed. by H.W. Kuhn, A.W. Tucker (Princeton University Press, Princeton, 1950), pp. 3–18
[349]
D.P. Williamson, D.B. Shmoys, The Design of Approxiamtion Algorithms (Cambridge University Press, Cambridge, 2011)
[350]
L.A. Wolsey, Further facet generating procedures for vertex packing polytopes. Math. Program. 11, 158–163 (1976)MATHMathSciNet
[351]
L.A. Wolsey, Valid inequalities and superadditivity for 0–1 integer programs. Math. Oper. Res. 2, 66–77 (1977)MATHMathSciNet
[352]
L.A. Wolsey, Heuristic analysis, linear programming, and branch and bound. Math. Program. Stud. 13, 121–134 (1980)MATHMathSciNet
[353]
L.A. Wolsey, Integer Programming (Wiley, New York, 1999)
[354]
R.T. Wong, Dual ascent approach for Steiner tree problems on directed graphs. Math. Program. 28, 271–287 (1984)MATH
[355]
M. Yannakakis, Expressing combinatorial optimization problems by linear programs. J. Comput. Syst. Sci. 43, 441–466 (1991)MATHMathSciNet
[356]
D. B. Yudin, A. S. Nemirovski, Evaluation of the information complexity of mathematical programming problems. Ekonomika i Matematicheskie Metody 12, 128–142 (1976) (in Russian). English Translation: Matekon 13, 3–45 (1976)
[357]
G.M. Ziegler, Lectures on Polytopes (Springer, New York, 1995)MATH
Metadata
Title
Valid Inequalities for Structured Integer Programs
Authors
Michele Conforti
Gérard Cornuéjols
Giacomo Zambelli
Copyright Year
2014
Book
Integer Programming

Print ISBN: 978-3-319-11007-3

Electronic ISBN: 978-3-319-11008-0

Copyright Year: 2014

DOI
https://doi.org/10.1007/978-3-319-11008-0_7