Pattern search with integer decision variable.

Hello.

I tried to solve Nonlinear integer programming to minimize using Optimization tool box.

I understand how I input both objective function and nonlinear constraint function.

However, I don't know how I obtain some decision variable are integer and others are real variable. Cuz, there is no option in pattern search tool box and function in matlab.

Are there any method to get integer variable using pattern search in matlab tool box?

Answer 1

[Alan Weiss]

If you have mixed (some integer, some continuous) variables, then no, there is currently no patternsearch solution. Use ga for this type of problem.

However, if all your variables are integer-valued, then you might be able to use patternsearch. Start at an integer point, set ScaleMesh off, and set TolMesh to 0.9 or so. I believe that, with those settings, patternsearch will search only integer points.

Alan Weiss

MATLAB mathematical toolbox documentation

[J. Womack]

Tried this and it worked like an absolute charm. I need to validate vs solutions I get using fmincon and continuous variables to ensure I'm getting the right values, but so far so good.

[Matlab Noob]

I set

x0 = [500 500 500 500 500 500 50 50 50];

 lb = [1  1  1  1  1  1   1  1  1];
 ub = [1000 1000 1000 1000 1000 1000 100 100 100];
 option=psoptimset('Display','Iter','TolMesh',0.9,'Cache','on','CacheTol',sqrt(1e-5),'CompletePoll','on','ScaleMesh','off','PollMethod','MADSPositiveBasis2N');

And I got this result.

 Iter   f-count      f(x)      constraint   MeshSize      Method
    0     1       151511    1.125e+04          0.9    
    1 16244       824671            0        0.001   Increase penalty
    2 18000       356324            0        1e-05   Increase penalty
Maximum number of function evaluations exceeded: increase options.MaxFunctionEvaluations.

x =

    2.7543    5.0000   69.1333  144.3475  132.7128  173.7526    3.0000    2.0000    6.0000

What do i miss during this work...? Should I change any other options?

[Alan Weiss]

I'm sorry that I didn't say this earlier, but you should not use MADS if you want integer values. Leave the poll method alone. Also, it looks like you have nonlinear constraints. Are those absolutely necessary? I am not sure what they will do to the integrality of your results. Finally, I am not sure that you should be using cache. You might try to time things with cache both on and off, to see if it is helping or hurting.

Alan Weiss

MATLAB mathematical toolbox documentation

[Cassandra Wong]

Hi Alan,

I tried

option = optimoptions(@patternsearch,'TolMesh',0.9,'ScaleMesh',false);

But I got x =

    0.4000    0.6000    0.2000    0.5000    0.5000    0.2000    0.0000

Why is it that I still get float instead of integer?

How should I modify the code to get integer only?

Thank you.

Sincerely,

Cassandra

[Alan Weiss]

Did you start at an integer point? Are your bounds integer-valued? Do you have linear constraints? Do you have nonlinear constraints?

In short, we need to see more details, including your entire problem setup.

Alan Weiss

MATLAB mathematical toolbox documentation

[Cassandra Wong]

I am trying to achieve full observability, f(x) with minimum number of installation given that f(x) >= 1.

f(x) = [x1+x2; x1+x2+x3+x6+x7; x2+x3+x4+x6; x3+x4+x5+x7; x4+x5; x2+x3+x6; x2+x4+x7]

Every component of f(x) must be >= 1 and x can be either 0 or 1.

For example, with x2 and x4 = 1 and others = 0, full and max observability is achieved with minimum number of installation which is 2 in this case as f(x) = [1; 1; 2; 1; 1; 1; 2]

I'm new to patternsearch and the following is my code

n = input('Number of bus: ');
A = -(input ('Binary connectivity: '));
b = -(ones (n, 1));
a0 = zeros (1,n);
lb = zeros(1,n);
ub = ones(1,n);
option = optimoptions(@patternsearch,'TolMesh',0.9,'ScaleMesh',false);
x = patternsearch(@ttest,a0,A,b,[],[],lb,ub,[],option)

but I was unable to get the desired output.

Please help.

Sincerely,

Cassandra

[Torsten]

Use "intlinprog" instead of "patternsearch".

