Explicit-Constraint Branching for Solving Mixed-Integer Programs

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 form 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.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Jan 01, 2000
Accession Number
ADA492253

Entities

People

  • Jeffrey A. Appleget
  • R. Kevin Wood

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Human Systems

DTIC Thesaurus Topics

  • Algorithms
  • Applied Mathematics
  • Computer Programming
  • Convex Programming
  • Dynamic Programming
  • Evolutionary Algorithms
  • Genetic Algorithms
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Mathematics
  • Nonlinear Programming
  • Operations Research
  • Optimization
  • Petroleum Industry
  • Simplex Method
  • Standards

Fields of Study

  • Mathematics

Readers

  • Operations Research