Nonbasic Branching and Dual Relaxation in a Branch-and-Bound Mixed Integer Programming Algorithm.
Abstract
This paper presents branch-and-bound linear mixed integer algorithms which employ nonbasic branching and/or a form of dual relaxation in order to attain the objective function change prescribed by a bound more rapidly than in the standard algorithm. The subproblems arising from the algorithms may at times be solved with no computation or their solution may result in simplex tableaus which are both primal and dual infeasible. Procedures to allow for recovery from dual infeasibility and branching criteria which guarantee optimality will be described. Sample problems will be solved and comparisons made between the specified algorithms.
Document Details
- Document Type
- Technical Report
- Publication Date
- Feb 01, 1975
- Accession Number
- ADA008361
Entities
People
- Ronald D. Armstrong
Organizations
- University of Texas at Austin