Verzweigungsstrategien in branch and bound-algorithmen für gemischt-ganzzahlige lineare 0-1-optimierungsanfgaben

Abstract

The paper deals with branching strategies in a branch and bound algorithm for a class of mixed boolean programs. In any vertex of the solution tree the linear relaxation of the MIP with some boolean variables fixed to 0 or 1 is solved. In this manner the present investigations complete earlier results of the author for variables a priori fixing.

AMS 1980 Subject Classifications:

• Primary: 90 C 11
• Secondary: 90 C 05
• Secondary: 90 C 09

Keywords:

• Mixed integer 0-1-programming
• linear relaxation, pseudo solutions
• branch and bound
• surrogate constraint