Is there any constaint for the objective function? The highest order or sth. else?

[Yanyan]

Hi Johan,

I see your reply to other guys, and I want to ask a question about the objective function as in the title. Actually, my problem is like this: I use X=binvar(n,n) as the variable and I want to minimize the objective function. But when n=3 or 4, it works fine and I can get the correct X. But when n=5, the resulting X is always full of NaN. In the objective function, there are many operations such as X(i,j)*X(m,n) and further may be multiplies by (1-X(p,q)), I mean it is a complex calculation process. So is there any constraint on the objective function in terms of variable order? Why does n=4 work but not for n>=5?

If you need my code, please let me know.

Really appreciate your help!

Sincerely,

Yanyan

[Adkitta]

There is no restriction on the order of the objective function. Looks like a numerical issue with the solver that you call from YALMIP. A small working example of your code will help to fix the issue.

[Johan Löfberg]

Do you mean all elements in X are NaNs, or that there are many of them which are NaN?

In case all are NaN, solver has crashed or something like that, or YALMIP has detected that the problem cannot be solved using the solvers you have. You should report the error codes given by solvesdp

x =sdpvar(1);
solvesdp(x>=0,x^2,sdpsettings('solver','linprog'))

ans = 

    solvertime: 0

          info: 'Solver not applicable (linprog)'

       problem: -4

    yalmiptime: 0.4910

So please report everything displayed when you run solvesdp (solver display, and result structure)

In case some of them are Nan, it indicates that you are not using all variables in your model, hence they are never optimized by the solver and thus have no value. For example

x=sdpvar(3,1);
solvesdp(x(1:2)>=0,x(1));

>> double(x)

ans =

     0

     0

   NaN

[Yanyan]

Hi Johan,

There is 6 hours' time difference between US and Sweden, but I am still expecting your reply!

Besides the NaN in X (full of NaN), I I found that the program gets stuck at here:
Operation terminated by user during ==> findhash at 6

In ==> sdpvar.mtimes at 326
                            before =
                            findhash(new_mt_hash_aux,current_hash,new_mt_hash_counter);
                            % first among new monomials

In ==> sdpvar.mtimes at 43
        Z = (Y'*X')'; % Optimized for this order (few variables *
        many variables)

In ==> Exp_price at 25
tot=tot*(1-PR(m));

Actually PR is a function os X which involves all variables in X. So I find with a larger X(5 by 5), the program is frozen in calculating tot=tot*(1-PR(m)), that is why I ask the upper bound of order in Yalmip. Do you need other information for the problem? I can send the my code to you.

Thanks,

Yanyan

[Johan Löfberg]

Send the code

[Johan Löfberg]

Have you looked at the solution status returned from solvesdp? Most likely the solver has crashed.

You could also turn on the debug flag to see the crash

solvesdp(constraints,objective,sdpsettings('debug',1))

[Yanyan]

Yes, I have used 'debug', but how to make use of the debug flag? Besides, I get the result of solvesdp that :problem:2, what does it mean? I didn't found the definition of problems in Yalmip.

[Johan Löfberg]

If the code crashes when you have turned on the debug flag, you will see the error message in detail (the try-catch logic is turned off). If it doesn't crash there will be no difference

For error codes, see yalmiperror. (2 means unbounded objective)

[Yanyan]

Hi Johan,
I have sent you the code on Thursday but maybe you fail to receive it. So I sent it again. The attached is my code, and it contains a Note.txt, which has some explanation about how to run it. Hope it helps to understand.
Thanks a bunch!
Yanyan

[Yanyan]

It only shows the problem:2 and the info: is (1*324 variables), so what is the cause of problem 2?

[Johan Löfberg]

I answered you per email yesterday (your model explodes in size, you will have on the order of 65^6 nonlinear terms in your mode, i.e., billions, completely intractable).

[Yanyan]

Apologize for not receiving your answer. But you mean for X=4*4, it can solve, but for X=6*6, the order is too high so that it is not solvable, right? It is not due to the order of each variable but the number of variables?

[Johan Löfberg]

