how can i make globalsearch return integer results(select the whole item and not fraction of the item) ?

Hi all,

I have an optimization problem at which I would like to find the maximum value of the objective function at given constraints. it is easy to be described as rucksack problem, which means no fraction of the item should be selected rather the whole item should be selected.

using the GA function in matlab does solve the problem for me, yet it may find a local maximum and not the global maximum. in order to avoid this problem of GA function, I have tried to use globalsearch "gs" function in matlab.

unfortunately, I was unable to force gs function to return results containing whole items. here is my code:

      %Data contain information about the item to be selected (number of columns = number of items can be selected  and number of rows = number of constraints)
      Data= [0.3909    0.3143    0.4323    0.3573;
      0.8218    0.6681    0.6925    0.7125;
      0.0002    0.0003    0.0002    0.0003;
     21.0000   24.5000   31.5000   38.5000;
      3.0000    7.0000   13.5000   22.0000
      1         1        1         1];
      Temp.Input.Aly = [1 1 1 1];
      Lim = [1; 1; 1; 100; 50; 1 ];  
      rng default % For reproducibility
      gs = GlobalSearch;
      MyObj = @(x)(-1*(x(1) + x(2) + x(3) + x(4) ));  
      c = @(x)[x(1) + x(2) + x(3) + x(4) + x(5) - Lim(1);
          x(1) + x(2) + x(3) + x(4) + x(5) - Lim(2);
          x(1) + x(2) + x(3) + x(4) + x(5) - Lim(3);
          x(1) + x(2) + x(3) + x(4) + x(5) - Lim(4);
          x(1) + x(2) + x(3) + x(4) + x(5) - Lim(5);
          x(1) + x(2) + x(3) + x(4) + x(5) - Lim(6)];

      nonlinfcn = @(x)deal(c(x));problem = createOptimProblem('fmincon','x0',zeros(length(Temp.Input.Aly),1),...
      'objective',MyObj,'lb',zeros(length(Temp.Input.Aly),1),'ub',Temp.Input.Aly,...
      'nonlcon',nonlinfcn);
       problem.options.TolCon = 1.0000e-12;
       x = run(gs,problem);

so I would like the optimum selected result to be the global maximum and to be the whole item and not part of each item.

best regards,

Answer 1

[Walter Roberson]

fmincon() cannot be used with integer constraints. For fmincon(), the objective function must be continuous and differentiable within its limits. The same is true for all four of the searches supported by createOptimProblem: fmincon, fminunc, lsqnonlin, and lsqcurvefit .

[Housam]

Hi Walter,

thank you very much for your reply, what do you suggest to use for the above problem then?

so, I believe that the GA function is my solution yet I am unable to change my constraints and objective function to make the GA function give only one output which is the best selected item that best fit the given constraints.

my idea is to force the GA function to select only one item by lowering the objective function unknown variables to one (@(x) -1*(x(1)) ) instead of the previous objective function ( @(x)(-1*(x(1) + x(2) + x(3) + x(4) )) )

unfortunately, I was unable to get the GA to operate using this function. please find the code bellow:

if true
  % code
   Cal.options = gaoptimset('Display','off', 'PlotFcns',@gaplotbestf,'StallGenLimit',Inf ,'TolFun', 1e-6, 'PopulationSize',200, 'InitialPopulation', ones(200,1) );  %pop size: min(max(10*length(Temp.Input.AWT),40),100) - 'CreationFcn',@gacreationuniform,  % stopping for gaoptimset: 'Generation',Inf,'FitnessLimit',-Inf,'StallGenLimit',Inf 
      Cal.fun = @(x) -1*(x(1));[Ressult.x,Ressult.fval,Ressult.exitflag,Ressult.output,Ressult.population,Ressult.scores] = ga(Cal.fun,1,Cal.A(1:end-1,:),Cal.b(1:end-1,:),[],[],0,1,[],1,1);

end

for this example, I would like for the optimization function to return item in column 2 in the Data (the expected output should have the following ranks for column index [2 4 1 3]; which mean the second column in the data is the best fit to the constraints then the forth column in the data is the second best fit and so on; ) as an optimum solution for the given constraints.