linearization using yalmip

[Yanyan]

Hello Johan,

I have a very basic question about the linearization in yalmip. Now I have a binvar vector x, a sdpvar z1 and sdpvar z2, I want to use the non-linear constraint  2*x(1)*x(2)>=1， 3*x(1)*x(2)+2*x(1)*x(2)>=0.8 to be replaced by the linear constrait:2*z1>1,0<=z1<=1,z1<=x(1),z1<=x(2),z1>=x(1)+x(2)-1，   3*z2+2*z1>1.1,0<=z2<=1,z2<=x(2),z2<=x(3),z2>=x(2)+x(3)-1], so the code is like this:

x=binvar(1,3);%al=sdpvar(1);all=sdpvar(1);

obj=x(1)+x(2)+x(3);z1=sdpvar(1);z2=sdpvar(1);

options=sdpsettings('solver','bnb','verbose',0,'debug',1);

opt=solvesdp([2*z1>1,0<=z1<=1,z1<=x(1),z1<=x(2),z1>=x(1)+x(2)-1,...

    3*z2+2*z1>1.1,0<=z2<=1,z2<=x(2),z2<=x(3),z2>=x(2)+x(3)-1],obj,options)

double(x)

But it cannot found the solution and shows infeasible problem.

If I change z1=sdpvar(1);z2=sdpvar(1);to z1=binvar(1);z2=binvar(1); and the result shows errors like: 

Error using sprintf

Function is not defined for sparse inputs.

