On the Value of Binary Expansions For General Mixed-Integer Linear Programs

Jonathan Owen (jonathan.owengm.com)
Sanjay Mehrotra (mehrotraiems.nwu.edu)

Abstract: We study the use of binary variables in reformulating general mixed-integer linear programs. We show that binary reformulations result in problems for which almost all the binary variables replacing a general integer variable need to be explored during branching. We also give computational results on the performance of such reformulations in solving the mixed-integer programs, which support our theoretical results.

Keywords: Mixed Integer Programming Disjunctive Reformulation-linearization

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

Category 2: Optimization Software and Modeling Systems (Other )

Citation: to appear in Operations Research

Download:

Entry Submitted: 10/20/2000
Entry Accepted: 10/20/2000
Entry Last Modified: 05/23/2001

Modify/Update this entry