Originally posted by: SystemAdmin

[alysson said:]

Dear all,

I am really puzzled with the following:

I have an IP model. ( http://www.icmc.usp.br/~alysson/files/share/sol21.lp ) . If I solve this model (I am using Cplex 11.2, interative optimizer, under Ubuntu ), I obtain an "optimal" integer solution with cost 23 ( http://www.icmc.usp.br/~alysson/files/share/SolutionUsingCplexWithCost23.txt ).

HOWEVER, I know of a solution with cost 21 ( http://www.icmc.usp.br/~alysson/files/share/sol21.mst ). Indeed, if I pass this solution to CPLEX as an mst file, Cplex starts using it as the "Best Integer found" ( http://www.icmc.usp.br/~alysson/files/share/ReadingSolutioWithfCost21.txt ).

Am I missing anything ? Any help is appreciated,

Alysson

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[prubin said:]

I verified this with CPLEX 11.0 (also on Ubuntu).  There are two ways (that I found) to get CPLEX to produce a correct solution (objective = 21) without the hot start:  turn off the presolver; or crank up the simplex feasibility tolerance (1e-9 worked for me).  Turning off the presolver seems to be the faster option.  (Disclaimer:  In both instances, I aborted the run after it found an integer-feasible solution with value 21 but before it exhausted the search tree, so it's possible one or the other option might have led to problems down the road.)

I ran into a similar problem a while back, with a similar looking MIP model (mine was a set covering problem), in which the symmetry reduction constraints added by CPLEX cut off the optimal solution.  In this case, turning off the symmetry reductions does not help, but it looks like one of the reductions done by the presolver is causing problems.  I'll alert someone in IBM's CPLEX unit about your post; they'll probably want to test your model to see what's going wrong.

/Paul

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[alysson said:]

Dear Dr. Rubin,

Thank you for your prompt (as usual) answer! Both ways you suggested worked here as well (CPLEX 11.2). I am really looking forward to hear more about this from people from CPLEX. In the meantime, some additional information:

- My problem is sort of a makespan minimization with precedence constraints. The time to execute each task x at each machine depends on the worker y assigned to the machine.

- If I change the last set of constraints

x_1 + x_2 + ... x_n \leq n*y

for their disaggregated form:

x_i \leq y  (for all i),

then CPLEX finds the optimal solution.


- I asked a friend to run the example on his CPLEX 10.1.1 installation and he got the correct answer (21).


Thank you again!

Alysson

#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[EdKlotz said:]

I have an IP model. ( http://www.icmc.usp.br/~alysson/files/share/sol21.lp ) . If I solve this model (I am using Cplex 11.2, interative optimizer, under Ubuntu ), I obtain an "optimal" integer solution with cost 23 ( http://www.icmc.usp.br/~alysson/files/share/SolutionUsingCplexWithCost23.txt ).


I just ran CPLEX 11.2 with defaults on Fedora Core 4 Linux (I don't have any machines running
Ubuntu), and it found the solution with objective
21.  Looking at the output in SolutionUsingCplexWithCost23.txt, you appear to be running
defaults as well, but I see one line that suggests otherwise:

Repeating presolve.

Typically, CPLEX doesn't repeat the presolve by default, and in my default run it did not do so.
Did you turn on the repeat presolve parameter or set some other non default settings?  If so,
try just running with defaults and see what happens.  If you did not set any non default parameters,
try explicitly turning the repeat presolve parameter off explicitly:

CPLEX>  set pre repeatpresolve 0

Tell us what happens.    I did try turning this parameter on, but I still got the solution of 21.
Numerically your model looks pretty reasonable, so this doesn't look like some sort of numerical
instability or ill conditioning issue. 

                                                                                                      Ed


#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[alysson said:]

Thanks for your answer, Dr. Klotz.

Indeed, I used default parameters. In particular, the repeatpresolve was set at -1 (automatic).

As you suggested, I forced the repeatpresolve at zero and re-run the test, but still got the same answer: http://www.icmc.usp.br/~alysson/files/share/repeatPreSolveAtZero.txt

Alysson
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[alysson said:]

This can be completely unrelated, but since it is happening on the same installation, I decided to put here:

While solving another model ( http://www.icmc.usp.br/~alysson/files/share/negativeTime.lp ) , another curious error appears: at a given point (around 40 minutes of simulation), CPLEX switchs the sign of the elapsed time. This way, no stopping criterium based on time works (a negative time is always less than any set time limit).

[i] Elapsed time = -1974.64 sec. (tree size = 58.66 MB, solutions = 6)
798100 111289    infeasible            18.0000      17.0000 30851562    5.56%
798200 111285      17.0000    8      18.0000      17.0000 30855588    5.56%
798300 111285      17.0000    10      18.0000      17.0000 30859655    5.56%
798400 111288      17.0000    4      18.0000      17.0000 30862781    5.56%
[/i]


I wonder if it can be a problem of OUR installation. Again, I am running CPLEX 11.2 on a dual-core processor with Ubuntu. 

Alysson


#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[alysson said:]

The complete log file for the simulation mentioned above can be found here:

http://www.icmc.usp.br/~alysson/files/share/negativeTime.log

The problem happens around time 2145s.
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[alysson said:]

Below is some input from the sci.op-research forum. Indeed there are some big-M LHS constants and they seem to be causing the problem. I now wonder about the negative time question.


------
Instead of tinkering with tolerances I would suggest to reduce the
size of your big-M constants. E.g. replace the values you use (100000)
by 10000. Large Big-M constants can cause quite a few probems.

----------------------------------------------------------------
Erwin Kalvelagen
Amsterdam Optimization Modeling Group
erwin.kalvela...@gmail.com
http://amsterdamoptimization.com
----------------------------------------------------------------
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[EdKlotz said:]

Below is some input from the sci.op-research forum. Indeed there are some big-M LHS constants and they seem to be causing the problem. I now wonder about the negative time question.


------
Instead of tinkering with tolerances I would suggest to reduce the
size of your big-M constants. E.g. replace the values you use (100000)
by 10000. Large Big-M constants can cause quite a few probems.

----------------------------------------------------------------

Reducing the size of the big M constraints as much as possible without compromising
the meaning of the model is always a good idea, although values of 100000
are not exceptionally large. 

Regarding the negative timings, Ubuntu Linux is not one of the officially supported CPLEX platforms,
so I don't have much help to offer.  It could involve the installation, or it could involve some
issue with the Linux kernel Ubuntu uses.  CPLEX measures time by making system calls, so
this output probably involves bogus values in the system calls.  You could try working around
the problem by setting CPLEX's clocktype parameter to 2 to use wall clock time instead of
CPU time, as the latter is the default under Linux.

I checked for any other such reports of negative time on any operating system, but I did not
find anything. 
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[alysson said:]

Dear Dr. Klotz,

Thank you again for your answer.

I will ask the technical staff of our department to change the linux distribution on the CPLEX machines. Fedora Core 4 seems to be an option. Does ILOG recommend any particular distribution ?

(This will need to wait a bit cause right now there are some students running final tests for their thesis, but I will post the results I obtain on the new installation here, as soon as they are available.)

Thanks again!

Alysson
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[EdKlotz said:]

Dear Dr. Klotz,

Thank you again for your answer.

I will ask the technical staff of our department to change the linux distribution on the CPLEX machines. Fedora Core 4 seems to be an option. Does ILOG recommend any particular distribution ?

(This will need to wait a bit cause right now there are some students running final tests for their thesis, but I will post the results I obtain on the new installation here, as soon as they are available.)

Thanks again!

Alysson

http://www.ilog.com/products/cplex/product/platforms.cfm

contains a list of officially supported platforms for 11.2

Machine: x86
OS: Debian 4.0 Red Hat Enterprise Linux 5.0,
SUSE Linux Enterprise Server 10
C++ compiler: g++ 4.1
Java: JDK 5.0, 6.0 

Fedora Core should be fine, but ideally you should select from one of the above.

Also, regarding the sol21.lp file associated with this thread, I found that setting
CPLEX's probing parameter to its most aggressive level of 3 significantly reduced the
run time to optimality.  More generally, on fairly difficult models with only a modest
number of binary variables, this non default parameter setting often helps.




#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[alysson said:]

Thank you again for the answer. I will sugest the installation of Red Hat and, if we cannot get it, some version of Fedora.

Concerning the suggestion about the parameters, thank you again. I will make some tests on my set of instances.

Best regards,

Alysson
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[plr said:]

Hi, all.

I also have the problem of getting a negative elapsed time with my model ( http://www.cs.nott.ac.uk/~plr/negativeTime2.lp ). It only happens with specific instances, not all of them.
I am running CPLEX 11.2.0 on CentOS 5.3, which is derivative from Red Hat Enterprise 5.
I will try to run it on a Debian machine to see if the same problem occurs and post the results here.

Cheers,
Pedro
#CPLEXOptimizers
#DecisionOptimization

Originally posted by: SystemAdmin

[notdarkyet said:]

I tested your problem under openSuSE x64 with CPLEX 11.2.1 and a solution with value 21 is found even when turning on presolve repeat and all cuts set to aggressively. So the cutoff of the optimal solution doesn't occur with this OS.
But it takes quite a lot of nodes to prove optimality, I interrupted the run at
666600 50174      20.8571    12      21.0000      20.8571 13001274    0.68%

With a drastically reduced big-M (to 33), probing level 3, cuts selectively set to 2 and mip emphasis 3 the problem is solved to optimality in short time (though it takes more nodes to find the solution with 21 than with default params):
      0    0      10.5417  205      55.0000      Cuts: 92    20049  80.83%
      0    0      10.5417  208      55.0000      Cuts: 93    20277  80.83%
*    0+    0                          31.0000      10.5417    20277  65.99%
      0    2      11.0000  174      31.0000      11.0000    20277  64.52%
Elapsed time =  13.85 sec. (tree size =  0.00 MB, solutions = 3)
    100    43      21.7895    42      31.0000      13.0000    68964  58.06%
*  140+  59                          29.0000      14.0000    88280  51.72%
*  160+  66                          24.0000      15.0000    95661  37.50%
    200    62      17.0000    44      24.0000      17.0000  102955  29.17%
*  230+  67                          23.0000      17.0000  111843  26.09%
    300    84      18.0000    40      23.0000      18.0000  136399  21.74%
*  340+  59                          22.0000      18.0000  147523  18.18%
*  360+    0                          21.0000      21.0000  151129    0.00%

GUB cover cuts applied:  83
Clique cuts applied:  160
Cover cuts applied:  129
Implied bound cuts applied:  2
Mixed integer rounding cuts applied:  159
Zero-half cuts applied:  1

Solution pool: 8 solutions saved.

MIP - Integer optimal solution:  Objective =  2.1000000000e+01
Solution time =  50.86 sec.  Iterations = 151129  Nodes = 360


The negative time measurement occured to me, too - under Ubuntu. I did not observe this under SuSE, so there seems to be a flaw in the time measuring system calls of Ubuntu.
A negative time looks strange, though we all would be happy if problems were solved before we stated them!
Ralf
#CPLEXOptimizers
#DecisionOptimization