How to combine 2 constraints to minimise cost and maximise capacity using DOcplex.mp in Python

Question

I have the following OF to minimize the cost of supply chain:

mdl.minimize(mdl.sum((cs+ch+cf+cv*d[j])*q[j] for j in arcs) + mdl.sum(α*(eh+et*d[j])*q[j] for j in arcs) + mdl.sum(β*(gh+gt*d[j])*q[j] for j in arcs) + mdl.sum(X[f]*cjf for f in comb))

Where cs, ch, cf, cv, eh, et, gh, gt, cjf, α and β are a series of constant parameters.

d[j] is the distance between origin iand destination j that are combined in a list of arcs or tuples.

q[j] is the flow variable between origin i and destination j in arcs.

X[f] is a binary variable to open a facility in destination j with capacity f, the possible combinations of j and f are listed in comb.

The first constraint 1 ensures the flow q[i,j] from origin i does not exceed its maximum availability of material dQ in i. D[(i, j)] is a binary parameter that is 1 if the distance between origin i and destination j is less or equal than a treshold value, else the value of D[(i, j)] is 0. (This parameter helps us to limit the transport distance.)

for i in I: mdl.add_constraint(mdl.sum(q[(i, j)]*D[(i, j)] for j in J) <= Qi[i])

The second constraint 2 ensures the flow q[i,j] to a destination j equals the capacity of the opened facility in destination j with capacity f.

for j in J: mdl.add_constraint(mdl.sum(q[(i, j)]for i in I) == mdl.sum(X[(j,f)] for f in F))

But then, we want another constraint 3 that ensures the sum of capacities f in the facilities opened at destinations j has to be as close as possible to the total demand of capacities E. Let's say there is an energy demand of 100 MW E = 100, then we want to reduce the cost in OF of the supply but also make sure we reach the demand E. Otherwise minimizing the cost would be 0. This constraint can be formulated like:

mdl.add_constraint(mdl.sum(X[j,f]for j in J for f in F) == E)

Unfortunately, this solution is never feasible. If we replace == by <= than it is feasible, but it is at minimal cost and the capacity is nowhere near maximal. We don't need this to be a strict constraint but we do wanna get as close to E as possible, by opening multiple facilities at destinations j with different capacities f. (Eg. we could have one destination with 20 MW, one at 5 MW, two at 30 MW and another at 15 MW to reach 100 MW by opening 5 destinations)

One way is to force the model to open N number of locations j, however, we have a set of 128 locations. To find the minimum cost and maximum capacity from a ranges of scenarios from N=1 to N=128 means we need to run this model 128 times.

On top of the above-mentioned constraint we have 3 additional constraints:

• We can only select destination j to built a facility and open it at only one capacity f.
• The sum of destinations j to open is greater than 0.
• There is no negative flow q between origins i and destinations j

Is there a way to:

• Make constraint 3 less binding, but still try to reach E while keeping the cost minimal?
• Reformulate the OF to combine the minimized cost with the maximized capacity?

Importantly we do not want to run the model 128 times. We want to model to select the destinations j to open a facility and select the capacity f accordingly, to minimize the overall cost of supply and maximize the installed capacity. In our case,e it would also be very unlikely to open just one destination j to satisfy all demand E. Instead we would have multiple j with smaller f capacity that approach E when summed.

Answer 1

This is 'multi-objective optimisation'. Two possible ways to achieve this are outlined below.

First approach is to get a combined single objective function. This is easier if both terms are working in the same direction e.g. both are minimising terms. So for your 'constraint 3' try using a term in the objective for the shortfall relative to the demand, so the shortfall is something like:

Shortfall == E - mdl.sum(X[j,f]for j in J for f in F)

Then add the shortfall into the objective, and use some weighting factors for the two terms, e.g.:

w * Cost + (1-w) * Shortfall

Then if w is one, you are just minimising the cost, while if w is zero, you are just minimising the shortfall. Of course, if you use a value for the weighting between zero and one, then you will get a balance of the two objectives. You will need to pay careful attention to the value of the weighting split between your two terms.

A variation in this approach would be to give a much bigger weight to one term than the other, so that term dominates the objective. Then the solver will try to minimise that more important term (e.g. the shortfall), and the other term will help select the lower cost options for achieving that. In practice this often does NOT work as well as people expect - adding very large and very small terms in the objective can give rise to numerical issues in the solver, and often the real differences in the objective values of different solutions can get lost in the tolerances in the solver anyway. For example we have seen some people use relative weights of 1 million to one, while still using an optimality gap of 1e-6; in this case the second term effectively gets lost in the noise because many (perhaps very different) alternatives look almost the same to the solver and fall within the tolerances and so effectivley get ignored.

The second approach is 'lexical multi-objective' solving which is a little more complicated, but doesn't rely on some troublesome weighting factors. Effectively you need to solve your problem twice - once to find the maximum capacity that you can provide, and then fix that with a constraint in your second problem and minimise the cost of delivering that capacity.

In practice you might adjust this purist approach, and accept solutions in your second model that are close enough to achieving the maximum capacity. So for example you may fix the total capacity in your second model to be e.g. at least 99% of the calculated maximum capacity achievable from the first model. This reflects the cases where there are maybe only a few (expensive) ways to achieve the absolute maximum capacity, but there may be worthwhile savings if we explore solutions that are close to that maximum.

Note that there are several solvers that provide ready-built support for multi-objective models using this 'lexical' approach which may avoid you explicitly solving the model twice for each case.

Answer 2

You could try to use CPLEX multi objective feature in docplex.

See basic example in https://www.linkedin.com/pulse/making-optimization-simple-python-alex-fleischer/

from docplex.mp.model import Model

mdl = Model(name='buses')

nbbus50 = mdl.integer_var(name='nbBus50')
nbbus40 = mdl.integer_var(name='nbBus40')
nbbus30 = mdl.integer_var(name='nbBus30')

cost = mdl.continuous_var(name='cost')
co2emission = mdl.continuous_var(name='co2emission')

mdl.add_constraint(nbbus50*50+nbbus40*40 + nbbus30*30 >= 200, 'kids')
mdl.add_constraint(co2emission==nbbus50+nbbus40*1.1+nbbus30*1.2)
mdl.add_constraint(cost==nbbus40*500 + nbbus30*400+nbbus50*625)
                
sense="min"
exprs=[cost,co2emission]
priorities=[1,2]
weights=[1,1]
mdl.set_multi_objective(sense, exprs, priorities, weights, abstols=None, reltols=None, names=None)

mdl.solve(lex_mipgaps = [0.001, 0.05], log_output=True)

for v in mdl.iter_integer_vars():
    print(v," = ",v.solution_value)

print("The minimum cost is ",cost.solution_value);
print("CO2 emission is ",co2emission.solution_value);

'''
which gives

nbBus50  =  4.0
nbBus40  =  0
nbBus30  =  0
The minimum cost is  2500.0
CO2 emission is  4.0

'''

Answer 3

You might also consider a simpler API, namely Model.minimize_static_lex, to which you pass a list of expressions you want to minimize in a lexicographic ordering:

#mdl.set_multi_objective(sense, exprs, priorities, weights, abstols=None, reltols=None, names=None)
mdl.minimize_static_lex(exprs=[cost, co2emission])
mdl.solve(lex_mipgaps=[0.001, 0.05], log_output=True)