Discontinued function optimization

Question

I am struggling with transport optimization problem, that simplified might stated as:

• Minimize the number of bananas transports to the shop in the following 5 days (transported_bananas = [n1_bananas, n2_bananas, n3_bananas, n4_bananas, n5_bananas])
• The number of bananas in the shop, at any moment, cannot exceed 1000 (max constrain)
• The number of bananas in the shop, at any moment, cannot be lower than 100 (min constrain)
• Predicted bananas bought in the shop in the 5 following days are: (predictions = [100, 500, 800, 10, 30])

I use scipy.optimize.minimize with SLSQP. I have ineq min and max constraints for each day, something like: min_bananas > transported_bananas[0, current_day] - predictions[0, current_day]and similar to max constraint.

The function which I am trying to optimize is: transport_number = sum(transported_bananas > 0)

SLSQP cannot find minimum of this function. I believe that is because only if transported bananas in given day are 0 there is no transport. It also does not matter if 1 banana is transported or 100000 bananas is transported - it is still one transport in given day. Should I look for different solver then (not based on gradient) or should I think about scaling transport number or think about making the objective function continues somehow?

Answer 1

Your problem has continuous variables (the number of bananas delivered each day) but a discrete objective function (the number of deliveries over the period).

As you noticed, counting the number of deliveries by using the expression "sum(transported_bananas > 0)" makes the objective function discontinuous. SLSQP (Least Square Sequential Quadratic Programming) belongs to SQP methods which require the objective and the constraints to be twice continuously differentiable.

Your problem can be expressed as a Mixed-Integer Linear Problem (MILP) and then solves using MILP solvers. To do so, you have to introduce binary variables to count the number of deliveries and link these variables to the number of bananas using the so-called "big M" modeling technique.

To solve it directly, without any reformulation, you can also use LocalSolver, which is a global optimization solver (contrary to what the name suggests :-). Indeed, LocalSolver is able to handle discontinuous expressions like "sum(transported_bananas > 0)". Please note that LocalSolver is a commercial solver. Nevertheless, academic and trial licenses are available for free.