Multiple Objectives vs One Objective

[J. Friedman]

I am solving a academic timetabling problem and the 0-1 integer program M is too big to be solved as a monolithic model. Fortunately,  a real schedule sort of splits into smaller schedules. Suppose g_1, g_2, ... g_n are groups of students who need the same courses. I define M_1 as the model involving scheduling only students in g_1, and M_k as the model involving students in G_k: = \union_{i \leq k} g_i.

In order to get Gurobi to solve the sequence of nested models (M_{i} < M_{i+1}) I biassed the objective. Let o_i be the normal objective for M_i where this objective guides M_i to find the solutions with the best physical properties (professors get their days off, courses are spread out over the week,...). Then I add a pretty strong (high weight) biased objective b_i  that says to look for a solution that is most similar the solution of the previous model, M_{i-1}.

Once the optimal to (M_i, b_i+o_i) is found, I remove b_i, freeze most variables of variables  M_i (using different slices) and  add many minor terms to o_i to find a better solution. For example, I only allow Monday and Friday classes to move, all else is frozen. Now after presolving M_i is now very small for each slice and I get nice improvements very fast.

Then I repeat the process for M_{i+1} until all students are scheduled.


The performance is 12-48 hours. And I really think this problem can be solved in 12-48 minutes. My question: if I rewrite this to use the multiple objective feature of Gurobi, should I see a great performance increase?

[Tobias Achterberg]

I doubt that you will get better performance out of the multi-objective approach.

First of all, with the multi-objective approach you would still solve the full
model M_n in all steps, except that the objective function is different in each
step of the multi-objective optimization. More precisely, in the first step you
would solve M_n with o_1. This is probably (much) easier than M_n with o_n,
because all the costs for scheduling g_2, ..., g_n will be zero, so presolving
will be pretty effective in reducing the model. Nevertheless, I guess that this
is still harder to solve than just M_1.

In the second step, the multi-objective approach would solve M_n with o_2,
subject to the additional constraint that o_1 should not degrade (too much) from
the optimal value of (M_n, o_1). This additional constraint will probably be a
pretty strong restriction and thus reduce the search space, but I doubt that it
will lead to many presolve reductions that would actually shrink the size of the
model to be optimized. Moreover, (M_n, o_2) will probably be again more
difficult to solve than (M_2, o_2) as in your version.

So, my conclusion is that your approach is already a pretty clever and problem
specific decomposition scheme, and I doubt that you will get something better
out of the generic multi-objective approach that Gurobi offers. But of course,
if it is easy for you to code up, it is still worth a try.


Regards,

Tobias