0

This is the result of implementing my very first model in CPLEX C++ and I am very much surprised how slow and poor the quality is. I belief that much of it can be avoided by a better formulation. Can anyone help me improve the code, please? Hints, ideas, thoughts ... everything is appreciated!

It is about scheduling exams within 5 days that have 2 timeslots each available. My input is the number of exams (first row first number) and conflicting exam pairs (first row second number) where I also know the number of students taking both exams(in the following rows -> exam1 exam2 #students taking both exams). The code you can find here and the instance here.

The constraints I am including are:

  1. each exams is scheduled exactly once
  2. conflicting exams cannot be scheduled at the very same period
  3. penalize if conflicting exams are scheduled on same day
  4. penalize if conflicting exams are scheduled on consecutive days
  5. penalize if conflicting exams are scheduled on adjacent periods over night

I have the feeling that something is even wrong in the formulation because I cannot imagine that the value of the objective value is that high. Does anyone see the flaw? I'm stuck.

The problem might be in the loop where I try to figure out whether a soft constraint is violated or not. There I am looping over days but probably I accidentally overwrite my variables all the time. Does anyone have an idea how to determine the binary variable indicating if the soft constraint is violated on any day (and of course it can happen only once but most probably it is not at the end).

Improve this question
4
  • When you say the model is slow, I guess you mean the solving performance? This sounds like small problem. How slow was the model to build and solve? When you say poor quality, are you referring to the generated solution? In what way is it poor quality? How big is your objective value? Commented Mar 20, 2016 at 21:11
  • The log reads "Root relaxation solution time = 0.05 sec. (38.16 ticks)", I guess that's the time needed to find the first feasible solution. Its objective value is 28722 (in the column Best Integer) and it does not get lower than 28608 and it should be more like 700 something Commented Mar 20, 2016 at 21:23
  • No. The root relaxation time is how long it took to solve the relaxed problem (ignoring integrality) at the root node. That would not normally be an integer feasible solution. Can you manually create a solution for comparison? Commented Mar 20, 2016 at 21:59
  • and if the very first entry in the node log says best integer, isn't the solution found by the relaxation integer? Or how can I interpret that? Commented Mar 21, 2016 at 8:27

1 Answer 1

Reset to default
2

Rather than debugging C++ code I just re-implemented the model using a modeling language (I believe that is quicker and a more pleasant way to spend a sunday evening).

(Note: updated after fixing bug). Here is my solution with a total penalty of 751:

enter image description here

You should be able to plug this into your code and verify the results.

Note: it took about 900 seconds on an old laptop to prove optimality with Cplex. If you want just a good solution, you can stop a little bit earlier:

enter image description here

(Blue line is the objective and the red line is the best possible bound). To get good performance I helped Cplex a little bit with setting branching priorities and using some options suggested by a tuning run.

Improve this answer
Sign up to request clarification or add additional context in comments.

11 Comments

that's impressive but I still do not understand where I forgot something or made it too complicated
Having a known optimal solution should make it a breeze to debug your code. Just plug in the solution (fix variables) and check the counts on the conflicts.
ok, fixing the variables gives me this large objective value ... so there is definitely a mistake in my code
What penalties did you include? I get a much higher number than you when I calculate it manually
@Yash It is the "lower bound" or best possible integer solution. When red line and blue line meet we can stop: we have proven no better solution can exist. As this is a MIP problem we cannot use Simplex directly (that is only for LP).
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.