A Constraint Branch-and-Bound Method for Set Partitioning Problems

Abstract

This thesis compares the efficiency of a constraint branch-and-bound method against the conventional variable branch-and-bound method in solving set partitioning problems. Because of the difficulties encountered in writing the constraint branch-and-bound subroutine, it was necessary to solve each subproblem encountered from scratch. This is in contrast to the variable branching code which, when solving closely related subproblems, essentially starts from an advanced starting solution. Even using an inefficient implementation, the constraint branch-and-bound method appears to be significantly more efficient than the conventional variable branch-and-bound method. It saves, on average, 30.0% in CPU time over the variable branch-and- bound-method when tested on a set of small test problems. On average, constraint branch and bound produces 59.3% fewer nodes in its enumeration trees than does variable branch and bound, and the trees encountered are shallower and better balanced.

Open PDF

Document Details

Document Type
Technical Report
Publication Date
Mar 01, 1990
Accession Number
ADA227092

Entities

People

  • Moo B. Ryoo

Organizations

  • Naval Postgraduate School

Tags

Communities of Interest

  • Air Platforms

DTIC Thesaurus Topics

  • Abstracts
  • Algorithms
  • Classification
  • Computer Programming
  • Contrast
  • Coverings
  • Efficiency
  • Evolutionary Algorithms
  • Integer Programming
  • Linear Programming
  • Mathematical Programming
  • Notation
  • Operating Systems
  • Operations Research
  • Optimization
  • Procedures (Computers)
  • Quadratic Programming

Readers

  • Operations Research