infeasibility

[Maryam Bodaghi]

Dear Mr. Johan;

when a problem is infeasible, could it be caused by selecting wrong solver? My problem is quadratic, and I don't have CPLEX to solve it.

(I solved the same problem whitout "variable x" in CVX , but in YALMIP it is infeasible.)

[Johan Löfberg]

Well, this minor addition of x is massive, as the problem now is a nonconvex program far from anything solvable using cvx.

The following shows that there is a trivial error in your model

>> solvesdp(Constraint)
Exiting due to infeasibility:  1 lower bound exceeds the corresponding upper bound.

ans =

    yalmiptime: 1.6700
    solvertime: 0.0310
          info: 'Infeasible problem (FMINCON)'
       problem: 1

Some analysis shows that it is the 45th variable which has these weird bounds , which corresponds to the last element in y_1

[Johan Löfberg]

And cplex would not be able to solve this as you have nonconvex quadratic inequalities

[Johan Löfberg]

You can start debugging already in C1+C2

>> solvesdp([C1 C2])
Infeasibility row 'c68':  0  = 9.
Presolve time = 0.00 sec. (0.01 ticks)

ans =

    yalmiptime: 0.4990
    solvertime: 0.0160
          info: 'Infeasible problem (CPLEX-IBM)'
       problem: 1

[Johan Löfberg]

If you put a break and check when i=2, after the creation of C1 and C2, you have that these two vectors should be zero

 sdisplay(sdpvar(C1))

ans =

    '3*y_1(3)'
    '3*y_1(6)'
    '3*y_1(9)'
    '3*y_1(12)'
    '3*y_1(15)'
    '3*y_1(18)'
    '3*y_1(21)'
    '3*y_1(24)'
    '3*y_1(27)'
    '3*y_1(30)'
    '3*y_1(33)'
    '3*y_1(36)'
    '3*y_1(39)'
    '3*y_1(42)'
    '0.2-0.2000*y_1(1)+1.5000*y_1(3)'
    '0.2-0.2000*y_1(4)+1.5000*y_1(6)'
    '0.2-0.2000*y_1(7)+1.5000*y_1(9)'
    '0.2-0.2000*y_1(10)+1.5000*y_1(12)'
    '0.2-0.2000*y_1(13)+1.5000*y_1(15)'
    '0.2-0.2000*y_1(16)+1.5000*y_1(18)'
    '0.2-0.2000*y_1(19)+1.5000*y_1(21)'
    '0.2-0.2000*y_1(22)+1.5000*y_1(24)'
    '0.2-0.2000*y_1(25)+1.5000*y_1(27)'
    '0.2-0.2000*y_1(28)+1.5000*y_1(30)'
    '0.2-0.2000*y_1(31)+1.5000*y_1(33)'
    '0.2-0.2000*y_1(34)+1.5000*y_1(36)'
    '0.2-0.2000*y_1(37)+1.5000*y_1(39)'
    '0.2-0.2000*y_1(40)+1.5000*y_1(42)'
    '0.2-0.2000*y_1(43)+1.5000*y_1(45)'

K>> sdisplay(sdpvar(C2))

ans =

    '19.8000*y_1(3)'
    '21.6000*y_1(6)'
    '23.4000*y_1(9)'
    '25.2000*y_1(12)'
    '27*y_1(15)'
    '28.8000*y_1(18)'
    '30.6000*y_1(21)'
    '32.4000*y_1(24)'
    '34.2000*y_1(27)'
    '36*y_1(30)'
    '37.8000*y_1(33)'
    '39.6000*y_1(36)'
    '41.4000*y_1(39)'
    '43.2000*y_1(42)'
    '9*y_1(1)'
    '10*y_1(4)'
    '11*y_1(7)'
    '12*y_1(10)'
    '13*y_1(13)'
    '14*y_1(16)'
    '15*y_1(19)'
    '16*y_1(22)'
    '17*y_1(25)'
    '18*y_1(28)'
    '19*y_1(31)'
    '20*y_1(34)'
    '21*y_1(37)'
    '22*y_1(40)'
    '23*y_1(43)'

From C2, it follows, that y_1(4) must be 0, and in C_1 that y_1(6) must be zero. This is inconsistent with '0.2-0.2000*y_1(4)+1.5000*y_1(6)'
being zero as required in C1

[Maryam Bodaghi]

Dear Mr. Lofberg

I wan to tank you for your really helpful and so sharp advises. I've ask many questions up to now, ad you answered them in a best way.

Tanks so much.

Maryam

[Maryam Bodaghi]

Dear Mr. Lofberg;

I've fixed the problem, but why I get NAN by using " BMIBNB" solver?( I want to solve with this because BMIBNB solver is for nonlinear and non convex problem and gives global optimization)

I'm trying to solve it whith BONMIN, but it takes so mane times.

[Johan Löfberg]

Rule 1 when doing things: test small things. Don't start by trying to use the solver on 24 hours. Try 3 hours first or something really small like that. Then try larger models until it doesn't work, and draw conclusions from that (if it even worked for N=3..)

I doubt you've seen any kind of termination with bmibnb on this model

[Johan Löfberg]

Hmm, it actually terminated in only 3 iterations. Took 2 hours though!

    3 :    9.604E+02     5.17      9.119E+02   4    
* Finished.  Cost: 960.3736 Gap: 5.1701
* Timing: 97% spent in upper solver
*         1% spent in lower solver
*         3% spent in LP-based domain reduction

ans =

    yalmiptime: 2.3370
    solvertime: 6.5896e+03
          info: 'Successfully solved (BMIBNB)'

What is NaN for you?

[Johan Löfberg]

Hi,

When setting up models like these in theory, you must attack the model much harder when going to practice from some notes on a paper. Being forced to go from LP to MILP is a huge step, but it can often remain tractable, albeit hard to solve. Adding nonlinearities, and you typically make it much harder as the field of MINLP is much less mature and thus make the problem more likely to be unsolvable and thus uninteresting, and adding nonconvexities on top of that, and you almost always have nothing left for practical purposes.

However, in your case, I strongly suspect some massage will simplify this whole thing to a MILP. You are doing a lot of unnecessary complications and bad modelling.

For instance, you are defining quadratics (a-bx)^2, and then you add the constraint that this expression should be non-negative. That is a completely redundant constraint, but it adds non-convexity to the model making life hard for the solvers. Going further, even the convex constraint (a-bx)^2 <= c is unnecessarily complicated and moving you away from a MILP-representable model. Sure, it is convex quadratic, but the feasible set it describes is simply a linear set.

Similarly, you define expressions max(0,something) and then you add the constraint that this object is non-negative. Once again a completely redundant constraint, but what's more harmful, the max operator is convex, hence the redundant constraint is non-convex and YALMIP has to abandon simple epigraph modelling and model the max operator in a complicated fashion using auxilliary binary variables etc.

Finally, you are multiplying binary variables and continuous expressions without any careful inspection if they can be represented as linear expressions instead (many of them can here). Almost always, this is much better, and it moves you to closer to a MILP representable model.

Contact me per email if you want to discuss the model further.