Optimization problem with integer variables starting from a large dataset of tested configurations

Dear all, I have an optimization problem with 3 integer variables that can have a value from 1 to 3000, so 2.7E10 possible configurations.

Goodness=function(a,b,c);

function domain ([1:3000],[1:3000],[1:3000])

I have already tested 3E4 configurations and I'm confident to be 70% close to the maximum allowed result.

My wish is to start a global optimization procedure that take into account the population of configurations already tested.

Thanks in advance for the help you will provide.

Best Regards,

Lorenzo

[Walter Roberson]

Is the Goodness function "black box"? That is, do we need to answer in the general case where the optimization is only permitted to know that the Goodness function takes integer inputs and calculates the result somehow ? Or is the Goodness function expressible using Integer Programming or Mixed Integer Programming, where the goodness is a linear combination of the inputs?

In the general "black box" case, knowledge of the configurations already tested does not give any information about where the solution might be. For example, the function could be equivalent to

   if a == 2871 && b == 937 && c == 298
     goodness = -1;
   else
     rng(a);
     p1 = randi([1 3000]);
     rng(b);
     p2 = randi([1 3000]);
     rng(c);
     p3 = randi([1 3000]);
     goodness = a * (a ~= p3) + b * (b ~= p1) + c * (c ~= p2);
   end

analytically we can see that if the random numbers happen to match then in the "else" goodness could be as low as 0, but that the special treatment of one particular point is lower than that. Knowledge of the very irregular surface the above gives from the "else" does nothing to tell you where the best solution is.

[lorenzo neri]

The Goodness function is a real device. Using Matlab I'm able to set in the device the three input parameters and receive back an output. I need to find the configuration that maximize this output.

To be able to do a fast sampling of the possible configurations I made a function:

[a,b,c]=samplingF(x,y)

Using x=[1:159] y=[1:361]

I obtained from the device the Goodness reported in the next figure

I'm pretty confident that with this fast sampling I'm close to the optimum configuration, but I want to start an additional optimization taking into account the experience gained.

Tell me if you need more details.

Thanks, Lorenzo

Answer 1

[Walter Roberson]

Sorry, in the situation you describe, it is not possible to make use of any information you have already calculated. You have no reason to expect that there will not be some points that are much higher or much lower than the points you happened to have sampled. You will need to test all 27000000000 possibilities to find the minimum.

If circumstances were different and you instead could at least assume continuity instead of having no idea how the device produces values, then you could take approaches such as estimating gradients in order to make predictions about direction to look in. For some shapes of interest you might be able to apply Compressive Sensing