Back to SYMPHONY Home Page

The Linear Programming Module

The linear programming (LP) module is the most complex and computationally intensive of the five processes. Its job is to perform the bounding and branching operations. These operations are, of course, central to the performance of the algorithm. Functions performed by the LP module are:

• Inform the tree manager when a new subproblem is needed.
• Receive a subproblem and process it in conjunction with the cut generator and the cut pool.
• Decide which cuts should be sent to the global pool to be made available to other LP modules.
• If necessary, choose a branching object and send its description back to the tree manager.
• Perform the fathoming operation, including generating variables.