On the value of binary expansions for general mixed-integer linear programs

Jonathan H. Owen; Sanjay Mehrotra

doi:10.1287/opre.50.5.810.370

On the value of binary expansions for general mixed-integer linear programs

Jonathan H. Owen^*, Sanjay Mehrotra

^*Corresponding author for this work

Industrial Engineering and Management Sciences

Research output: Contribution to journal › Article › peer-review

26 Scopus citations

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.

Original language	English (US)
Pages (from-to)	810-819
Number of pages	10
Journal	Operations Research
Volume	50
Issue number	5
DOIs	https://doi.org/10.1287/opre.50.5.810.370
State	Published - 2002

Keywords

Integer: remodeling of general integer variables
Programming

ASJC Scopus subject areas

Computer Science Applications
Management Science and Operations Research

Access to Document

10.1287/opre.50.5.810.370

Cite this

@article{7c766af13a35428db90d1ede984efa63,

title = "On the value of binary expansions for general mixed-integer linear programs",

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 = "Integer: remodeling of general integer variables, Programming",

author = "Owen, {Jonathan H.} and Sanjay Mehrotra",

year = "2002",

doi = "10.1287/opre.50.5.810.370",

language = "English (US)",

volume = "50",

pages = "810--819",

journal = "Operations Research",

issn = "0030-364X",

publisher = "INFORMS Institute for Operations Research and the Management Sciences",

number = "5",

}

TY - JOUR

T1 - On the value of binary expansions for general mixed-integer linear programs

AU - Owen, Jonathan H.

AU - Mehrotra, Sanjay

PY - 2002

Y1 - 2002

N2 - 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.

AB - 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.

KW - Integer: remodeling of general integer variables

KW - Programming

UR - http://www.scopus.com/inward/record.url?scp=0036759238&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0036759238&partnerID=8YFLogxK

U2 - 10.1287/opre.50.5.810.370

DO - 10.1287/opre.50.5.810.370

M3 - Article

AN - SCOPUS:0036759238

SN - 0030-364X

VL - 50

SP - 810

EP - 819

JO - Operations Research

JF - Operations Research

IS - 5

ER -

On the value of binary expansions for general mixed-integer linear programs

Abstract

Keywords

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this