error 2 is listed as  "Unbounded objective function" in yalmiperror, and that is what you have in your info variable too if you display it (it is not displayed if you simply display the solution struct, you must display solution.info

[Johan Löfberg]

A problem with a 6x6 variable is typically trivially small. However, you start multiplying a lot of nonlinear expressions. If you multiply two expression involving 65 variables (which each element in PR has) you get something like O(65^2) monomials. Now you multiply that with an expression involving another 65 variables and end up with O(65^3). So in the end, expect an expression involving O(65^6) terms. It is simply a way too complicated model. (just for fun, do (a+b+c+d+e+f)*(x+y+z+w+u) by hand, and now convince your self that with 65 terms, it will be a loooong list of monomials. now take your result and multiply it with another sum of variables (e+r+t+p+k). and repeat 3 more times...)

And as I said in the mail, you probably want X to be fully parameterized, not symmetric, X = binvar(NodeNum,NodeNum,'full')

[Yanyan]

Ok, so if I want to show solution.info, how could I do if my initial code is like this?
options=sdpsettings('solver','bnb','verbose',0,'debug',1);
opt=solvesdp(F,pl,options)

[Johan Löfberg]

opt.info

which essentially is the same as

yalmiperror(opt.problem)

[Yanyan]

Yes, you are absolutely, actually I only need the half of the variables in X, and I can only use the right part of X and ignore the left part, so that i can get the result as
NaN   0    1    1
NaN NaN  0    1
NaN NaN NaN 0
NaN NaN NaN NaN, right?
Again appreciate your quick response, I will modify my code to see the new result, : )
Yanyan

[Johan Löfberg]

If a variable isn't part of the optimization problem, then it will have the value NaN when you evaluate the variable using double

[Yanyan]

Hey Johan,
Now I have another problem. I want to get a binary matrix X, still the constaint C is the linear combination of the binary variables in X, but the objective P is the linear combination of binary variables/C. So now when I use bnb or cplex solver, I always get a very bad result, which satisfies the constraint but the objective is  far from the optimal. Actually I found it may be the worst objective that satisfying the constraint. When I change the objective from P to -P, the result is the same, which indicates that the objective function doesn't even work. So do you think the P in my problem is too complex? Is it solvable? Or how could I solve it ?
Thanks so much!
Yours sincerely,
Yanyan

[Johan Löfberg]

You would have to give an explicit example. A linear combination of a constant and binary variables is not a complex objective

You do know that the objective is *minimized* I hope (since you said you obtained the worst possible)

[Yanyan]

Hi Johan,

In detail, the constraint P is a summation of binary variable production, the objective C is the ratio of a summation of binary variable production to P. It is like P=X(1,2)*X(2,3)+X(1,4)*X(4,3)+X(1,2)*X(2,4)*X(4,3), C={2*(X(1,2)+X(2,3))+2*(X(1,4)+X(4,3))+3*(X(1,2)+X(2,4)+X(4,3))}/P. Now I want P >= threshold, and minimize C. Currently, the optimization runs only for a few seconds to get the result, but the resulting cost is apparently not optimal, since I can easily find a better result by hand.

Do you need my code for reference?

Thanks,

Yanyan

[Johan Löfberg]

First rule of integer programming: Avoid nonlinearities at all costs
Second rule of integer programming: See rule 1.

almost at least. As you've coded it now, I guess the last resort bnb solver is invoked, at it explicitly warns you that it will most likely not deliver a good solution.

You will have to model the bilinear products, introduce a variable W1223 to model X(1,2)*X(2,3). W1223 should be zero when either of the two X is zero, and 1 otherwise, i.e W1223 = X(1,2) AND X(2,3)

W1223 = binvar(1,1)
W1223 <= X(1,2)
W1223 <= X(2,3)
W1223 >= X(1,2)+X(2,3)-1

and similar for all terms in P

Objective even worse. Now you have fractional terms.

(2*(X(1,2)+X(2,3))+2*(X(1,4)

+X(4,3))+3*(X(1,2)+X(2,4)+X(4,3)))/P

Write as minimize t subject to 2*(X(1,2)+X(2,3))+2*(X(1,4)

+X(4,3))+3*(X(1,2)+X(2,4)+X(4,3))}/P <= t

which you write as

2*(X(1,2)+X(2,3))+2*(X(1,4)

+X(4,3))+3*(X(1,2)+X(2,4)+X(4,3)) <= t*P = t*(W1223 + ---)

Bilinear terms again, this time between the general variable t and the Wijkl variables. These you also have to model

sdpvar tW1223
...

if W1223 is zero then tW1223 should be zero, otherwise tW1223 should be t. You now W1223 is less than or equal to 1, so the big-M model is

tW1223 <=  M*W1223
-M*(1-W1223) <= t-W1223 <= M*(1-W1223)

M is a small-but-sufficiently large big-M constant which you have to derive a good value for. It should follow trivially from your model since it is easy to derive upper bounds on all terms since everything is bounded due to the use of binary variables (for instance, t can never be larger than 17)

http://users.isy.liu.se/johanl/yalmip/pmwiki.php?n=Tutorials.Big-MAndConvexHulls