Hi Christiane,
if I understand you correctly, you suggest something like this:
from docplex.cp import model as cp
model = cp.CpoModel()
jobs = [cp.interval_var(size=5) for _ in range(10)]
model.add(cp.no_overlap(jobs))
max_end_times = cp.max(cp.end_of(job) for job in jobs)
sum_end_times = cp.sum(cp.end_of(job) for job in jobs)
obj1 = cp.minimize(max_end_times)
obj2 = cp.minimize(sum_end_times)
model.add(obj1)
sol1 = model.solve(TimeLimit=1)
d = 1
model.add(max_end_times <= sol1.get_objective_values()[0] * d)
model.remove(obj1)
model.add(obj2)
model.set_starting_point(sol1.get_solution())
sol2 = model.solve(TimeLimit=1)
If that is what you had in mind, then it seems to work in principle. However, I see some downsides to that. It's rather complicated to implement and more importantly, the optimization has to be split into phases. In each, CPO only focuses on one of the criteria instead of all of them simultaneously. If my understanding is correct this would seriously slow down the optimization process. Lastly, better solutions to previous objectives not part of the current model are ignored. All this is elegantly avoided by minimize_static_lex. Too bad it has no relaxation parameter.
I'd hoped for a simpler solution, but if that's not the case when I have to reconsider my approach to the problem.
Thanks
Sebastian
------------------------------
Sebastian Bayer
------------------------------
Original Message:
Sent: Wed July 21, 2021 11:58 AM
From: Christiane Bracchi
Subject: Relaxed Lexicographic Optimization
Hello Sebastian,
A way to improve your first proposal is using StartingPoint.
So you would have something like:
minimize f1get the value F1 (objective) and solution S (some variables)add a constraint f1 <= F1 * d (with d >=1 )add starting point S (set_starting_point(S))minimize f2
See set_starting_point.
I hope this helps,
------------------------------
Christiane Bracchi
Original Message:
Sent: Wed July 21, 2021 01:23 AM
From: Sebastian Bayer
Subject: Relaxed Lexicographic Optimization
Dear Christiane,
many thanks for your swift reply!
I'm in a situation where I have a clear preference between two objectives, which indicates the usage of the lexicographic method.
However, I'm willing to give up "a little" (say 1%) of the primary goal to gain in the secondary objective. This is e.g. interesting when the Pareto front flattens out. I could of course do this by computing the whole Pareto front and selecting the weighting parameter coinciding with that idea of giving up something in one criterion, but the relaxed version of the lexicographic would be so much more convenient. Moreover, the goal is to have this in some automated solution and not in a one-time analysis.
Regards
Sebastian
------------------------------
Sebastian Bayer
Original Message:
Sent: Tue July 20, 2021 11:48 AM
From: Christiane Bracchi
Subject: Relaxed Lexicographic Optimization
Hello Sebastian,
Sure what you suggested is possible, but why don't use minimize_static_lex
?
What is your need which wouldn't be addressed by multi-criteria objectives?
Regards,
------------------------------
Christiane Bracchi
Original Message:
Sent: Tue July 20, 2021 09:51 AM
From: Sebastian Bayer
Subject: Relaxed Lexicographic Optimization
Dear all,
I'm exploring alternatives the weighted sum approach we're currently using for multi-objective optimization. I realize that lexicographic optimization is possible in CPO using the minimize_static_lex
method.
I wonder if it is possible to implement a relaxed version of the lexicographic method:
1. min f1 => F12. min f2 s.t. f1 <= F1 * d
where f1, f2 are objective functions and F1 is the minimal value obtained in the first step. The parameter d >= 1 would then relax the constraint.
Is that possible in CPO?
------------------------------
Sebastian Bayer
------------------------------
#DecisionOptimization