Optimization Online


Using Bit Representation to Improve LP Relaxations of Mixed-Integer Quadratic Programs

Laura Galli(laura.galli***at***unipi.it)
Adam N. Letchford(a.n.letchford***at***lancaster.ac.uk)
Daniel J. Grainger(daniel.grainger***at***thomson.co.uk)

Abstract: A standard trick in integer programming is to replace each bounded integer-constrained variable with a small number of binary variables, using the bit representation of the given variable. We show that, in the case of mixed-integer quadratic programs (MIQPs), this process can enable one to obtain stronger linear programming relaxations. Moreover, we give a simple sufficient condition under which one can use bit representation to convert a (not necessarily convex) MIQP into a mixed 0-1 linear program of polynomial size.

Keywords: mixed-integer nonlinear programming; cutting planes; global optimisation

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

Category 2: Integer Programming (Cutting Plane Approaches )

Category 3: Global Optimization

Citation: Working paper, Department of Management Science, Lancaster University, United Kingdom, May 2017.

Download: [PDF]

Entry Submitted: 05/18/2017
Entry Accepted: 05/18/2017
Entry Last Modified: 05/18/2017

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