Scipy Differential Evolution with integers

Question

I'm trying to run an optimization with scipy.optimize.differential_evolution. The code calls for bounds for each variable in x. But I want to a solution where parts of x must be integers, while others can range freely as floats. The relevant part of my code looks like

    bounds = [(0,3),(0,3),(0,3),???,???]
    result = differential_evolution(func, bounds)

What do I replace the ???'s with to force those variables to be ints in a given range?

Preview

You can't. In fact, none of the solvers in scipy.optimize support such a constraint. pyevolve and DEAP are two other Python libraries for building genetic algorithms which offer control over your mutation function such that you could constrain some or all of the elements in your solution vectors to be integers. Depending on the nature of your problem you might also take a look at integer programming libraries such as cvxpy or PuLP. – Antonio

Okay, thanks. I'll go figure out DEAP then. – Preview

Good luck! You should probably have a think think about whether your optimization problem could be expressed in a form that could be solved using existing ILP or MILP solvers. Simulated annealing might be another option worth exploring. It's hard for me to offer any specific recommendations without knowing anything about the nature of the problem you're trying to solve. – Antonio

Answer 1

As noted in the comments there isn't direct support for a "integer constraint".

You could however minimize a modified objective function, e.g.:

def func1(x):
    return func(x) + K * (x[3] - round(x[3]))**2

and this will force x[3] towards an integer value (unfortunately you have to tune the K parameter).

An alternative is to round (some of) the real-valued parameters before evaluating the objective function:

def func1(x):
    z = x;
    z[3] = round(z[3])
    return func(z)

Both are common techniques to approach a discrete optimization problem using Differential Evolution and they work quite well.

Ramburt

These are two interesting approaches. The first one seems to yield a unique solution, but at the cost of an additional parameter ($K$). Is there any recommendation regarding the specific choice of one of the two for given "typical" problem types? For instance in case of a binary variable? And what about combining the two approaches? – Bipartisan

@Bipartisan I've tried the second one for some scheduling tasks and it worked quite well. Not sure if there is any recommendation... – Ramburt

Answer 2

Differential evolution can support integer constraint but the current scipy implementation would need to be changed.

From the scipy source code it appears that their DE is based Storn, R and Price, K, Differential Evolution - a Simple and Efficient Heuristic for Global Optimization over Continuous Spaces, Journal of Global Optimization, 1997

However there has been progress in this field as pointed out by this review paper Recent advances in differential evolution – An updated survey

There are a few papers which introduce changes to the algorithm so that it can handle ints. I have not had time to look at all the options but perhaps this paper could help.

An Improved Differential Evolution Algorithm for Mixed Integer Programming Problems

Cayman

Answer 3

What do I replace the ???'s with to force those variables to be ints in a given range?

wrapdisc is a package that is a thin wrapper which will let you optimize bounded integer variables alongside floats with various scipy.optimize optimizers. There is a usage example in its readme. With it, you don't have to adapt your objective function at all. It internally uses rounding in order to support integers, although this detail is hidden from the user.

Clippard