UniTime / cpsolver

Local-search based solver of Constraint Satisfaction and Optimization Problems
http://www.cpsolver.org
GNU Lesser General Public License v3.0
60 stars 35 forks source link

Solver MPP mode #21

Closed ebracci closed 2 years ago

ebracci commented 3 years ago

Hi everyone,

I would like to know if there is the possibility (using some particular configuration in the cfg file) to build a solution starting from an initial partial solution WITHOUT changing the assignments already done in the input xml.

Thank you

tomas-muller commented 3 years ago

If the initial placement of a class cannot be changed, you can just leave the initial placement in the domain of the class. Similarly, if a class can be moved to a different room but not to a different time, you can just leave the one time in the domain in the class, together with the initial as well as the alternative rooms.

ebracci commented 3 years ago

Thank you for your reply!

So the only solution is to run the solver with a single domain for rooms, instructors and time as needed.

In this specific case, can the solver unassign the class?

I'm thinking about the case in which the assignment made of that particular class creates conflicts.

tomas-muller commented 3 years ago

That is not the only option. It is also possible to massively increase the penalization for assigning a different time and/or room to a class -- but the solver may still make a change in order to find a complete solution (all variables are assigned).

Yes, the solver can unassign the class. If there is only one possible placement (time and room) and you want to make sure the solver cannot unassign the class, you can mark it as committed (committed='true' on the lecture element). Also, in this case, make sure that the initial placement is also included in the current and best solutions (solution='true' and best='true' beside of initial='true').

If there is a hard conflict between initial solutions, one of them will be left unassigned even when the solution is committed (the solver will fail to assign the second class during the load).

You can always strive to have all variables assigned, otherwise, the solver will spend most of its time trying to find the complete solution instead of doing any optimization.

ebracci commented 3 years ago

Great, I understand

Referring to this data model https://www.unitime.org/uct_dataformat_v24.php, are the inital and best flags at the same level of committed i.e. in reference to the class or should they be inserted within the individual solution (i.e. classroom, instructor solutions)?

tomas-muller commented 3 years ago

The committed attribute is on the class element. The initial, best, and solution attributes (marking the initial, current, and best solution) are on the time, room, and instructor elements that are part of the initial, current, and best assignment.