Egon Balas - Publications

Affiliations: 
Carnegie Mellon University, Pittsburgh, PA 
Area:
Operations Research, Computer Science, Applied Mathematics

115 high-probability publications. We are testing a new system for linking publications to authors. You can help! If you notice any inaccuracies, please sign in and mark papers as correct or incorrect matches. If you identify any major omissions or other inaccuracies in the publication list, please let us know.

Year Citation  Score
2020 Balas E, Serra T. When Lift-and-Project Cuts Are Different Informs Journal On Computing. 32: 822-834. DOI: 10.1287/Ijoc.2019.0943  0.427
2020 Kazachkov AM, Nadarajah S, Balas E, Margot F. Partial hyperplane activation for generalized intersection cuts Mathematical Programming Computation. 12: 69-107. DOI: 10.1007/S12532-019-00166-2  0.44
2016 Balas E, Kis T. On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts Mathematical Programming. 1-30. DOI: 10.1007/S10107-015-0975-1  0.38
2015 Balas E, Kis T. Intersection cuts - Standard versus restricted Discrete Optimization. 18: 189-192. DOI: 10.1016/J.Disopt.2015.10.001  0.389
2013 Balas E, Cornuéjols G, Kis T, Nannicini G. Combining Lift-and-Project and Reduce-and-Split Informs Journal On Computing. 25: 475-487. DOI: 10.1287/Ijoc.1120.0515  0.482
2013 Balas E, Margot F. Generalized intersection cuts and a new cut generating paradigm Mathematical Programming. 137: 19-35. DOI: 10.1007/S10107-011-0483-X  0.45
2012 Balas E, Qualizza A. Monoidal cut strengthening revisited Discrete Optimization. 9: 40-49. DOI: 10.1016/J.Disopt.2011.11.002  0.683
2012 Balas E, Fischetti M, Zanette A. A hard integer program made easy by lexicography Mathematical Programming. 135: 509-514. DOI: 10.1007/S10107-011-0450-6  0.471
2011 Balas E. Projecting systems of linear inequalities with binary variables Annals of Operations Research. 188: 19-31. DOI: 10.1007/S10479-009-0623-3  0.425
2011 Zanette A, Fischetti M, Balas E. Lexicography and degeneracy: Can a pure cutting plane algorithm work? Mathematical Programming. 130: 153-176. DOI: 10.1007/S10107-009-0335-0  0.473
2010 Balas E, Fischetti M, Zanette A. On the enumerative nature of Gomory's dual cutting plane method Mathematical Programming. 125: 325-351. DOI: 10.1007/S10107-010-0392-4  0.462
2009 Balas E, Bonami P. Generating lift-and-project cuts from the LP simplex tableau: Open source implementation and testing of new variants Mathematical Programming Computation. 1: 165-199. DOI: 10.1007/S12532-009-0006-4  0.467
2009 Balas E, Stephan R. On the cycle polytope of a directed graph and its relaxations Networks. 54: 47-55. DOI: 10.1002/Net.V54:1  0.328
2008 Balas E, Hoffman AJ, McCormick ST. A Special Issue in Memory of George B. Dantzig Discrete Optimization. 5: 145-150. DOI: 10.1016/J.Disopt.2007.12.001  0.318
2008 Balas E, Simonetti N, Vazacopoulos A. Job shop scheduling with setup times, deadlines and precedence constraints Journal of Scheduling. 11: 253-262. DOI: 10.1007/S10951-008-0067-7  0.412
2008 Balas E, Saxena A. Optimizing over the split closure Mathematical Programming. 113: 219-240. DOI: 10.1007/S10107-006-0049-5  0.515
2008 Zanette A, Fischetti M, Balas E. Can pure cutting plane algorithms work? Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 5035: 416-434. DOI: 10.1007/978-3-540-68891-4_29  0.316
2007 Balas E. Some thoughts on the development of integer programming during my research career Annals of Operations Research. 149: 19-26. DOI: 10.1007/S10479-006-0093-9  0.35
2006 Balas E, Carr R, Fischetti M, Simonetti N. New facets of the STS polytope generated from known facets of the ATS polytope Discrete Optimization. 3: 3-19. DOI: 10.1016/J.Disopt.2005.10.001  0.46
2005 Balas E. Projection, lifting and extended formulation in integer and combinatorial optimization Annals of Operations Research. 140: 125-161. DOI: 10.1007/S10479-005-3969-1  0.441
2005 Balas E, De Souza CC. The vertex separator problem: A polyhedral investigation Mathematical Programming. 103: 583-608. DOI: 10.1007/S10107-005-0574-7  0.488
2005 De Souza C, Balas E. The vertex separator problem: Algorithms and computations Mathematical Programming. 103: 609-631. DOI: 10.1007/S10107-005-0573-8  0.486
2004 Balas E. Logical constraints as cardinality rules: Tight representation Journal of Combinatorial Optimization. 8: 115-128. DOI: 10.1023/B:Joco.0000031413.33955.62  0.449
2004 Balas E, Schmieta S, Wallace C. Pivot and shift - A mixed integer programming heuristic Discrete Optimization. 1: 3-12. DOI: 10.1016/J.Disopt.2004.03.001  0.475
2004 Balas E, Bockmayr A, Pisaruk N, Wolsey L. On unions and dominants of polytopes Mathematical Programming. 99: 223-239. DOI: 10.1007/S10107-003-0432-4  0.385
2003 Balas E, Perregaard M. A precise correspondence between lift-and-project cuts, simple disjunctive cuts, and mixed integer gomory cuts for 0-1 programming Mathematical Programming. 94: 221-245. DOI: 10.1007/S10107-002-0317-Y  0.461
2002 Balas E, Perregaard M. Lift-and-project for Mixed 0-1 programming: Recent progress Discrete Applied Mathematics. 123: 129-154. DOI: 10.1016/S0166-218X(01)00340-7  0.464
2001 Balas E, Ceria S, Dawande M, Margot F, Pataki G. Octane: A new heuristic for pure 0-1 programs Operations Research. 49: 207-225. DOI: 10.1287/Opre.49.2.207.13535  0.474
2001 Balas E, Simonetti N. Linear Time Dynamic-Programming Algorithms for New Classes of Restricted TSPs: A Computational Study Informs Journal On Computing. 13: 56-75. DOI: 10.1287/Ijoc.13.1.56.9748  0.43
2001 Balas E. Projection and lifting in combinatorial optimization Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2241: 26-56. DOI: 10.1007/3-540-45586-8_2  0.335
2001 Perregaard M, Balas E. Generating cuts from multiple-term disjunctions Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 2081: 348-360.  0.347
2000 Balas E, Oosten M. On the cycle polytope of a directed graph Networks. 36: 34-46. DOI: 10.1002/1097-0037(200008)36:1<34::Aid-Net4>3.0.Co;2-2  0.38
1999 Balas E, Fischetti M. Lifted cycle inequalities for the asymmetric traveling salesman problem Mathematics of Operations Research. 24: 273-292. DOI: 10.1287/Moor.24.2.273  0.331
1999 Balas E. New classes of efficiently solvable generalized Traveling Salesman Problems Annals of Operations Research. 86: 529-558. DOI: 10.1023/A:1018939709890  0.402
1998 Balas E, Zemel E. Critical Cutsets of Graphs and Canonical Facets of Set Packing Polytopes Mathematics of Operations Research. 23: 1022-1022. DOI: 10.1287/Moor.23.4.1022  0.348
1998 Balas E, Vazacopoulos A. Guided local search with shifting bottleneck for job shop scheduling Management Science. 44: 262-275. DOI: 10.1287/Mnsc.44.2.262  0.34
1998 Balas E, Zemel E, Todd MJ. Error Noted in a Paper by Jacobs, Silan, and Clemson Interfaces. 28: 121-122. DOI: 10.1287/Inte.28.2.121  0.313
1998 Balas E, Lancia G, Serafini P, Vazacopoulos A. Job Shop Scheduling with Deadlines Journal of Combinatorial Optimization. 1: 329-353. DOI: 10.1023/A:1009750409895  0.383
1998 Balas E, Niehaus W. Optimized Crossover-Based Genetic Algorithms for the Maximum Cardinality and Maximum Weight Clique Problems Journal of Heuristics. 4: 107-122. DOI: 10.1023/A:1009646528813  0.355
1998 Balas E. Disjunctive programming: Properties of the convex hull of feasible points Discrete Applied Mathematics. 89: 3-44. DOI: 10.1016/S0166-218X(98)00136-X  0.489
1997 Balas E, Fischetti M. On the monotonization of polyhedra Mathematical Programming, Series B. 78: 59-84. DOI: 10.1007/Bf02614506  0.4
1997 Balas E. A modified lift-and-project procedure Mathematical Programming, Series B. 79: 19-31. DOI: 10.1007/Bf02614309  0.513
1996 Balas E, Carrera MC. A dynamic subgradient-based branch-and-bound procedure for set covering Operations Research. 44: 875-890. DOI: 10.1287/Opre.44.6.875  0.455
1996 Balas E, Ceria S, Cornuéjols G. Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework Management Science. 42: 1229-1246. DOI: 10.1287/Mnsc.42.9.1229  0.451
1996 Balas E, Ceria S, Cornuéjols G, Natraj N. Gomory cuts revisited Operations Research Letters. 19: 1-9. DOI: 10.1016/0167-6377(96)00007-7  0.495
1996 Balas E, Xue J. Weighted and Unweighted Maximum Clique Algorithms with Upper Bounds from Fractional Coloring Algorithmica (New York). 15: 397-412. DOI: 10.1007/Bf01955041  0.445
1996 Simonetti N, Balas E. Implementation of a linear time algorithm for certain generalized traveling salesman problems Lecture Notes in Computer Science (Including Subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics). 1084: 316-329.  0.362
1996 Balas E, Ceria S, Cornuéjols G. Mixed 0-1 programming by lift-and-project in a branch-and-cut framework Management Science. 42: 1229-1246.  0.349
1995 Balas E, Lenstra JK, Vazacopoulos A. The one-machine problem with delayed precedence constraints and its use in job shop scheduling Management Science. 41: 94-109. DOI: 10.1287/Mnsc.41.1.94  0.409
1995 Balas E, Fischetti M, Pulleyblank WR. The precedence-constrained asymmetric traveling salesman polytope Mathematical Programming. 68: 241-265. DOI: 10.1007/Bf01585767  0.491
1995 Balas E. The prize collecting traveling salesman problem: II. Polyhedral results Networks. 25: 199-216. DOI: 10.1002/Net.3230250406  0.441
1993 Balas E, Qi L. Linear-time separation algorithms for the three-index assignment polytope Discrete Applied Mathematics. 43: 1-12. DOI: 10.1016/0166-218X(93)90164-J  0.341
1993 Balas E, Fischetti M. A lifting procedure for the asymmetric traveling salesman polytope and a large new class of facets Mathematical Programming. 58: 325-352. DOI: 10.1007/Bf01581274  0.395
1993 Balas E, Ceria S, Cornuéjols G. A lift-and-project cutting plane algorithm for mixed 0-1 programs Mathematical Programming. 58: 295-324. DOI: 10.1007/Bf01581273  0.434
1992 Balas E, Fischetti M. The Fixed-Outdegree 1-Arborescence Polytope Mathematics of Operations Research. 17: 1001-1018. DOI: 10.1287/Moor.17.4.1001  0.32
1992 Balas E, Xue J. Addendum: minimum weighted coloring of triangulated graphs, with application to maximum weight vertex packing and clique finding in arbitrary graphs Siam Journal On Computing. 21: 1000-1000. DOI: 10.1137/0221058  0.4
1991 Balas E, Saltzman MJ. An algorithm for the three-index assignment problem Operations Research. 39: 150-161. DOI: 10.1287/Opre.39.1.150  0.421
1991 Balas E, Zemel E, Todd MJ. Probabilistic models for linear programming Mathematics of Operations Research. 16: 671-693. DOI: 10.1287/Moor.16.4.671  0.448
1991 Balas E, Miller D, Pekny J, Toth P. A Parallel Shortest Augmenting Path Algorithm for the Assignment Problem Journal of the Acm (Jacm). 38: 985-1004. DOI: 10.1145/115234.115349  0.441
1989 Balas E. The asymmetric assignment problem and some new facets of the traveling salesman polytope on a directed graph Siam Journal On Discrete Mathematics. 2: 425-451. DOI: 10.1137/0402038  0.417
1989 Balas E. Robert G. Jeroslow 1942 – 1988 Annals of Discrete Mathematics. 40. DOI: 10.1016/S0167-5060(08)70518-1  0.337
1989 Balas E, Saltzman MJ. Facets of the three-index assignment polytope Discrete Applied Mathematics. 23: 201-229. DOI: 10.1016/0166-218X(89)90014-0  0.464
1989 Balas E, Pulleyblank WR. The perfectly Matchable Subgraph Polytope of an arbitrary graph Combinatorica. 9: 321-337. DOI: 10.1007/Bf02125345  0.344
1989 Balas E, Ng SM. On the set covering polytope: II. Lifting the facets with coefficients in {0, 1, 2} Mathematical Programming. 45: 1-20. DOI: 10.1007/Bf01589093  0.395
1989 Balas E, Tama JM, Tind J. Sequential convexification in reverse convex and disjunctive programming Mathematical Programming. 44: 337-350. DOI: 10.1007/Bf01587096  0.485
1989 Balas E, Ng SM. On the set covering polytope: I. All the facets with coefficients in {0, 1, 2} Mathematical Programming. 43: 57-69. DOI: 10.1007/Bf01582278  0.462
1989 Balas E. The Prize collecting traveling salesman problem Networks. 19: 621-636. DOI: 10.1002/Net.3230190602  0.404
1989 Balas E, Yu CS. On graphs with polynomially solvable maximum‐weight clique problem Networks. 19: 247-253. DOI: 10.1002/Net.3230190206  0.4
1988 Adams J, Balas E, Zawack D. The Shifting Bottleneck Procedure for Job Shop Scheduling Management Science. 34: 391-401. DOI: 10.1287/Mnsc.34.3.391  0.406
1988 Balas E. On the convex hull of the union of certain polyhedra Operations Research Letters. 7: 279-283. DOI: 10.1016/0167-6377(88)90058-2  0.339
1987 Balas E, Chvátal V, Nešetřil J. On the maximum weight clique problem Mathematics of Operations Research. 12: 522-535. DOI: 10.1287/Moor.12.3.522  0.401
1987 Balas E, Nauss R, Zemel E. Comment on 'some computational results on real 0-1 knapsack problems' Operations Research Letters. 6: 139-140. DOI: 10.1016/0167-6377(87)90028-9  0.342
1986 Balas E, Yu CS. Finding a maximum clique in an arbitrary graph Siam Journal On Computing. 15: 1054-1068. DOI: 10.1137/0215075  0.376
1986 Balas E. A fast algorithm for finding an edge-maximal subgraph with a TR-formative coloring Discrete Applied Mathematics. 15: 123-134. DOI: 10.1016/0166-218X(86)90036-3  0.359
1985 Balas E. Disjunctive programming and a hierarchy of relaxations for discrete optimization problems Siam Journal On Algebraic and Discrete Methods. 6: 466-486. DOI: 10.1137/0606047  0.455
1984 Balas E. A Sharp Bound on the Ratio Between Optimal Integer and Fractional Covers Mathematics of Operations Research. 9: 1-5. DOI: 10.1287/Moor.9.1.1  0.376
1984 Balas E, Mazzola JB. Nonlinear 0-1 programming: II. Dominance relations and algorithms Mathematical Programming. 30: 22-45. DOI: 10.1007/Bf02591797  0.44
1984 Balas E, Mazzola JB. Nonlinear 0-1 programming: I. Linearization techniques Mathematical Programming. 30: 1-21. DOI: 10.1007/Bf02591796  0.402
1983 Balas E, Bergthaller C. Benders's method revisited Journal of Computational and Applied Mathematics. 9: 3-12. DOI: 10.1016/0377-0427(83)90024-9  0.494
1983 Balas E, Landweer PR. Traffic assignment in communication satellites Operations Research Letters. 2: 141-147. DOI: 10.1016/0167-6377(83)90045-7  0.317
1983 Balas E, Pulleyblank WR. The perfectly matchable subgraph polytope of a bipartite graph Networks. 13: 495-516. DOI: 10.1002/Net.3230130405  0.403
1981 Balas E. Integer and Fractional Matchings North-Holland Mathematics Studies. 59: 1-13. DOI: 10.1016/S0304-0208(08)73453-4  0.327
1981 Balas E, Christofides N. A restricted Lagrangean approach to the traveling salesman problem Mathematical Programming. 21: 19-46. DOI: 10.1007/Bf01584228  0.479
1980 Balas E, Zemel E. An Algorithm for Large Zero-One Knapsack Problems Operations Research. 28: 1130-1154. DOI: 10.1287/Opre.28.5.1130  0.469
1980 Balas E, Martin CH. Pivot and Complement--A Heuristic for 0-1 Programming Management Science. 26: 86-96. DOI: 10.1287/Mnsc.26.1.86  0.491
1980 Balas E, Jeroslow RG. Strengthening cuts for mixed integer programs European Journal of Operational Research. 4: 224-234. DOI: 10.1016/0377-2217(80)90106-X  0.485
1979 Balas E, Padberg MW. Adjacent vertices of the all 0-1 programming polytope Rairo-Operations Research. 13: 3-12. DOI: 10.1051/Ro/1979130100031  0.387
1979 Balas E, Guignard M. Report of the Session on. Branch and Bound/Implicit Enumeration Annals of Discrete Mathematics. 5: 185-191. DOI: 10.1016/S0167-5060(08)70348-0  0.5
1978 Balas E, Zemel E. Facets of the Knapsack Polytope From Minimal Covers Siam Journal On Applied Mathematics. 34: 119-148. DOI: 10.1137/0134010  0.418
1977 Balas E. Some Valid Inequalities for the Set Partitioning Problem Annals of Discrete Mathematics. 1: 13-47. DOI: 10.1016/S0167-5060(08)70725-8  0.478
1977 Balas E. A note on duality in disjunctive programming Journal of Optimization Theory and Applications. 21: 523-528. DOI: 10.1007/Bf00933095  0.446
1977 Balas E, Zemel E. Graph substitution and set packing polytopes Networks. 7: 267-284. DOI: 10.1002/Net.3230070307  0.384
1977 Balas E, Samuelsson H. A node covering algorithm Naval Research Logistics Quarterly. 24: 213-233. DOI: 10.1002/Nav.3800240203  0.421
1976 Balas E, Padberg MW. Set Partitioning: A survey Siam Review. 18: 710-760. DOI: 10.1137/1018115  0.391
1975 Balas E, Padberg M. On the Set-Covering Problem: II. An Algorithm for Set Partitioning Operations Research. 23: 74-90. DOI: 10.1287/Opre.23.1.74  0.462
1975 Balas E. Nonconvex Quadratic Programming via Generalized Polars Siam Journal On Applied Mathematics. 28: 335-349. DOI: 10.1137/0128029  0.436
1975 Balas E. Facets of the knapsack polytope Mathematical Programming. 8: 146-164. DOI: 10.1007/Bf01580440  0.471
1975 Balas E, Zoltners A. Intersection cuts from outer polars of truncated cubes Naval Research Logistics Quarterly. 22: 477-496. DOI: 10.1002/Nav.3800220307  0.436
1973 Balas E. Technical Note-A Note on the Group Theoretic Approach to Integer Programming and the 0-1 Case Operations Research. 21: 321-322. DOI: 10.1287/Opre.21.1.321  0.437
1972 Balas E, Padberg MW. On the Set-Covering Problem Operations Research. 20: 1152-1161. DOI: 10.1287/Opre.20.6.1152  0.404
1972 Balas E, Jeroslow R. Canonical Cuts on the Unit Hypercube Siam Journal On Applied Mathematics. 23: 61-69. DOI: 10.1137/0123007  0.418
1972 Balas E. Ranking the facets of the octahedron Discrete Mathematics. 2: 1-15. DOI: 10.1016/0012-365X(72)90056-8  0.489
1972 Balas E. Integer programming and convex analysis: Intersection cuts from outer polars Mathematical Programming. 2: 330-382. DOI: 10.1007/Bf01584553  0.463
1971 Balas E, Bowman VJ, Glover FW, Sommer D. An Intersection Cut from the Dual of the Unit Hypercube Operations Research. 19: 40-44. DOI: 10.1287/Opre.19.1.40  0.424
1971 Balas E. Intersection Cuts—A New Type of Cutting Planes for Integer Programming Operations Research. 19: 19-39. DOI: 10.1287/Opre.19.1.19  0.391
1971 Balas E. A duality theorem and an algorithm for (mixed-) integer nonlinear programming Linear Algebra and Its Applications. 4: 341-352. DOI: 10.1016/0024-3795(71)90005-X  0.387
1970 Balas E. Machine sequencing: Disjunctive graphs and degree‐constrained subgraphs Naval Research Logistics Quarterly. 17: 1-10. DOI: 10.1002/Nav.3800170102  0.45
1969 Balas E. Machine Sequencing Via Disjunctive Graphs: An Implicit Enumeration Algorithm Operations Research. 17: 941-957. DOI: 10.1287/Opre.17.6.941  0.436
1969 Balas E. Duality in Discrete Programming: II. The Quadratic Case Management Science. 16: 14-32. DOI: 10.1287/Mnsc.16.1.14  0.487
1968 Balas E. Letter to the Editor—A Note on the Branch-and-Bound Principle Operations Research. 16: 442-445. DOI: 10.1287/Opre.16.2.442  0.319
1967 Balas E. Discrete Programming by the Filter Method Operations Research. 15: 915-957. DOI: 10.1287/Opre.15.5.915  0.459
1966 Balas E. An Infeasibility-Pricing Decomposition Method for Linear Programs Operations Research. 14: 847-873. DOI: 10.1287/Opre.14.5.847  0.445
1966 Balas E. The Dual Method for the Generalized Transportation Problem Management Science. 12: 555-568. DOI: 10.1287/Mnsc.12.7.555  0.391
1965 Balas E. An Additive Algorithm for Solving Linear Programs with Zero-One Variables Operations Research. 13: 517-546. DOI: 10.1287/Opre.13.4.517  0.457
1965 Balas E. Solution of Large-Scale Transportation Problems Through Aggregation Operations Research. 13: 82-93. DOI: 10.1287/Opre.13.1.82  0.346
Show low-probability matches.