BIXBY, ROBERT E. / Mathématiques / Chercheurs

Centre International de Recherche Scientifique


Mathématiques / BIXBY, ROBERT E.


Research Professor of Management in Rice University’s Jesse H. Jones School of Management, and Noah Harding Professor Emeritus of Computational and Applied Mathematics in Rice University’s Department of Computational and Applied Mathematics, Houston, Texas, U.S.A.

Thèmes de recherche

Solution of large-scale linear programming problems and the application of linear programming methods to integer programming; parallel methods for integer and linear programming; algorithms for combinatorial optimization problems

Bixby\'s research interests include the solution of large-scale linear programming problems, the application of linear programming methods to integer programming, parallel methods for integer and linear programming, and algorithms for combinatorial optimization problems. \"I\'m simply fascinated by being able to solve numerically intensive, real-world problems, especially ones that were previously unsolved,\" he says. \"I find great satisfaction in looking at large volumes of numerical data and deducing new, generally applicable solution strategies and algorithms.\"

Among the areas in which linear and integer programming models have found application are transportation, finance, manufacturing, forestry, agriculture, oil and gas exploration, food processing, health care, and textiles. For example, the airline industry applies these techniques in managing crew, fleet, and maintenance scheduling. Bixby, in a joint effort with researchers from Princeton, Rutgers, and Cray Research, implemented a new algorithm for the solution of the linear-programming relaxation of a 13 million variable, real-world, crew-scheduling model, the total solution time was under five minutes.

In 1990, Bixby began working together with colleagues from Rutgers, Bell Communications Research, and AT&T Bell Laboratories on the Traveling Salesman Problem (TSP). This problem has challenged scientists, mathematicians, and engineers for decades. A central vehicle for advances in the theory of integer programming, the TSP is the problem, given a set of points or “cities”, to find the shortest route starting at some fixed point and visiting every other point exactly once. When Bixby and his colleagues began working on the TSP, the largest solved “real” instance was one with 2,329 cities. In 1992, they increased that number to 3,038. That year, Discover magazine selected their work as one of its top 10 stories in science. Since then, the researchers have continued to develop innovative algorithms that have repeatedly broken their own records, and in 2001, they found a provably optimal solution for a 15, 112-city instance, an optimal tour plan for visiting all the cities in the present-day Germany.

Prix et récompenses

- Co-founder and Chairman of the Board, CPLEX Optimization, Inc., 1989-1997: Integer and linear programming software components. Company sold to ILOG, Inc., 1997. Board Member, ILOG, Inc., (1997-2000)

- Editor, Linear Algebra and its Applications (Special Issue), (1989), Editor-in-Chief of Mathematical Programming (1989-1994)

- Elected to the National Academy of Engineering, 1997.

- Mathematical Programming Society Beale-Orchard-Hayes Prize for Computational Mathematical Programming, 2000.

- Member of the following Professional Societies : Mathematical Programming Society, INFORMS, Society for Industrial and Applied Mathematics, Association for Computing Machinery

- President, ILOG Technical Advisory Board, (2000-Present)

- Chairman of Mathematical Programming Society (2001-Present)


On the Length-Width Inequality for Compound Clutters (1971), Journal of Combinatorial Theory 11 246-248

Decomposition Theory for Path Clutters and Flows (with L.J. Billera) (1971). Proceedings of 1971 NATO Conference: Applications of Optimization Methods for Large-Scale Resource Allocation Problems

A Characterization of Pareto Surfaces (with L.J. Billera) (1973). Proceedings of the American Mathematical Society 41 261-267

A Characterization of Polyhedral Market Games (with L.J. Billera) (1973). International Journal of Game Theory 2 253-261

l - Matrices and Characterization of Binary Matroids (1974). Discrete Mathematics 8 139-145

The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n-Bonds (1974). Bulletin of the American Mathematical Society 80 700-704

Market Representations of n-Person Games (with L.J. Billera) (1974). Bulletin of the American Mathematical Society 80 522-526

A Composition for Matroids (1975). Journal of Combinatorial theory (B) 18 59-72

The Minimum Number of Edges and Vertices in a Graph with Edge Connectivity n and m n-Bonds (1976). Networks 5 253-298

Pareto Surfaces of Complexity 1 (with L.J. Billera) (1976). SIAM Journal on Applied Mathematics 30 81-89

A Strengthened Form of Tutte’s Characterization of Regular Matroids (1976). Journal of Combinatorial Theory (B) 20 216-221

Kuratowski’s and Wagner’s Theorems for Matroids (1977). Journal of Combinatorial Theory (B) 22 31-53

A Simple Proof that Every Matroid is an Intersection of Fundamental Transversal Matroids (1977). Discrete Mathematics 18 311-312

The Solution to a Matroid Problem of Knuth (1978). Discrete Mathematics 21 87-88

An Efficient Algorithm for Finding Hamitonian Circuits in Certain Graphs (with Da-Lun Wang) (1978). Mathematical Programming Study No. 8: Polyhedral Combinatories (Dedicated to the memory of D. R. Fulkerson) 35-49

On Reid’s Characterization of the Ternary Matroids (1979). Journal of Combinatorial Theory (B) 26 174-203

Matroids, Graphs and 3-connectivity (with W. H. Cunningham) (1979). In Graph Theory and Related topics J. A. Bondy and U. S. R. Murty (eds.), Academic Press, New York 91-103

Converting Linear Programs to Network Problems (with W. H. Cunningham) (1980). Mathematics of Operations Research 5 321-357

