A carregar...
Publicação
From a MILP Model to Solve the Weighted MAX-CSP to a MILP Model to Generate University Timetables with Teacher and Student Preferences
| Nome: | Descrição: | Tamanho: | Formato: | |
|---|---|---|---|---|
| 182.73 KB | Adobe PDF |
Autores
Orientador(es)
Resumo(s)
The maximal constraint satisfaction problem (MAX-CSP) is an over constrained optimization problem where we want to maximize the number of constraints satisfied or equivalently minimize the number of unsatisfied constraints and where all constraints can be unsatisfied or relaxed. In the weighted MAX-CSP we also associate a weight to each constraint and we minimize the sum of weights associated to unsatisfied or relaxed constraints. We present a general MILP model to solve this class of problems and then apply it to an over constrained problem constituted by four linear equations of two variables. We showed that the MILP model obtains the solution of the system of the two equations to which we attributed a higher weight and so they were not relaxed or removed from the MILP model. To our knowledge our work is the first proposal of solution of the weighted MAX-CSP using a MILP model and the Cplex solver. Previous proposals were based in dedicated solvers and logic programming. Then we adapt this MILP model to solve university timetabling problems that are a variant of the weighted MAX-CSP where there are a set of constraints that cannot be unsatisfied or relaxed, the hard constraints. The remaining constraints that can be unsatisfied or relaxed are called soft constraints. To each soft constraint set is associated a weight that reflect the different priorities to satisfy them. We associate to each set of soft constraints an indexed binary variable that will control the relaxation of soft constraints. Finally we apply this MILP model to a small instance of the university timetabling problem with four different preferences of teachers and students. Due to the big runtimes, in the near future we plan to implement our MILP Model with the Prolog language.
Descrição
Palavras-chave
Artificial Intelligence Operations Research Optimization Problems Mathematical Programming Linear Programming MILP Model to Generate University Timetables.