Best wishes

Torsten.

[Doug Rank]

Hi Alan,

I have tried with these options:

        opts = optimoptions('patternsearch', ...
            'ScaleMesh', false, ...
            'MeshTolerance', 0.99);

And called patternsearch by:

        [x, fval, exitflag, output] = patternsearch(fitnessFunction, ...
            xo, A, b, [], [], zeros(1, nVariables), ...
            ones(1, nVariables), [], opts);

(where xo is one of the feasible initial population members I was giving to the ga() before, A and b are the original linear constraint matrices I was using, and nVariables is the length of xo).

However, I got this error:

Error using lcondirections (line 38) Constraints are dependent at current iterate. Try increasing OPTIONS.TolBind (< eps).

Error in poll (line 60) [DirVector,TangentCone] = lcondirections(AdaptiveMesh,MeshSize,Iterate.x, ...

Error in pfminlcon (line 62) [successPoll,nextIterate,optimState] = poll(FUN,X,Iterate,MeshSize,Aineq,bineq, ...

Error in patternsearch (line 377) [X,FVAL,EXITFLAG,OUTPUT] = pfminlcon(FUN,objFcnArg,initialX,numberOfVariables,Iterate, ...

Error in optimize (line 385) [x, fval, exitflag, output] = patternsearch(fitnessFunction, ...

I also tried modifying the options after googling the error to:

        opts = optimoptions('patternsearch', ...
            'ScaleMesh', false, ...
            'PollMethod', 'GSSPositiveBasis2N', ...
            'MeshTolerance', 0.99);

and got a similar error ending in:

Error using gssdirections (line 39) Constraints are dependent at current iterate. Try increasing OPTIONS.TolBind (< eps).

Error in poll (line 57) [DirVector,TangentCone,AugmentedDirs] = gssdirections(MeshSize,Iterate.x, ...

Would you happen to know what the issue may be here?

[Alan Weiss]

I suspect that you have linear constraints that are redundant or nearly so. Remove the redundant constraints and all should be well.

But I am not sure that the result will be integer-valued.

Good luck,

Alan Weiss

MATLAB mathematical toolbox documentation

[Ryan Potter]

Hi, I just wanted to check whether this advice was still valid? I have followed the points above but still generate non-integer values. I'm using the following code:

fun     = @computeMagVol;
x0      = [10,25,20,2];
A       = [];
b       = [];
Aeq     = [];
beq     = [];
lb      = [1, 1, 1,1];
ub      = [21,51,41,4];
nonlcon = @combineConstraints;
options = optimoptions('patternsearch',            ...
                       'PollMethod'     , 'GPSPositiveBasis2N', ...
                       'Display'        , 'Iter',  ...
                       'ScaleMesh'      , 'off',   ...
                       'AccelerateMesh' , false,   ...
                       'TolMesh'        , 0.9,    ...
                       'PlotFcn'        ,{@psplotbestf,@psplotmeshsize});

[x,fval,exitflag,output] = patternsearch(fun,x0,A,b,Aeq,beq,lb,ub,nonlcon,options);

My objective function use the integer variables to select discrete, non-integer variables from a list. After the following computations:

  Iter   Func-count       f(x)      Constraint   MeshSize      Method
    0         1      75615.1        104.4          0.9        
    1        50      71970.7            0        0.001   Increase penalty

I obtain that x = [1 44.5, 21, 4] which causes my objective function calculation to fail. The same functions work with the ga algorithm, however I was hoping to use patternsearch as it supports having the object function and non-linear constraints in a single function. Any advice would be greatly appreciated.

[Alan Weiss]

As I said earlier, I am not at all sure that this method works when you have nonlinear constraints. Sorry.

Alan Weiss

MATLAB mathematical toolbox documentation

Answer 2

[Benjamin Duquenne]

Hi, I would like to use patternsearch for full integer problems. To do so, I set the ScaleMesh off, and set TolMesh to 0.9. However I still have problems with the TolBind that has to be way too high (~1e3) to make the code work, otherwise I have errors like 'Constraints are dependent at current iterate'. Could you help me? Thanks in advance.