Originally posted by: giannil

Hello,

We have a problem with the creation of our integer problem.

Can anyone help us? You will find the question in the attached file

Thank you

Before answering I post the content of your docx file since this will make it easier to read this thread:

--- snip ---

Hello,

I am trying to make a model which gives me an optimal festival schedule. Right now I am trying to define this model as an IP.

For my first try, I created a variable Xijk , which is one if artist i is scheduled on podium j in timeslot k. I made some constraints to make sure every artist has a unique combination of podium and timeslot. So far everything went well.

As input data I have a matrix Cost(i)(j) in which the number of people is defined who want to see as well artist i as artist j. To calculate which schedule is optimal, I would like to make an objective function which minimizes the number of overlaps and the number of sequenceconflicts. Som y objective should be of this form:

Minimize: Cij*Oij*w1+ Cij*Sij*w2

Oij: 1, if artist i is in the same timeslot as artist j and 0 otherwise

Sij: 1, if artist j is in the next timeslot, but at a different stage as artist i and 0 otherwise

To define Oij, I would make a constraint like this:

∀ i,z ∈Artists, ∀ k ∈Timeslots: jXijk*jXzjk=Oiz

The same way for Sij:

∀ i,z ∈Artists, ∀ k ∈Timeslots: jXijk*lXzlk+1=Siz , with l different from j

Is this possible? Can CPlex solve this kind of problem, because I think the objective function will be of a quadratic form.

--- snap ---

To define O[i,j] = 1 if artist i and artist j are in the same slot you can do

forall k in Timeslots: 1 + O[i,j] >= sum(p in Podiums) X[i,p,k] + sum(p in Podiums) X[j,p,k]

Since there is a non-negative penalty on O[i,j] (namely C[i,j]) this will keep O[i,j] at zero unless both sums on the right-hand side are 1. Since an artist can play only one podium in a time slot, each of the sums on the right-hand side is less than or equal to 1 and is 1 if and only if the artist plays in timeslot k.

I think S[i,j] the constraints on S[i,j] can be stated similarly.

Whether your objective is quadratic depends on whether w1 and w2 are variables or data. What are they?

Originally posted by: giannil

Thank you for your answer.

I have also a question about this constraint : I tried to make the constraint concerning the sequence variable. Culex doesn't say there is something wrong, but if I run Cplex and I get a solution, the values of the sequence variable are not possible.

What is wrong with this constraint?

Thanks

The best way to debug things like this is to look at a solution vector and check why the constraint does not forbid this vector. That usually tells you why your constraint is not as strict as you thought it was.