Monday, April 6, 2009

Binary QP

I have been trying to solve an Binary Integer Program using AMPL/CPLEX
with the following objective function

minimize Total_Cost:
        sum{i in flights,k in gates} In[i,k] * Pnty * (Y[i,k]-X[i,k])^2 + sum
{i in flights, k in gates} ct*FTG[i,k]*(Y[i,k]-X[i,k])

where X[i,k] is the only decision variable.

I tried to solve it, but it gave me the following error:

CPLEX 11.2.0: 5 diagonal QP coefficients of the wrong
Variable Diagonal
_svar[8] -5
_svar[4] -2.5
_svar[3] -24.5
Diagonal QP Hessian has elements of the wrong sign.

When I tried to solve the problem using Minos (trial version) solver
for miniature problem, it solves it but the integrality of some
variables are ignored.

I am trying to linearize the above objective function and trying to
solve it through the CPLEX, but I am not successful yet. Can you
suggest for any solution or approach to solve it.

Assuming Y is a parameter and X is a binary variable (and all other identifiers are parameters), you can replace

(Y[i,k]-X[i,k])^2 = Y[i,k]-2*Y[i,k]*X[i,k]+X[i,k]^2 = Y[i,k]-2*Y[i,k]*X[i,k]+X[i,k]

which is linear in X. Note that x2=x when x is a binary variable.