# Combinatorial Optimization - Cristofides N.

**Download**(direct link)

**:**

**9**> 10 11 12 13 14 15 .. 156 >> Next

8 Ophelie SIA CDC 6600 1972

9 Sciconic Scicon Univac 1100 Series 1976

10 Tempo Burroughs B7000 and B8000 Series 1975

11 XDLA ICL 1900 Series 1970

In the early 1970s, codes became available which could handle larger problems. Published computational experience distinguished between two generic types of problems. Type one problems are fundamentally large lps with a few integer variables, and type two problems are highly structured ilps. Type one problems are more common in practice, and different strategies are generally used for the two types. Much of the published computational experience relates the specific strategies used for handling the different type problems and is too detailed to relate here. We will relate only a few data points for some of these codes, and refer the reader to the individual articles for greater detail or to Geoffrion and Marsten (1972) or Garfinkel and Nemhauser (1972a) for additional detail. ^

An early version of Code 8 was described by Roy, Benayoun, and Tergny

(1970). Their rules were based to a large extent on penalties. They solve, for example, a problem with 1244 constraints and 3908 variables, 24 of which are integer, in about six minutes of CDC-6600 time. Code 5, based on similar concepts, is described by Benichou et al. (1971). A problem with 721 constraints and 1156 variables, 39 of which are integer, is solved in 18 minutes on the IBM 360/75. Tomlin (1970) also describes a similar algorithm and indicates that incorporation of the penalty (1.10) yields reduction in running times of up to 50 percent over an algorithm based on the penalties (1.7)(1.9).

In the middle 1970s it was discovered that penalty-based codes did not perform well for large problems. This discovery led to experimentation with pseudo costs. It is stressed in Forrest, Hirst, and Tomlin (1974) and Gauthier and Ribiere (1977) that the branching strategy is the key element of a branch and bound code and that pseudo costs are good tools for making these decisions. Both of these articles give detailed experience contrasting different strategies.

Branch and Bound Methods for Integer Programming

19

A good deal of experience is also reported in Breu and Burdet (1974) for

binary milps.

References

Agin, N. (1966). Optimum Seeking with Branch-and-Bound. Man. Sci., 13, B176-185.

Balas, E. (1968). A Note on the Branch-and-Bound Principle. Operations Research, 16, 442-445.

Beale, E. M. L. (1977). Branch and Bound Methods for Mathematical Programming Systems. Presented at the Conference on Discrete Optimization, Vancouver, B.C.

Beale, E. M. L. and R. E. Small (1965). Mixed Integer Programming by a Branch and Bound Technique. In W. A. Kalenich (Ed.), Proc. IFIP Congress, Vol. 2, Spartan Press, pp. 450-451.

Beale, E. M. L. and J. A. Tomlin (1970). Special Facilities in a General Mathematical Programming System for Nonconvex Problems Using Ordered Sets of Variables. In Proc. Fifth Int. Conf. on Operational Research, pp. 447-454.

Benichou, M. et al. (1971). Experiments in Mixed-Integer Linear Programming. Mathematical Programming, 1, 76-94.

Breu, R. and C. A. Burdet (1974). Branch and Bound Experiments in Zero-One Programming. Mathematical Programming Study, 2, 1-50.

Dakin, R. J. (1965). A Tree-Search Algorithm for Mixed Integer Programming Problems. Computer Journal, 8, 250-255.

Driebeek, N. J. (1966). An Algorithm for the Solution of Mixed Integer Programming Problems, Management Science, 12, 576-587.

Forrest, J. J. H., J. P. H. Hirst, and J. A. Tomlin (1974). Practical Solution of Large Mixed Integer Programming Problems with UMPIRE. Management Science, 20, 736-773.

Ciarfinkel, R. S. and G. L. Nemhauser (1972a). Integer Programming, Wiley, New ^ York.

Garfinkel, R. S. and G. L. Nemhauser (1972b). Optimal Set Covering: A Survey. In A. M. Geoffrion (Ed.), Perspectives in Optimization, Addison-Wesley. pp. 164-183.

Gauthier, J. M. and F. Ribiere (1977). Experiments in Mixed-Integer Linear Programming Using Pseudo-Costs. Math. Prog, 12, 26-47.

Geoffrion, A. M. (1974). Lagrangian Relaxation for Integer Programming. Mathematical Programming Study, 2, 82-114.

^.Geoffrion, A. M. and R. E. Marsten (1972). Integer Programming Algorithms: A Framework and State-of-the-Art Survey. Management Science, 18, 465-491.

Gomory, R. E. (1958). Outline of an Algorithm for Integer Solutions to Linear Programming. Bull. Amer. Math. Soc., 64, 175-178.

Gomory, R. E. (1965). On the Relation between Integer and Non-integer Solutions to Linear Programs. Proc. Nat. Acad. Science, 53, 260-265.

Hillier, F. S. (1969). Efficient Heuristic Procedures for Integer Linear Programming with an Interior. Operations Research, 17, 600-637.

Jeroslow, R. (1977). An Introduction to the Theory of Cutting Planes. Presented at the Summer School in Combinatorial Optimization, Urbino, Italy, June 1977.

Land, A. and A. G. Doig (1960). An Automatic Method of Solving Discrete Programming Problems. Econometrica, 28, 497-520.

Land, A. and S. Powell (1977). Computer Codes for Problems of Integer Programming. Presented at the Conference on Discrete Optimization, Vancouver, B.C., 1977.

**9**> 10 11 12 13 14 15 .. 156 >> Next