How to use minlp with non analytic optimization function

Im trying to formulate an optimization problem that minimizes the total passengers time of passengers on buses.

My objective function Z=f(x) in non linear and not analytical, in such that it changes every loop.

I have 72 decision variables (x), 48 are continous and 24 are binary.

I think that minlp is the best method to use here, but I cannot set the optimization function.

 Opt = opti('fun',function2optimize,'ineq',A,b,'bounds',min_b_val,max_b_val,...
            'xtype',xtype);

My function2optimize contains a lot of calculations and in the final part of its there is the formulation of Z.

My question is how to set the function2optimize? I have wrote:

function2optimize = @ (Z) but have the error:

??? Error: File: function2Optimize.m Line: 1 Column: 27
Expression or statement is incomplete or incorrect.

Thanks a lot,

Hend

Answer 1

[Alan Weiss]

I am not sure what you are asking. The only MATLAB solver I know for MINLP problems is ga from Global Optimization Toolbox. Use the Mixed Integer Optimization documentation to guide you in setting up the problem.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[hend ma]

Thanks a lot Alan for answering me.

My problem has 27 varibles, when the variables 19..27 are binary (0/1).

In addition, I have constraints like x(10)<=x(19), x(11)<=x(20).. x(18)<=x(27). And constraints for the binary variables like: x(19)+x(24)>=1.

I tried to use the ga for solving my mixed integer problem, but I found that the result is always with 1 for all the binary variables, and the matlab did not consider the constraints. because when I tried to fix the binary variables to 0, the values of x(10)..x(18) was bigger than zero (despite the constraints x(10)<x(19) and so).

I read the help of matlab for ga with mixed integer variables and found that I have to put 'PopulationType','doubleVector' in the options of gaoptimset, but it did not help.

Thanks a lot

Hend

Answer 3

[Alan Weiss]

You did not state how you included the constraints such as

 x(10) <= x(19);

I hope you used linear inequality matrices and not nonlinear constraints.

I do not understand what you mean when you say "the matlab did not consider the constraints." I can assure you that, if you formulate your problem properly, solvers generally return feasible solutions, and warn you if they do not find feasible points.

For more help you will have to be more explicit in describing exactly how you set up your constraints.

Alan Weiss

MATLAB mathematical toolbox documentation

[hend ma]

I do use linear inequality matrices and not nonlinear constraints. Attached 2 files of mini optimization that I built in order to check the problem. I ran matlab with these two functions, and the optimal fval was 58.5, with value of 1 of the all integer variables (19..27). while by checking the fval (Z) with x(20)=0 and x(11) =0 (other variables are the same as the optimal value). Even though this solution meets all constraints with Z= 53.5. the matlab did not give me that solution.(there are more than one solution that give me 53.5 as Z). I did not know what is the problem. Thanks a lot Hend

[Alan Weiss]

There are many reasons why ga might not have converged to a satisfactory answer.

• You have a lot of variables. ga might need a larger population size.
• ga is random. If you run it multiple times does it come up with different answers?
• Did you try seeding ga with a partial initial population? If not, please try doing so with your better final point. If so, did ga improve the answer, or return a poorer solution?

Finally, I suspect that you could reformulate your problem somewhat along the lines of the travelling salesman example to convert it to a MILP. Then you would be able to use the faster and more reliable intlinprog solver instead of ga.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[hend ma]

I tried the 3 points you offered but I still getting ones for all the binary values. Instead of converting the model to MINLP, which may take a lot of time. I think to solve the proplem hueristicly. so the binary varibles may be any value from 0 to 1. and when these variables are less than 0.5 that mean that they are zero. My problem is that there are variables that have to be zero when the binary variables are less than 0.5 (which is zero). I do not know how to formulate the constraint x(10)-round(x(19))<=0 as: A(x)<=b. When x(19) had to be the binary variable. Thanks a lot, Hend

[Alan Weiss]

Did you try putting in a partial population with the better solution as an initial point? If so, what happened?

I suspect that your "better" point does not satisfy your linear inequalities. You can check by evaluating

 A*x - b

where x is your better point, and checking whether the maximum entry is positive.

Alan Weiss

MATLAB mathematical toolbox documentation

[hend ma]

You are right. I tried again with initial population that satisfies my inequalities and it works. My question is: Does GA check other combinations of changing the values of the integer variables? I am asking this because I get that the optimal solution is my initial population. Indeed I do not know if my initial population is the better solution, because I am performing this optimization iteratively and dynamically. So I cannot check for each optimization what the "better solution" is and put it as initial population.

Thanks a lot Hend

[Alan Weiss]

Of course ga checks other values of the variables. That is what it does to optimize.

But you cannot rely on ga to find the global optimum. The algorithm is stochastic, and cannot guarantee that it finds anything.

If you really want to stick with ga, then I suggest again that you give a much larger initial population, and run it multiple times.

But you would probably do yourself a favor to look carefully at the travelling salesman example I pointed you to earlier, and see whether you can reformulate your problem to be MILP instead of MINLP.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation