Multi-objective optimization with CP-Sat

[ghost]

Hi!

This may come across as a newbie question, but is it possible to have multiple objective functions and set a priority or preference over them?

Right now I am manually adding a coefficient to each objective:
model.Minimize(objective1+10000*objective2)

But this doesn't seem right as the order of magnitude of each objective may be different.

[lperron]

No you cannot directly What I would do: solve with the first objective record the solution change the objective to the second objective add a constraint s.t. the first objective is close to the optimal solution of the first solve add solution hinting to the model to start from the optimal solution of the first solve resolve Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mar. 11 juin 2019 à 15:40, Xiang Chen <notifications@github.com> a écrit :

…

Hi! This may come across as a newbie question, but is it possible to have multiple objective functions and set a priority or preference over them? Right now I am manually adding a coefficient to each objective: model.Minimize(objective1+10000*objective2) But this doesn't seem right as the order of magnitude of each objective may be different. — You are receiving this because you are subscribed to this thread. Reply to this email directly, view it on GitHub <#1344?email_source=notifications&email_token=ACUPL3LMFYPHAOQKCMHG72TPZ6TNPA5CNFSM4HW6OWE2YY3PNVWWK3TUL52HS4DFUVEXG43VMWVGG33NNVSW45C7NFSM4GY2ENXQ>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACUPL3PTB5MNO6QJADGWNHTPZ6TNPANCNFSM4HW6OWEQ> .

[ghost]

Thank you very much!

Didn't know about solution hinting, maybe my problem should also be broken down to make better use of this feature.

Will use the code that you posted in another issue to do this:

model.Proto().solution_hint.Clear()
for i in range(len(model.Proto().variables)):
    model.Proto().solution_hint.vars.append(i)
    model.Proto().solution_hint.values.append(solver.ResponseProto().solution[i])

[lperron]

yes, there is now a nice example for it: https://github.com/google/or-tools/blob/master/ortools/sat/samples/solution_hinting_sample_sat.py Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mar. 11 juin 2019 à 16:06, Xiang Chen <notifications@github.com> a écrit :

…

Closed #1344 <#1344>. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#1344?email_source=notifications&email_token=ACUPL3OJTXKNSGXDWFHRVGLPZ6WNHA5CNFSM4HW6OWE2YY3PNVWWK3TUL52HS4DFWZEXG43VMVCXMZLOORHG65DJMZUWGYLUNFXW5KTDN5WW2ZLOORPWSZGOR5HF6EI#event-2404278033>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACUPL3P7IINYBIY2ESNREP3PZ6WNHANCNFSM4HW6OWEQ> .

[ghost]

Thanks!

I only knew about the examples in https://github.com/google/or-tools/tree/master/examples, will also keep an eye on https://github.com/google/or-tools/tree/master/ortools/sat/samples from now on.

[lperron]

Yes, I am adding new examples when I see the need. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le mar. 11 juin 2019 à 16:46, Xiang Chen <notifications@github.com> a écrit :

…

Thanks! I only knew about the examples in https://github.com/google/or-tools/tree/master/examples, will also keep an eye on https://github.com/google/or-tools/tree/master/ortools/sat/samples from now on. — You are receiving this because you commented. Reply to this email directly, view it on GitHub <#1344?email_source=notifications&email_token=ACUPL3KV73OIL3ZHTOY4JKTPZ63EVA5CNFSM4HW6OWE2YY3PNVWWK3TUL52HS4DFVREXG43VMVBW63LNMVXHJKTDN5WW2ZLOORPWSZGODXNL72Y#issuecomment-500875243>, or mute the thread <https://github.com/notifications/unsubscribe-auth/ACUPL3I5ZNVH2IUKAKVJTTDPZ63EVANCNFSM4HW6OWEQ> .

[philippe3263]

Hi!

This may come across as a newbie question, but is it possible to have multiple objective functions and set a priority or preference over them?

Right now I am manually adding a coefficient to each objective:
model.Minimize(objective1+10000*objective2)

But this doesn't seem right as the order of magnitude of each objective may be different.

here a two step approach

https://github.com/philippe3263/ORTools_Visual_Studio

file : JS_with_SAT_And_Two_Objective.cpp

not a good solution but acceptable avoiding objective function defined with a sum of objectives

[ghost]

No you cannot directly What I would do: solve with the first objective record the solution change the objective to the second objective add a constraint s.t. the first objective is close to the optimal solution of the first solve add solution hinting to the model to start from the optimal solution of the first solve resolve Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00

@lperron, how do I keep the first objective close to the optimal?

Just a model.add(obj < x), where x is a value that I calculate? Is there any other way?

Thanks,
Ciprian

[lperron]

This is the way. Laurent Perron | Operations Research | lperron@google.com | (33) 1 42 68 53 00 Le lun. 15 juin 2020 à 10:51, Ciprian Pintilei <notifications@github.com> a écrit :

…

No you cannot directly What I would do: solve with the first objective record the solution change the objective to the second objective add a constraint s.t. the first objective is close to the optimal solution of the first solve add solution hinting to the model to start from the optimal solution of the first solve resolve Laurent Perron | Operations Research | ***@***.*** | (33) 1 42 68 53 00 @lperron <https://github.com/lperron>, how do I keep the first objective close to the optimal? Just a model.add(obj < x), where x is a value that I calculate? Is there any other way? Thanks, Ciprian — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#1344 (comment)>, or unsubscribe <https://github.com/notifications/unsubscribe-auth/ACUPL3NRIFH7WJAYLNXFKMDRWXOK3ANCNFSM4HW6OWEQ> .

[ghost]

Thank you for showing me the way 🙇