next up previous contents index
Next: Adding Constraints Up: The Subproblem Previous: Branch-and-Bound

The Optimization of the Subproblem

The core of the class ABA_SUB is its optimization by a cutting plane algorithm. As dynamically generated variables are dual cuts we also use the notion cutting plane algorithm for a column generation algorithm. By default, the cutting plane algorithm only solves the LP-relaxation and tries to fix and set variables by reduced costs. Within the cutting plane algorithm four virtual dummy functions for the separation of constraints, for the pricing of variables, for the application of primal heuristics, and for fixing variables by logical implications are called. In a problem specific class derived from the class ABA_SUB these virtual functions can be redefined. Motivated by duality theory (see [Thi95]), we handle constraint and variable generation equivalently. If both constraints and variables are generated, then by default constraints are generated. In addition to the mandatory pricing phase before the fathoming of a subproblem, we price out the inactive variables every k iterations. The value of k can be controlled by a parameter. By the redefinition of a virtual function other strategies for the separation/pricing decision can be implemented.



Stefan Thienel
Fri Sep 19 11:32:54 MET DST 1997