Aggregation and Mixed Integer Rounding to Solve MIPs

Hugues Marchand () and Laurence A. Wolsey
Additional contact information
Hugues Marchand: Department of Operational Research, London School of Economics, Houghton Street, London WC2A 2AE, United Kingdom
Laurence A. Wolsey: Center for Operations Research and Econometrics, Université Catholique de Louvain, Voie du Roman pays, 34, Louvain-la-Neuve B-1348, Belgium

Operations Research, 2001, vol. 49, issue 3, 363-371

Abstract: In this paper, we discuss the use of mixed integer rounding (MIR) inequalities to solve mixed integer programs. MIR inequalities are essentially Gomory mixed integer cuts. However, as we wish to use problem structure, we insist that MIR inequalities be generated from constraints or simple aggregations of constraints of the original problem. This idea is motivated by the observation that several strong valid inequalities based on specific problem structure can be derived as MIR inequalities.Here we present and test a separation routine for such MIR inequalities that includes a heuristic row aggregation procedure to generate a single knapsack plus continuous variables constraint, complementation of variables, and finally the generation of an MIR inequality. Inserted in a branch-and-cut system, the results suggest that such a routine is a useful additional tool for tackling a variety of mixed integer programming problems.

Keywords: Integer programming; cutting planes: valid inequalities and solution for mixed integer programming problems (search for similar items in EconPapers)
Date: 2001
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (34)

Downloads: (external link)
http://dx.doi.org/10.1287/opre.49.3.363.11211 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:oropre:v:49:y:2001:i:3:p:363-371

Access Statistics for this article

More articles in Operations Research from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().