Matroids and Operations Research (1981). In Advanced techniques in the Practice of Operations Research H.J. Greenberg, F. H. Murphy, and S. H. Shaw, (eds.), vol. 4 in Publications in Operations Research Series, S. I. Gas (ed.), North-Holland, New York, 333-458

Hidden Structure in Linear Programs (1981). In Computer-Assisted Analysis and Model Simplifications H.J. Greenberg and J. Maybee (eds.), Academic Press, 327-360

A Simple Theorem on 3-Connectivity (1982). Linear Algebra and Its Applications 45 123-126

Algorithms for Two Version of Graph Realization and an Application to Linear Programming (1983). In Progress in Combinatorial Optimization W. R. Pulleyblank (ed.), Academic Press, 39-68

A Composition for Perfect Graphs (1984). Annals of Discrete Mathematics 21 221-224

The Partial Order of a Polymatroid Extreme point (with W. H. Cunningham and D. M. Topkis) (1985). Mathematics of Operations Research 10 367-378

On chains of 3-Connected Matroids (with C. R. Coullard) (1986). Discrete Applied Mathematics 15 155-166

A Note on Detecting Simple Redundancies in Linear Systems (with D. K. Wagner) (1986). Operations Research Letters 6 15-17

Finding A Small 3-Connected Minor Maintaining a Fixed Minor and a Fixed Element (with C.R. Coullard) (1987). Combinatorica 7 231-242

Packing and covering by Integral Feasible Flows in Integral Supply-Demand Networks (with O. M.-C. Marcotte and L. E. Trotter, Jr.) (1987). Mathematical Programming 39 231-239

Short Co circuits in Binary Matroids (with W. H. Cunningham) (1987). European Journal of Combinatorics 8 213-225

An Almost Linear-Time Algorithm for Graph Realization (with D. K. Wagner) (1988). Mathematics of Operations Research 13 99-123

Finding Embedded Network rows in Linear Programs I: Extraction Heuristics (with R. F. Fourer) (1988). Management Science 34 342-376

Adjoints of Binary Matroids (with C.R. Coullard) (1984). European Journal of Combinatorics 9 139-147

A Short Proof of a the Truemper-Tseng Theorem on Max-Flow Min-Cut Matroids (with Arvind Rajan) (1989). Linear Algebra and its Applications 114 277-292

Implementing the Simplex Method: The Initial Basis (1992), ORSA Journal on Computing 4 267-284

Very Large-Scale Linear Programming: A Case Study in Combining Interior Point and Simplex Methods (with J. W. Gregory, I. J. Lustig, R. E. Marsten and D. F. Shanno) (1992). Operations Research 40 885-898

MIPLIB: A Test Set of Mixed Integer Programming Problems (with E. A. Boyd and R. Indovina) (1992). SIAM News 25

The MIPLIB Mixed Integer Programming Library (with E. A. Boyd, S. S. Dadmehr, and R. Indovina) (1993) COAL Bulletin 22

Recovering on Optimal LP Basis from an Interior Point Solution (with Matthew J. Saltzman) (1994). Operations Research Letters 15 169-178

Commentary: Progress in Linear Programming (1994). ORSA Journal on Computing 6 15-22

Automatic Data Layout using 0-1 Integer Programming (with K. Kennedy and U. Kremer) (1994), IFIP Transactions A: Parallel Architectures and Compilation Techniques 111-122

Matroid Optimization and Algorithms (with W. H. Cunningham) (1995). A chapter in Handbook of Combinatorics R. Graham, M. Grötschel and L. Lovász (ed.)

Solving Nonlinear Integer Programs with a Subgradient Approach on Parallel Computers (with J. Dennis and Z. Wu) (1996). In Applications on Advanced Architecture Computers, Greg Astfalk, (ed.), SIAM, 277-286

On the Solution of Traveling Salesman Problems (with D.A. Applegate, V. Chvátal, and W. Cook) (1998). Documenta Mathematica Journal der Deutschen Mathematiker-Vereinigung, International Congress of Mathematicians 645-656

Solving a Truck Dispatching Scheduling Problem Using Branch-and-Cut (with Eva K-Y Lee) (1998). Operations Research 46 355-367

An updated Mixed Integer Programming Library: MIPLIB 3.0 (with S. Ceria, C. M. McZeal, and M. W. P. Savelsbergh) (1998). Optima 54 12-15

Computational Experience with Parallel Mixed Integer Programming in Distributed Environment (with W. Cook, A. Cox and E. Lee) (1999). Annals of Operations Research – Parallel Optimization 90 19-43

MIP: Theory and Practice – Closing the Gap (with M. Fenelon, Z. Gu, E. Rothberg and R. Wunderling) (2000) in System Modelling and Optimization: Methods, Theory and Applications, Kluwer, (eds.) M. J. D. Powell and S. Scholtes

Parallelizing the Dual Simplex Method (with A. Martin) (2000). INFORMS Journal on Computing 12 45-56

Market Split and Basis Reduction: Towards a Solution of the Cornuejols-Dawande Instances (with K. Aardal, C.A.J. Hurkens, A.K. Lenstra and J.W. Smeltink) (2000). INFORMS Journal on Computing 12 192-202

TSP cuts which do not conform to the template paradigm (with D. Applegate, V. Chvátel, and W. Cook) (2001). To appear in Computational Combinatorial Optimization.

Solving Real-World Linear Programs: A Decade and More of Progress (2001). To appear in Operations Research.

Mentions légales - Contact

Copyright © 2013 - - Tous droits réservés