 |
|
|
|
1999 MCS Divisional Seminars & Colloquia |
|
Solving the Network Design/Expansion Problem by Branch-and-Cut
|
|
| Abstract | In this talk we will present a summary of a recent study on solving
network design/expansion problems with a branch-and-cut algorithm. The algorithm is based
on strong cutting planes derived for a single node relaxation of network flow
problems with additive variable upper bounds. This type of relaxation arises in
network design/expansion problems as well as in production planning problems with
setup times. We first derive two classes of valid inequalities for this structure
and address their strength. Then we generalize our results through sequence
independent lifting of the valid inequalities for lower-dimensional projections. Our
computational experience with large network expansion problems indicates that these
inequalities are very effective in improving the quality of the linear programming
relaxations. This is a joint work with G. L. Nemhauser and M. W. P. Savelsbergh. |
| [MCS | Research | Resources | People | Collaboration | Software | Publications | Information] | |||
|
