Originally posted by: Liesa

For my endwork, I have to develop a MIP model which assigns students to schools. Students are assigned according to 2 criteria: preference and distance. Each school has a certain capacity for which students that have a preference number lower than '3' can be assigned (+ by using lottery) and a capacity for which students that are living close to the school can be assigned. The capacities can change if the number of students that have a preference lower than '3' is lower than the capacity. A file with the model is attached.

p(k,s) = preference of student k for school s

x(k,s) = 1 if student k is assigned to school s

QUESTION:

If my objective function is the following: minimize sum(p(k,s)*x(k,s)) I do not find a solution.

If my objective function is the reverse: maximize sum(-p(k,s)*x(k,s)), I find a solution very quickly.

How is this possible?

Hi,

can you attach the full model ?

regards

This could be a side-effect of a heuristic but it is hard to tell without actually seeing your model or at least the log files for the two different solves. Could you show any of them?

Originally posted by: Liesadh

Here you go.

Thank you in advance!

LP file:

http://we.tl/RuGVQ4j3qw

What version of CPLEX do you use? I could not reproduce your problem here.

Are you sure you are flipping the objective function correctly? In your logs you can see for "maximize"

Root relaxation solution time = 8.39 sec. (2695.54 ticks)

Nodes Cuts/

Node Left   Objective IInf Best Integer Best Bound ItCnt Gap

   0    0  37099.6949 1224              37099.6949 9901

and for "minimize"

Root relaxation solution time = 214.38 sec. (42780.70 ticks)

Nodes Cuts/

Node Left   Objective IInf Best Integer Best Bound ItCnt Gap

   0    0   2888.6639 6151               2888.6639 23431

If the objective was correctly flipped and everything else in the model was the same than the initial dual bound in the minimization case should be -37099.6949, right? And that is what I get when I flip your objective by hand here.

For your maximization model I get an optimal objective value of 37082 (i.e. the initial dual bound is tight). So the optimal solution for the minimization should be -37082. However, that solution is cut off by the initial dual bound in the minimization log.

Can you please double check how you are flipping the objective? Or can you even show us how you do that?

Originally posted by: Liesadh

I'm sorry, that's right, I added a constant to it. In the previous maximization problem, I had: max. sum((10-preference(k,s))*x(k,s)).

The log file for the flipped objective function is added to this message. It found a feasible solution but the program stopped because out of memory.

I find it strange that Cplex can solve the problem much faster with the added constant..

I use Cplex Studio 12.5.1 (32 bit)

I could not reproduce your problem with 12.5.1 either. The solves with and without flipped objective are completely symmetric for me.

In the log file for the maximization and the updated log file for the minimization, you can see that the sizes of the models after presolve are different. This looks surprising at first glance. Could you export an LP in the second case as well and make sure the only difference is in the objective function?

If you don't add the constant in the min case or add the constant in the max case as well, do you get consistent behavior with and without flipped objective?

In general, adding a constant to the objective function will affect the relative gap termination criterion unless you set CPX_PARAM_EPGAP to 0. So it is not unexpected that performance may change. What comes as a surprise is a different size of the models after presolve for the min and the max model. Could you attach the min model here as well?

About the different behavior of the two min models (with and without constant). They both run out of memory, it may be random luck that one runs out of memory just after finding something feasible while the other runs out of memory right before that. At the root node, CPLEX runs several "background threads" to do things it deems useful. These threads grab memory as well and may have a (random) influence on when CPLEX runs out of memory. What happens if you set CPX_PARAM_AUXROOTTHREADS and/or CPX_PARAM_CUTPASS to -1? Do you get more consistent behavior between the two min solves? You may also want to set CPX_PARAM_MEMORYEMPHASIS for your model and take a look at the Running out of memory chapter in the documentation.

Originally posted by: Liesa

I think you have misunderstood me. I gave you the updated log file for the maximization problem. For clarity, here are all log files of the 4 possibilities (Max/Min and with/without a constant) + the log file with the different settings that you gave me. The sizes of the models after presolve are the same for the min (resp. max) models, so that's okay.

Actually, I forgot that a constant has influence on the relative gap. However, relatively spoken, the model still performs better with a constant. Furthermore the maximization model is much faster.

The different settings hadn't much impact, I think.

Thank you for all the effort!

LP files:

http://we.tl/izvQz77DiG