Compact linearization for bilinear mixed-integer problems

Leo Liberti (leolibertiyahoo.com)

Abstract: We present a compact linearization for a broad class of bilinear 0-1 mixed-integer problems subject to assignment constraints. We apply the linearization to three classes of problems: quadratic assignment, multiprocessor scheduling with communication delays, and graph partitioning, and show that it yields faster solution times.

Keywords: linearization, bilinear, binary

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

Category 2: Nonlinear Optimization (Quadratic Programming )

Category 3: Applications -- OR and Management Sciences (Scheduling )

Citation: DEI, Politecnico di Milano, Working paper, April 2005.

Download: [Postscript]

Entry Submitted: 05/05/2005
Entry Accepted: 05/06/2005
Entry Last Modified: 05/05/2005

Modify/Update this entry