or-tools TSP earlier termination at poor solution - Heuristic settings documentation

[smile-on]

Let me clarify what do I mean by "poor". On small graph of 50 nodes search terminates automatically in fraction of a second resulting path ~ 4% below optimal. I need to improve quality of solution and can afford bigger search time but can't see how to configure that.

1) The predefined traide-off problem, some settings in the library rush to stop search. "User manual" 9.2.11.5. pg 329 says: You can force the RL to return proven optimal solutions but the RL wasn’t coded with exact solutions and procedures in mind. Any examples on how longer search can be "forced" to shift time/quality traide-off?

2) I am using java wrapper for or-tools and my set of options are limited, my best guess was trying different FirstSolutionStrategy settings. The AUTOMATIC option gave me -4% solution, most others failed futher down upto -10% the best one I found was PATH_MOST_CONSTRAINED_ARC still about -1% on 50 node graph and less than a second. The user manual does not listed those options. Is there a place were search choises behind those settings are described?

[Driss Lahlou]

Hi,

1) The predefined traide-off problem, some settings in the library rush to stop search. "User manual" 9.2.11.5. pg 329 says: You can force the RL to return proven optimal solutions but the RL wasn’t coded with exact solutions and procedures in mind. Any examples on how longer search can be "forced" to shift time/quality traide-off?

 

To make the solver look for the optimal solution, you have to set the use_depth_first_search parameter to true. This will dramatically increase the resolution time because the solver uses depth-first search rather than local search. In C++, you can set this parameter like so :

parameters.set_use_depth_first_search(true);

2) I am using java wrapper for or-tools and my set of options are limited, my best guess was trying different FirstSolutionStrategy settings. The AUTOMATIC option gave me -4% solution, most others failed futher down upto -10% the best one I found was PATH_MOST_CONSTRAINED_ARC still about -1% on 50 node graph and less than a second. The user manual does not listed those options. Is there a place were search choises behind those settings are described?

 

 You can find those parameters in routing_parameters.proto.

I hope this helps.

Regards,

--
You received this message because you are subscribed to the Google Groups "or-tools-discuss" group.
To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

--

driss

[Driss Lahlou]

Addendum:

To get better solutions, you can set local_search_metaheuristic to GUIDED_LOCAL_SEARCH instead of AUTOMATIC, then you should set a search time limit because, in this case, the solver may take a long time before it stops.

You can refer to this link for more details about guided local search and how it can improve the solution.

Regards, 

--

driss

[smile-on]

Thank you, Driss. The link on routing_enums.proto code is exactly what I need. Unfortunately proto buffer compiler + SWIG process strips off comments and makes code unreadable in java wrappers and fornovice like me it was not obvious were to look. Yes, GUIDED_LOCAL_SEARCH metaheuristic with PATH_MOST_CONSTRAINED_ARC initial solution strategy work the best for my problem.

Hi,

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

driss

--

driss

[Driss Lahlou]

You are welcome.

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discuss+unsubscribe@googlegroups.com.

[Ahmed Maher]

Does setting use_depth_first_search to true guarantee finding the optimal solution? In my case, I am almost certain it didn't. If not, then is there any way to get an optimal solution or even an exact value for what the optimal solution would have?

Here is the problem description:

• My problem is a pickup and delivery problem without demand/capacity or even time windows, but with different start locations for vehicles and an arbitrary end location that has zero cost to get to.
  
• The only cost I set is a global span cost on the time dimension with a cost coefficient of 100, and I used guided local search as a meta heuristic without setting any limitation.
  

On trying an instance with 50 pairs of pickup/delivery and 16 vehicles, it took it 22mins to get to a solution worse than my initial solution of just using all vehicles. I am saying worse because the model itself printed a lower value for my initial assignment than its assignment (I didn't use SolveFromAssignmentWithParameters; I was just testing how it would perform vs my solution). Thanks in advance.  

Hi,

To unsubscribe from this group and stop receiving emails from it, send an email to or-tools-discu...@googlegroups.com.

For more options, visit https://groups.google.com/d/optout.

--

driss

[Asmit Basu.]

I had the same problem with 15 nodes. I used GUIDED_LOCAL_SEARCH and SIMULATED_ANNEALING but they took for over. I had a time constraint of 2 minutes.
What I did was a poor hack but will give you a sub-optimal solution which is close to the global optimum. 
I set all parameters to AUTOMATIC I looped through all my nodes and selected each one as depot. The one with the minimum path was close to the optimum solution. 
Again, this is a nasty engineering hack and should only be done when you are bound by a time constraint.