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. |
Year | DOI | Venue |
---|---|---|
2018 | https://doi.org/10.1007/s10898-017-0562-5 | J. Global Optimization |
Keywords | Field | DocType |
Mixed integer programming,Cutting plane method,Separation algorithm,Coefficient strengthening | Integer,Discrete mathematics,Cutting-plane method,Polynomial time complexity,Mathematical optimization,Integer programming,Separation algorithm,Invariant (mathematics),Mathematics | Journal |
Volume | Issue | ISSN |
70 | 1 | 0925-5001 |
Citations | PageRank | References |
0 | 0.34 | 9 |
Authors | ||
4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Wei-Kun Chen | 1 | 2 | 1.08 |
liang chen | 2 | 40 | 24.38 |
Mu-Ming Yang | 3 | 6 | 2.82 |
Yu-Hong Dai | 4 | 1079 | 78.67 |