Using Bit Representation to Improve LP Relaxations of Mixed-Integer Quadratic Programs
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.
Entry Submitted: 05/18/2017
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|