Lp-based combinatorial problem solving |
| |
| Authors: | K Hoffman M Padberg |
| |
| Institution: | (1) Operations Research Division, National Bureau of Standards, 20899 Gaithersburg, Maryland, USA;(2) Graduate School of Business Administration, New York University, New York, New York, USA |
| |
| Abstract: | A tutorial outline of the polyhedral theory that underlies linear programming (LP)-based combinatorial problem solving is given. Design aspects of a combinatorial problem solver are discussed in general terms. Three computational studies in combinatorial problem solving using the polyhedral theory developed in the past fifteen years are surveyed: one addresses the symmetric traveling salesman problem, another the optimal triangulation of input/output matrices, and the third the optimization of large-scale zero-one linear programming problems. |
| |
| Keywords: | Integer programming polyhedral theory facets cutting planes traveling salesman problems triangulation of matrices large-scale zero-one problems software design computational testing |
| 本文献已被 SpringerLink 等数据库收录！ |
|
