Search code examples
optimizationcplexampl

AMPL Cplex error: QP Hessian is not positive semi-definite


I'm currently trying to solve an AMPL model, that runs for me using minos, with cplex and integral variables.

Most of the problems I've solved (i think). Helped myself with a "ratio trick" from here: http://lpsolve.sourceforge.net/5.5/ratio.htm, yet right now I get "QP Hessian is not positive semi-definite." error from one of my constraints.

I kinda know what the error means, yet I am not sure why it is showing for this constraint :/

#S
set SOURCE;
#D
set HALFPROD;
#K
set HALFPRODU;
#P
set PROD;

param surmax {SOURCE} >= 0;
param prodmin {PROD} >= 0;
param prodprofit {PROD} >= 0;
param convSDmax >= 0;
param convDKmax >= 0;
param convSD {SOURCE, HALFPROD} >= 0;
param convDK {HALFPROD, HALFPRODU} >= 0;
param convDP {HALFPROD, PROD} >= 0;
param convKP {HALFPRODU, PROD} >= 0;

var xs {SOURCE} >= 0, integer;
var xu {HALFPROD} >= 0, integer;
var xpd {PROD, HALFPROD} >= 0, integer;
var xpk {PROD, HALFPRODU} >= 0, integer;
var isKUsed binary;

var quantityD {j in HALFPROD} = sum {i in SOURCE} convSD[i,j] * xs[i];
var costSur = sum {i in SOURCE} xs[i]*12;

var quantityK {k in HALFPRODU} = (sum {j in HALFPROD} xu[j] * convDK[j,k]) * isKUsed;
var costK = isKUsed * 13000;

var quantityProdD {l in PROD} = sum {j in HALFPROD} xpd[l,j] * convDP[j,l];
var quantityProdK {l in PROD} = sum {k in HALFPRODU} xpk[l,k] * convKP[k,l];
var quantityProd {l in PROD} = quantityProdD[l] + quantityProdK[l];

var profitProd = sum {l in PROD} prodprofit[l] * quantityProd[l];
var balance = profitProd - costSur - costUwod;

subject to OgrSurMax {i in SOURCE}: xs[i] <= surmax[i];
subject to OgrconvSDMax: (sum {i in SOURCE} xs[i]) <= convSDmax;
subject to OgrconvDKMax: (sum {j in HALFPROD} xu[j]) <= convDKmax;
subject to OgrProdMin {l in PROD}: quantityProd[l] >= prodmin[l];
subject to OgrHALFPRODXPD {j in HALFPROD}: (sum {l in PROD} xpd[l,j]) + xu[j] - quantityD[j] <= 0;
#------------------TRAITOR!
subject to OgrHALFPRODXPK {k in HALFPRODU}: (sum {l in PROD} xpk[l,k]) - quantityK[k] <= 0;
#--------------------------

maximize balanceMax: balance;

This is my model.

"conv" stands for conversion:

  • S->D and D->K are ratios "how much of D I get from converting S?"
  • D->P and K->P are binary matrices that says whether D or K can be converted to P

Main actors in this model are xpd and xpk - they say how much PROD was aquired from converting HALFPROD or HALFPRODU. Because of multiple conversions I got to keep track of D's amount - number of D's used for D->K and D->P has to be less or equal than D's from S->D. This works, yet for some reason the same (even easier) constraint is not working :/

Any clues as to what may be an issue or how to fix it?


UPDATE:

Based on Erwin Kalvelagens answer I've tried to linearize it. Couldn't find a simple way for linearizing it apart from bigM method. I've changed my quantityD part to this:

param quantityKMAX = 490860;
var quantityK {k in HALFPRODU} >= 0;
s.t. ogrK1 {k in HALFPRODU}: quantityK[k] <= quantityKMAX * isKUsed;
s.t. ogrK2 {k in HALFPRODU}: quantityK[k] <= (sum {j in HALFPROD} xu[j] * convDK[j,k]);
s.t. ogrK3 {k in HALFPRODU}: quantityK[k] <= (sum {j in HALFPROD} xu[j] * convDK[j,k]) - quantityKMAX * (1 - isKUsed);

quantityKMAX is a maximum quantity acquired from conversion (when converting max possible number of D to the "most giving" K), but I've actually tried with arbitrally big number, that is for sure bigger than any possible value for quantityK.

Works!


Solution

  • Cplex can only handle certain classes of quadratic constraints (in general -- with some exceptions -- things must stay convex). In your definition of variable quantityK you introduce a quadratic expression that Cplex cannot handle.

    One simple approach is just to solve the problem twice: once with isKUsed=0 and once with with isKUsed=1. Then just pick the best solution.

    Otherwise you can linearize things. Multiplication of a binary variable times a continuous (or integer) non-negative variable is not very hard to linearize.