Generalized coefficient strengthening cuts for mixed integer programming

Wei Kun Chen, Liang Chen, Mu Ming Yang*, Yu Hong Dai

*Corresponding author for this work

Research output: Contribution to journalArticlepeer-review

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 languageEnglish
Pages (from-to)289-306
Number of pages18
JournalJournal of Global Optimization
Volume70
Issue number1
DOIs
Publication statusPublished - 1 Jan 2018
Externally publishedYes

Keywords

  • Coefficient strengthening
  • Cutting plane method
  • Mixed integer programming
  • Separation algorithm

Fingerprint

Dive into the research topics of 'Generalized coefficient strengthening cuts for mixed integer programming'. Together they form a unique fingerprint.

Cite this