Abstract
Cutting plane methods are an important component in solving the mixed integer programming (MIP). By carefully studying the coefficient strengthening method, which is originally a presolving method, we are able to generalize this method to generate a family of valid inequalities called generalized coefficient strengthening (GCS) inequalities. The invariant property of the GCS inequalities is established under bound substitutions. Furthermore, we develop a separation algorithm for finding the violated GCS inequalities for a general mixed integer set. The separation algorithm is proved to have the polynomial time complexity. Extensive numerical experiments are made on standard MIP test sets, which demonstrate the usefulness of the resulting GCS separator.
Original language | English |
---|---|
Pages (from-to) | 289-306 |
Number of pages | 18 |
Journal | Journal of Global Optimization |
Volume | 70 |
Issue number | 1 |
DOIs | |
Publication status | Published - 1 Jan 2018 |
Externally published | Yes |
Keywords
- Coefficient strengthening
- Cutting plane method
- Mixed integer programming
- Separation algorithm