Optimization Online


Branch-and-Price Guided Search for Integer Programs with an Application to the Multicommodity Fixed Charge Network Flow Problem

M Hewitt(mrheie***at***rit.edu)
G Nemhauser(gnemhaus***at***isye.gatech.edu)
M Savelsbergh(martin.savelsbergh***at***newcastle.edu.au)

Abstract: We develop an exact algorithm for integer programs that uses restrictions of the problem to produce high-quality solutions quickly. Column generation is used both for generating these problem restrictions and for producing bounds on the value of the optimal solution. The performance of the algorithm is greatly enhanced by using structure, such as arises in network flow type applications, to help define the restrictions that are solved. In addition, local search around the current best solution is incorporated to enhance overall performance. The approach is parallelized and computational experiments on a classical problem in network design demonstrate its efficacy.

Keywords: integer programmng; column generation; local search; multicommodity fixed-charge network flow

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Network Optimization

Citation: INFORMS Journal on Computing (Accepted 1/16/2012)

Download: [PDF]

Entry Submitted: 02/15/2012
Entry Accepted: 02/15/2012
Entry Last Modified: 02/15/2012

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society