I am using CPLEX to benchmark some of my instances. Recently I was trying to force CPLEX to find the best feasible solution. To do so, I set the MIPEmphasis parameter to feasibility and increased the heuristic frequency. I also tried activating the Local Branching heuristic to improve the solution every time a new incumbent is found.

I'm using the CPLEX 12.5. The time limit was set to 2 hours. The number of threads was limited to 1.

What I noticed after multiple runs is that CPLEX doesn't find the same solution. Some runs are better than others.

Is that due to some randomness in CPLEX's heuristics? Is it due to the Local Branching?

Thank you.

asked 12 Nov '13, 04:36

Taha's gravatar image

Taha
557
accept rate: 0%

edited 12 Nov '13, 05:33

2

Following the answer of Xavier, I found out that the clock time limit (in CPLEX TiLim) isn't a good measure of comparison between two runs. Instead, using the ticks limit (in CPLEX DetTiLim) was effective for me as I could have EXACTLY the same time in different runs whether the machine is loaded or not.

Nevertheless, converting between ticks and seconds is difficult. It changes from one machine to another. The user should try CPLEX on a free machine (what is a free machine?) to determine the number of ticks in a second, and then take that number as a converting reference for the same machine.

Here is an interesting article tackling this issue.

What should be noted and highlighted here though is that the random seed doesn't change from one run to another in CPLEX. It remains the same for all the runs. It is possible to change it using the new parameter RandomSeed (added in recent versions, I'm not sure which one). Changing it caused my program to have different path and thus, a different amount of ticks.

(19 Nov '13, 09:35) Taha

I will suppose that the runs happen on the same machine...

CPLEX's behavior is deterministic by default, but here you specified a 'time limit' of 2 hours. Unless you specifically used DetTiLim (CPX_PARAM_DETTILIM) instead of TiLim (CPX_PARAM_TILIM), a time limit is measured against wall-clock time, and is thus not deterministic. This is sufficient to explain why not all runs give you the same results. Even if the machine is idle before launching CPLEX and you are only using 1 thread, there is no guarantee that two runs will be the same if you are using CPX_PARAM_TILIM.

Note that CPX_PARAM_DETTILIM uses ticks rather than seconds, miliseconds, or other such wall-clock time units...

link

answered 12 Nov '13, 05:18

Xavier%20Nodet's gravatar image

Xavier Nodet
463
accept rate: 100%

edited 12 Nov '13, 06:37

Thank you Xavier for specifying the differences. I didn't know that :)

I edited the question to give more details.

(12 Nov '13, 05:25) Taha

I understand that the difference between the two parameters, but I think that they are the same when CPLEX is launched on a free machine (i.e. no other processes running with CPLEX). When I don't use the default settings, I obtain exactly the same results. That's what made me doubt the randomness in heuristics.

(12 Nov '13, 05:32) Taha
1

As long as you use TiLim, there's no guarantee... Does this reproduce with DetTiLim? "When I don't use the default settings [...]"? Did you mean the reverse?

(12 Nov '13, 06:39) Xavier Nodet

I have to check with the DetTiLim. Yes, I meant when I use the default settings, I get the same results.

(12 Nov '13, 09:07) Taha
2

"No other processes running with CPLEX" presumably means no other user-initiated processes. The operating system will still be running. On a typical PC, any antivirus software will be running, various scheduled jobs will run when their due date arrives (checks for software updates, for instance), ...

(12 Nov '13, 17:02) Paul Rubin ♦♦

Thank you Paul. I have indeed checked that. Two similar runs on a "free" PC don't give the same clock time.

(19 Nov '13, 09:39) Taha

@Xavier: the seed is unchanged in CPLEX, I guess that's the source of determinism. Am I wrong?

(19 Nov '13, 10:06) Taha
showing 5 of 7 show 2 more comments
Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×191
×71
×18

Asked: 12 Nov '13, 04:36

Seen: 2,404 times

Last updated: 19 Nov '13, 11:51

OR-Exchange! Your site for questions, answers, and announcements about operations research.