Search code examples
pythonscipynonlinear-optimizationmixed-integer-programmingdifferential-evolution

Binary variables for minimization by scipy differential evolution

I have a non-linear minimization problem that takes a combination of continuous and binary variables as input. Think of it as a network flow problem with valves, for which the throughput can be controlled, and with pumps, for which you can change the direction.

A "natural," minimalistic formulation could be:

arg( min( f(x1,y2,y3) )) s.t.
    x1 \in [0,1] //a continuous variable
    y2,y3 \in {0,1}  //two binary variables

The objective function is deterministic, but expensive to solve. If I leave away the binary variables, Scipy's differential evolution algorithm turns out to be a useful solution approach for my problem (converging faster than basin hopping).

There is some evidence available already with regard to the inclusion of integer variables in a differential evolution-based minimization problem. The suggested approaches turn y2,y3 into continuous variables x2,x3 \in [0,1], and then modify the objective function as follows:

(i) f(x1, round(x2), round(x3))

(ii) f(x1,x2,x3) + K( (x2-round(x2))^2 + (x3-round(x3))^2 )
     with K a tuning parameter

A third, and probably naive approach would be to combine the binary variables into a single continuous variable z \in [0,1], and thereby to reduce the number of optimization variables.

For instance,

if z<0.25: y2=y3=0
elif z<0.5: y2=1, y3=0
elif z<0.75: y2=0, y3=1
else: y2=y3=1.

Which one of the above should be preferred, and why? I'd be very curious to hear how binary variables can be integrated in a continuous differential evolution algorithm (such as Scipy's) in a smart way.

PS. I'm aware that there's some literature available that proposes dedicated mixed-integer evolutionary algorithms. For now, I'd like to stay with Scipy.

Solution

  • I'd be very curious to hear how binary variables can be integrated in a continuous differential evolution algorithm

    wrapdisc is a package that is a thin wrapper which will let you optimize binary 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.

    As of v2.0.0, it has two possible encodings for binary:

    • ChoiceVar: This uses one-hot max encoding. Two floats are used to represent the binary variable.
    • GridVar: This uses rounding. One float is used to represent the binary variable.

    Although neither of these two variable types were made for binary, they both can support it just the same. On average, GridVar requires fewer function evaluations because it uses one less float than ChoiceVar.