BONMIN QP binvar/integer problem

[Piotr Balik]

Dear Professor Löfberg,

I have tried a bigger variant of:

x=binvar(2,2);
C = [1 2; 3 4];

k=x.*C;
k=k(:);
F=[sum(x,1)==1, sum(x,2)==1]; %unique values

Where:

optimize(F,  sum(k)) %works well

optimize(F,  k'*k) %error, "Error solving relaxed problem with IPOPT" in 'debug'

After I changed the domain and cost

x=sdpvar(2,2);
k=ceil(x).*C;

F = [... , x(:)>=0]

optimize(F,  sum(k)) %works well, but calls scip-NL

optimize(F,  k'*k) %error "The LP relaxation is infeasible or too expensive"

Is there any way to combine binary problem with quadratic cost and not call nonlinear solver?

I blindly added another variable z=sdpv(1) with optimize( [F, z <= k'*k], z ) but the parsed model is the same.

QP solvers I have installed refuse to work with integer variables and integer-digesting ones refuse QP.

Best regards!

[Johan Löfberg]

quadratic is nonlinear, so a nonlinear solver must be used. Perhaps you mean general nonlinear in contrast to a quadratic solver?

You don't have a MIQP solver installed, so to solve the problem with a MIQP solver (mosek/gurobi/cplex/xpress), you would have to install that (or use 'bnb' assuming you have a QP solver at least, but much better to install a real solver)

[Johan Löfberg]

...and I've seen many strange crashes with bonmin via opti, so I would not try to get that working. I have no idea what is happening here

tisdag 13 april 2021 kl. 15:47:10 UTC+2 skrev Piotr Balik:

[Johan Löfberg]

and in this case I suspect it is because you have 3 variables and 4 equalities, and ipopt/bonmin does not like overdetermined problems

tisdag 13 april 2021 kl. 15:47:10 UTC+2 skrev Piotr Balik:

[Piotr Balik]

Thanks for insights!

I forgot to state that they must be 'full' so it's always N^2 vars and N^2 equalities - in that case the Ipopt returns status 5 during initialSolve.

But it appears I either need MIQP or just assign C=C^2 since it's merely (here) binary decision problem.

[Johan Löfberg]

with x full bonmin solves the problem when I test it.

x=binvar(2,2,'full');

C = [1 2; 3 4];

k=x.*C;

k=k(:);

F=[sum(x,1)==1, sum(x,2)==1]; %unique values

optimize(F,  k'*k) 

    yalmipversion: '20210331'

    matlabversion: '9.9.0.1524771 (R2020b) Update 2'

       yalmiptime: 0.2380

       solvertime: 0.1980

             info: 'Successfully solved (BONMIN)'

          problem: 0

Don't understand what you are talking about when talking about needing MIQP or assigning C (unless you mean that it is silly to solve as a MIQP and you only have x.^2 terms and thus just as well can solve the linearized model)

But again, I would not use bonmin to solve MIQPs

[Piotr Balik]

Strangely :o the same exact code gives me:
 yalmipversion: '20210331'
    matlabversion: '9.2.0.538062 (R2017a)'
       yalmiptime: 0.3572
       solvertime: 1.0538
             info: 'Infeasible problem (BONMIN)'
          problem: 1

What I meant about MIQP is that cost function is quadratic with discrete decision domain. About the assign: (c*x)^2 = c^2 *x when x is {0,1} so I can just use sum( x.*(C.^2) ) as a cost

[Piotr Balik]

Sorry - I need a MIQP solver obviously!

[Johan Löfberg]

different opti/bonmin/ipopt versions I guess