Error in lipsol (line 448)

      theMessage = sprintf(['Exiting due to infeasibility: %i

      singleton variables in the equality\n' ...

Error in linprog (line 249)

    [x,fval,lambda,exitflag,output] =

    lipsol(f,A,B,Aeq,Beq,lb,ub,options,defaultopt,computeLambda);

Error in calllinprog (line 59)

[x,fmin,flag,output,lambda] = linprog(c, A, b, Aeq, beq, lb, ub,

x0,options.linprog);

Error in bnb_solvelower (line 128)

            output = feval(lowersolver,p);

Error in bnb_solvelower (line 120)

        output = bnb_solvelower(lowersolver,dummy,upper,lower);

        Error in bnb>branch_and_bound (line 605)

        output =

        bnb_solvelower(lowersolver,relaxed_p,upper+abs(upper)*1e-2+1e-4,lower);

        Error in bnb (line 279)

[x_min,solved_nodes,lower,upper,profile,diagnostics] =

branch_and_bound(p,pss);

Error in solvesdp (line 337)

    eval(['output = ' solver.call '(interfacedata);']);

Error in Noc (line 79)

opt=solvesdp([2*z1>1,z1<=x(1),z1<=x(2),z1>=x(1)+x(2)-1,…

So what is the reason? Because apparently, there is feasible solutions and when I don't use the linearization, I can definitely get the correct solution. But now with the new variable z1 and z2, which is actually constrained to be 0 or 1, the bob doesn't work. Is there anything wrong with my approach?

Many thanks,

Yanyan

[Johan Löfberg]

1. You have strict inequalities in your model. Is that intentional? Strict inequalities are not supported

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Blog.Prepare-your-code

2. Install a real MILP solver. bnb is only intended for problems for which there are no publically available mixed-integer solvers (such as mixed-integer SDPs)

3. Install a real LP solver. The reason bnb fails is because your LP solver fails to solve the relaxation. It looks as if you are using linprog, which is among the worst LP solvers.

4. The crash is in linprog/lipsol, and to me it looks like a bug which would happen if you use an old version of linprog in a newer version of MATLAB (since sprintf changed behavior some years ago)

To summarize: Install a MILP solver (gurobi/cplex/mosek/xpress/scip/glpkmex/lpsolve/...) to solve the MILP

[Yanyan]

Hi Johan,

I have installed lp_solve, but I don't think this solver helps. In fact, the strict inequalities are intended set in order to constrained z1 to be 0 or 1 without using nonlinear x(1)*x(2). As you can see, with such constraints: 0<=z1<=1,z1<=x(1),z1<=x(2),z1>=x(1)+x(2)-1, actually z1 equals to x(1)*x(2), which is the transformation from nonlinear to linear. 

But now with lp_solver, for a specific constraint as :0<=z1<=1, e can only be -1,0 or 1 to denote less than, equal and greater than. But for this constraint, how could I set the constraint? Please give the example code for just this problem. Unknown variables: x(1), x(2), x(3), z1 and z2. The objective function is x(1)+x(2)+x(3), with such constraints: 2*z1>1, 0<=z1<=1,z1<=x(1),z1<=x(2),z1>=x(1)+x(2)-1, 3*z2+2*z1>1.1,0<=z2<=1,z2<=x(2),z2<=x(3),z2>=x(2)+x(3)-1. We want to find the minimal value of objective function. 

Many thanks,

Yanyan

[Johan Löfberg]

I don't understand what you are asking about. Does lpsolve not work? BTW, I would recommend a better solver if you have the possibility. If you are in academia, you can get free versions of cplex, gurobi and mosek. Far better solvers than lpsolve.

The second issue: The modelling of nonlinear products does not require strict inequalities. Which model is it you need help with?

This: 2*x(1)*x(2)>=1， 3*x(1)*x(2)+2*x(1)*x(2)>=0.8

is directly modeled by letting x12 denote the product

sdpvar x12
Model=[2*x12>=1,
3*x12+2*x12>=0.8,
x12<=x(1),x12<=x(2),x12>=x(1)+x(2)-1]

Of course, the model is silly since it is trivially only satisfied by x(1)=x(2)=1 

[Yanyan]

Hi Johan,

It is like this, I want to avoid using the nonlinear part 2*x(1)*x(2)>=1, 3*x(1)*x(2)+2*x(1)*x(2)>=0.8 by introducing another two variables z1 and z2. And z1 has the constraint of 2*z1>1, 0<=z1<=1,z1<=x(1),z1<=x(2),z1>=x(1)+x(2)-1. You can see the strict inequality is necessary to limit z1 to be 0 or 1. That is the basic idea of the non-linearization. Now I don't need the more powerful cplex, because now it is a very basic problem.

Do you get what I mean?

[Johan Löfberg]

No, I don't understand why you keep talking about strict inequalities, and why you are using two z variables to model 1 nonlinearity.

This

 2*x(1)*x(2)>=1, 3*x(1)*x(2)+2*x(1)*x(2)>=0.8

is equivalent to, and linearized with

sdpvar z
Model=[2*z>=1,
3*z+2*z>=0.8,
z<=x(1),z<=x(2),z>=x(1)+x(2)-1]

Which of course is a trivial problem since the only solution is z = 1, i.e., x(1)=x(2)=1

[Johan Löfberg]

Perhaps you mean

 2*x(1)*x(2)>=1, 3*x(1)*x(2)+2*x(2)*x(3)>=0.8

Still, no strict inequalities needed,

sdpvar z1 z2
Model=[2*z1>=1,,
3*z1+2*z2>=0.8,
z1<=x(1),z1<=x(2),z1>=x(1)+x(2)-1,
z2<=x(2),z2<=x(3),z2>=x(2)+x(3)-1]

[Yanyan]

Yes, now I don't use the strict inequality. But for a really small variables, it seems the non-linearization doesn't give the solution. So do you think this non-linearization approach really helps to reduce the computation complexity? Because my problem is the non-linear optimization with lots of variables. Since now we cannot get a solution due to the high complexity caused by so many variables and their non-linear operations, we want to use linear way to formulate instead. That is why we have to introduce a new variable z1 to represent x(1)*x(2) with the constraint of z1<=x(1),z1<=x(2),z1>=x(1)+x(2)-1. But now after linearization, we get much more constraints, and even worse, we cannot get a solution either. So do you have any idea? Or what could I do to solve the non-linear problem with larger variables to be optimized?

Thanks,

Yan

[Johan Löfberg]

What do you mean with "for a really small variables, it seems the non-linearization doesn't give the solution"? Example?

Yes, you get a much larger model when you linearize bilinear model using this approach. However, it is typically a much easier problem than the original nonlinear problem. If you cannot solve the linearized problem, you cannot, almost surely, solve the original problem to global optimality. 

However, you are using lpsolve. The fact that you cannot solve the problem using lpsolve does not say much (as an example, the sudoku example http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Examples.Sudoku is solved in 0 seconds using a good solver such as cplex, gurobi, mosek, scip, while lpsolve fails to solve the problem at all, or at least it used to do that a couple of years ago, haven't tried the latest versions)