Discrete integers function optimization ?

Hi everyone,

I was wondering what is the best method or optimization tool i can use for a optimization of a function which it's variables are discrete integers ?

I already used a metaheuristic method (PSO), so i was wondering if there are other method (mathematically) can be used in such kind of optimization problems ?

The problem include constraints such as a check function to test the feasibility of the solution but it's in other file than the main objective function file.

I already saw a similar question and the answer was using GA optimization tool, but i can't use it since it falls in the same category of heuristic methods which i previously mentioned that i used one of them (PSO).

Answer 1

[Walter Roberson]

In the situation where all of the variables are discrete values, you can just try all of the possible combinations of values. This might take a while...

In the situation where the function is linear, then you can use https://www.mathworks.com/help/optim/ug/intlinprog.html

In some cases there are analytic approaches that can reduce the search space, if you have the Symbolic Toolbox and do a bunch of programming yourself. You find the derivative and solve for the zeros of that, which gives the locations of the extrema in continuous coordinates. You take the second derivative and substitute the locations into that and look at the sign() of that value in order to determine which kind of extrema you have. This gives you some information that can be used to partition the search space according to which extrema any given point is closest to. Now you can evaluate for all discrete points in the catch basins of the minima in order to find the local minima in discrete terms. By examining the local gradient, you could potentially also eliminate some of the searching.

[hossam eldakroury]

Thanks man for your great answer, i was wondering if there is a tutorial video or link or pdf that explain how to do this step by step !!

I became much familiar with matlab than before but still a very beginner, so any tutorial will be helpful.

[Walter Roberson]

Which part do you need done step by step?

I am not going to go through the analytic approach; it would need a bit of development work, and figuring out how to partition the basins of attractions properly in the general case could be difficult. Possibly for certain kinds of functions it might not be bad.

The constraints would possibly be handled by solving each one with regards to some variable, and then substituting for that variable in the original functions, getting out a more complicated function of fewer variables that automatically satisfies the constraints (other than the integer restriction.)

https://www.mathworks.com/matlabcentral/fileexchange/35720-minlp-mixed-integer-nonlinear-programming

https://www.mathworks.com/help/finance/portfolio.setsolverminlp.html

https://tomopt.com/docs/models/tomlab_models010.php

https://www.inverseproblem.co.nz/OPTI/index.php/Probs/MINLP

And an ACO based one:

http://www.midaco-solver.com/

[hossam eldakroury]

So will (intlinprog) be usfel if my x variables is a string of discrete integers decisions ?

Okay may i should mentioned that in the begining,

My objective function variable x is a string of set of 15 discrete integers, they are choosed among 133 integers and they are all unique (non repeated).

So as you can see the variable is like set of integers that doesnt involved in calculation but they are just decisions that affects the value of objective function.

To make it clearer its like binary decisions for a network to decide the best path (minimize objective function), something like travelling salesman problem.

So please, if the your mentioned techniques don't staisfy that type of problem, then mention other techniques or functions that could help and not heuristic or metaheuristic like GA, PSO, ... etc.

[Walter Roberson]

"So will (intlinprog) be usfel if my x variables is a string of discrete integers decisions ?"

Yes.

"and they are all unique"

That could be the tricky part to write in terms of linear constraints.

"something like travelling salesman problem."

Are the values just present / not present? Or are they ordered?

If the values are just present / not present, then uniqueness becomes trivial and exactly 15 out of 133 is easy enough to implement. But if they are ordered and also unique then I need to consider more about how that could be implemented.

[hossam eldakroury]

Really thanks man,

Now i will focus on how to use (intlinprog) and implement my objective function and constraints to build the optimization code.

[Usman Bashir Tayab]

Hi Hossam,

Please can you share PSO codes for discrete integers variables. As I need to implement discrete integers variables using PSO for my problem.