Explicit-Constraint Branching for Solving Mixed-Integer Programs

Thumbnail Image
Authors
Appleget, Jeffrey A.
Wood, R. Kevin
Subjects
facilities/equipment planning: capacity expansion; industries: electric; networks/graphs: applications, stochastic; programming: integer, algorithms, Benders decomposition, applications, stochastic.
Advisors
Date of Issue
2000
Date
Publisher
Language
Abstract
This paper develops a new generalized-branching technique called "explicit constraint branching" (ECB) to improve the performance of branch-and-bound algorithms for solving mixed-integer programs (MIPs). ECB adds structure to a MIP, in the frm of auxiliary constraints and auxiliary integer variables, to allow branching on groups of (original) integer variables that would not otherwise be possible. Computational tests on three sets of real-world MIPs demonstrate that ECB often improves solution times over standard branch and bound, sometimes dramatically.
Type
Article
Description
URI
https://hdl.handle.net/10945/38419
Series/Report No
Department
Operations Research (OR)
Organization
Identifiers
NPS Report Number
Sponsors
Funder
Format
Citation
Distribution Statement
Rights
defined in Title 17, United States Code, Section 101. Copyright protection is not available for this work in the United States.
Collections
Publications