Egon Balas

View Printable Version

University Professor of Industrial Administration and Applied Mathematics, The Thomas Lord Professor of Operations Research

Education:
  • Bolyai University - Dipl Licentiae - 1949
  • University of Brussels - Dr.Sc.Ec. - 1967
  • University of Paris - Dr.U. (Math.) - 1968
Areas of Expertise:
  • Operations Research
  • Mathematical Programming
Teaching and Research Interests:
  • Mathematical programming, in particular integer programming, combinatorial optimization, graphs, networks, polyhedral theory, disjunctive programming, projection and lifting, scheduling theory, facility location, logistics. Solution techniques for vertex packing and maximum clique problems, traveling salesman and related problems, set covering and partitioning, knapsack problems, general 0-1 programming problems; machine sequencing, scheduling of steel rolling mills, crew assignments.
Select Publications: 
  • Combining Lift-and-Project and Reduce-and-Split
    INFORMS Journal on Computing, To appear.
    (with: Gérard Cornuéjols, Tamas Kis, Giacomo Nannicini)

  • Generalized Intersection Cuts and a New Cut Generating Paradigm
    Mathematical Programming A, 2011.
    (with: François Margot)

  • Disjunctive Programming in M. Juenger et al (editors)
    50 Years of Integer Programming 1958-2008: From the Early Years to the State-of-the-Art, 2010; 289-340.

  • Lexicography and Degeneracy: Can a Pure Cutting Plane Algorithm Work?
    Mathematical Programming A 130, 2010; 153-176.
    (with: Matteo Fischetti, Arrigo Zanette)

  • On the Cycle Polytope of a Directed Graph and Its Relaxations
    Networks, 2009; 47-55.
    (with: Ruediger Stephan)

  • Generating Lift-and-Project Cuts from the LP Simplex Tableau: Open Source Implementation and Testing of New Variants
    Mathematical Programming Computation 1, 2009; 165-199.
    (with: Pierre Bonami)

  • Optimizing over the Split Closure
    Mathematical Programming A 113, 2008; 219-240.
    (with: Anureet Saxena)

  • Job Shop Scheduling with Setup Times, Deadlines and Precedence Constraints
    Journal of Scheduling 11, 208; 253-262.
    (with: Neil Simonetti, Alkiviadis Vazacopoulos)

  • Some Thoughts on the Development of Integer Programming During my Research Career
    Annals of Operations Research 149(Feb), 2007; 19-26.

  • New Facets of the STS Polytope Generated from Known Facets of the ATS Polytope
    Discrete Optimization 3, 2006; 3-19.
    (with: Robert Carr, Matteo Fischetti, Neil Simonetti)

  • The Vertex Separator Problem: Algorithms and Computations
    Mathematical Programming 103(3), 2005; 609-631.
    (with: Cid de Souza)

  • Projection, Lifting and Extended Formulation in Integer and Combinatorial Optimization
    Annals of Operations Research 140, 2005; 125-161.

  • On Unions and Dominants of Polytopes
    Mathematical Programming A(99), 2004; 223-239.
    (with: A. Bockmayr, N. Pisaruk, L. Wolsey)

  • A Precise Correspondence Between Lift-and-Project Cuts, Simple Disjunctive Cuts, and Mixed Integer Gomory Cuts for 0-1 Programming
    Mathematical Programming B(94), 2003; 221-245.
    (with: Michael Perregaard)

  • Linear Time Dynamic Programming Algorithms for Some New Classes of Restricted TSP's
    INFORMS Journal on Computing 13, 2001; 56-75.
    (with: Neil Simonetti)

  • Guided Local Search with Shifting Bottleneck for Job Shop Scheduling
    Management Science 44, 1998; 262-275.
    (with: Alkiviadis Vazacopoulos)

  • Disjunctive Programming: Properties of the Convex Hull of Feasible Points (Management Science Research Report, GSIA, 1974)
    Invited paper in Discrete Applied Mathematics 89, 1998; 1-44.

  • Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework (with S. Ceria and G. Cornuéjols)
    Management Science 42, 1996; 1229-1246.
    (with: Sebastian Ceria, Gérard Cornuéjols)

  • A Lift-and-Project Cutting Plane Algorithm for Mixed 0-1 Programs
    Mathematical Programming 58, 1993; 295-324.
    (with: Sebastian Ceria, Gérard Cornuéjols)

  • The Prize Collecting Traveling Salesman Problem I
    Networks 19, 1989; 621-636.

  • The Shifting Bottleneck Procedure for Job Shop Scheduling
    Management Science 34, 1988; 391-401.
    (with: Joseph Adams, Dan Zawack)

  • On The Maximum-Weight Clique Problem
    Mathematics of Operations Research 12, 1987; 522-536.
    (with: Vaclare Chvatal, Jarik Nesetril)

  • Disjunctive Programming and a Hierarchy of Relaxations for Discrete Optimization Problems
    SIAM Journal on Algebraic and Discrete Methods 6, 1985; 466-486.

  • The Perfectly Matchable Subgraph Polytope of a Bipartite Graph
    Networks 13, 1983; 495-516.
    (with: William Pulleybank)

  • An Algorithm for Large 0-1 Knapsack Problems
    Operations Research 28, 1980; 1130-1154.
    (with: Eitan Zemel)

  • Strengthening Cuts for Mixed Integer Programs
    European Journal of Operations Research 4, 1980; 224-234.
    (with: Robert Jeroslow)

  • Facets of the Knapsack Polytope
    Mathematical Programming 8, 1975; 146-164.

  • On the Set Covering Problem
    Operations Research 20(6), 1972; 1152-1161.
    (with: Maufred Padberg)

  • An Additive Algorithm for Linear Programming in Zero-One Variables
    Operations Research 13(4), 1965; 517-546.

    Additional Publications: 
      • Will to Freedom: A Perilous Journey Through Fascism and Communism, 469 pp., Syracuse University Press, (2000).

      • "ROLL-A-ROUND: A Scheduling System for Rolling Mills"
        Algorithmica, (1988).
        (with: Clarence Martin)

      • "Recommendations for the Overall Size of the Strategic Petroleum Reserve"
        in Hearing before the Committee on Interior and Insular Affairs, U.S. Senate, 95th Congress, February 4, 1977 (ed.) Congressional Records, Publication No. 95-10, (1977).

      Awards:
      • Academy of Sciences of Bologna, Italy, corresponding member - 2011
      • Honorary Doctorate, University of Liege, Belgium - 2008
      • National Academy of Engineering - 2006
      • IFORS Hall of Fame - 2006
      • Honorary Doctorate in Mathematics, University of Waterloo - 2005
      • Hungarian Academy of Science, external member - 2004-
      • INFORMS Fellow - 2002
      • Honorary Doctorate in Mathematics, Miguel Hernandez University, Elche, Spain - 2002
      • EURO Gold Medal - 2001
      • John von Neumann Theory Prize, INFORMS - 1995
      • Senior U.S. Scientist Award, Alexander von Humboldt Foundation - 1980-1981
      Editorial Boards:
      • Discrete Optimization, 2003-
      • Naval Logistics Research, 2002-
      • Journal of Combinatorial Optimization, 1996-
      • Computational Optimization and Applications, 1991-
      • Annals of Operations Research, 1983-
      • Zeitschrift für Operations Research, 1980-
      • Revue d'Automatique, Informatique et Recherche Opérationnelle, 1976-2003
      • Discrete Applied Mathematics, 1976-
      • European Journal of Operational Research, 1976-
      • Operations Research, 1966-1996
      Consulting:
      • Algorithmica, Inc.
      • Sumitomo Steel
      • LTV Steel
      • CombineNet, Inc.
      • American Airlines
      Courses Taught:
      [ Back ]