A question about QBP

[Ahmadreza Talebian]

Hello everybody,

I have a Quadratic Binary Programming in the following form:

Min c*X+0.5*X'*H*X

S.t.

      A1*X <= b1

      A2*X =   b2

      X=0 or 1

The problem has 5000 variables. Using cplexmiqp() in MATLAB, my computer, which has 12GB of RAM, faced to memory overflow.

First of all, I don't know whether YALMIp could solve my problem or not. I was wondering if any of you guys could assist me because I'm in rush and my adviser is mad at me!

Secondly, I would like to know your prediction about YALMIP. Do you thinks that i would surpass CPLEX?

Thank you,

Ahmadreza 

[Ahmadreza Talebian]

PS: H is "Indefinite"

[Johan Löfberg]

You would not use YALMIP (i.e., bnb + some local QP solver) to solve the problem. YALMIP is not a solver, you use YALMIP to setup the problem and send it to a solver (such as CPLEX which you have installed apparently). No need here really to use YALMIP though since you already have all the data packaged in a simple format ready for a solver.

Note, x'*H*x is equal to x'*(H+lambda*I)*x-sum(x)*lambda, i.e., you can always shift the eigenvalues of H to make it positive semidefinite for purely binary problems. I think cplex does this for you automatically.

If cplex fails to solve the problem, you're pretty much out of options. You could of course try some other quality solver such as gurobi,mosek or xpress, but most likely, you will not see any major difference. Since memory seems to be an issue, use the various options in cplex to tune the solution strategy (such as emphasis.memory). Most likely though, a better model is needed, or you develop your own solver specific solver (with heuristics etc)

I don't understand why your advisor would be mad at you for cplex not being able to solve the problem. The problem is absolutely huge if you are unlucky. Do the following worst-case analysis: Assume cplex can process 1e6 nodes per second (very optimistic), and it runs 3600 seconds per hour, 24 hours per day, 365 days per year. In the worst case (very pessimistic, but that's reality of combinatorial problems) cplex has to process 2^5000 nodes. How many years will this take? The number of seconds passed since birth of universe is 3600*24*365*14e9=4.4e17. Hence, the number of universe lifelengths you could be forced to wait if unlucky is 10^(log10(2)*5000)/(1e6*4.4e17). Don't try to compute that number in MATLAB. It returns inf. If you do it by hand, you end up at 10^(log10(2)*5000-17-6)/4.4, i.e ~10^1488 times the lifetime of the universe.