How to choose between solvers

With PTV xTerritory Server you have to possibility to choose between a commercial and a free solver. This use case will outline the differences and capabilities of the available solvers and gives you all the information you need to choose the right solver for your problem.

Related Topics

The following topics might be relevant for this use case.

• How to configure territory algorithm profiles and solver

Terminology

solver

Solver is a collective term for special mathematical computer programs that can solve mathematical problems numerically. Input for a solver is a problem descriptions in a generic form and output is a calculated solution.

solution quality

Variable SolutionQuality (BASIC or HIGH) leads to variations in the quality of the results and the running time. Both methods are mathematically exact methods. That means that a valid solution exists, as soon as the permissible deviation is within a tolerance of the optimum.

location

Addresses of which the position cannot be altered (e.g. customers, drop of point of an order) or reference points of administrative territorial units (e.g. postcode areas).

territory

Planning result or input. Allocation of the locations to a common unit (e.g. operational area).Territories without a fixed territory center can also be called 'clusters'.

Benefits

Using this use case you will ...

• know which solvers can be used with PTV xServer.
• get an impression of the capabilities of the different solvers.
• have all the information you need to choose a solver for your use case.

Prerequisites

To use the commercial Gurobi solver in the PTV xTerritory Server, you will require a valid license for the Gurobi solver. This must be obtained independently from the PTV xTerritory server and configured like described in the use case How to configure the territory algorithm profile and solver.

If multiple PTV xTerritory server instances are configured, a Gurobi license will be required for each individual instance.

Concept

CBC - Free solver

The COIN-OR Branch and Cut solver(CBC) is an open-source mixed integer program (MIP) solver. CBC is an active open-source project led by John Forrest at www.coin-or.org.

Gurobi Optimiser - Commercial solver

The Gurobi Optimiser is a state-of-the-art solver for mathematical programming. The solvers in the Gurobi Optimiser were designed from the ground up to exploit modern architectures using the most advanced implementations of the latest algorithms.

Choosing the Solver

Both solvers using exact methods to solve the mathematically problem. Therefor it is expected that the solution quality for the purposes of compactness measure and imbalance is very similar in both solvers. . Whether a solution is "more beautiful" than the other, is as always in the eye of the beholder. But there is no tendency for one or another solver expected. Both solvers can handle a large amount of locations and territories, we tested them with up to 70000 locations and 180 territories.

In principle the running time and memory consumption counts for the selection of the solver.

Relevant for the estimation of the term is primarily the number locations and the number of territories which plays a not insignificant role.

Equal number of locations but different number of territories:

• The running time is roughly proportional.
• That twice as much territory does about twice as much maturity.

Equal number of territories but different number of locations:

• The running time behaves disproportionate.
• That means the greater the number territories, the more the number of locations has an impact on the run time.

Locations with same or different activities:

• A noticeable difference in running is only achieved with a large number locations.

Different tolerance of imbalance:

• The propagation time difference is relatively small but measurable in all tested scenarios.

Here are some benchmark figures for CBC solver. The test sets were executed on a Azure-VM with Windows Server 2012, 8 cores and 56 GB RAM.

The following parameter settings apply:

• solution quality: basic
• number of iterations: 5
• number of starts: 5

For even larger problems (eg. 70000 locations and 184 territories) is a running time less than one day only possible at the expense of sacrificing quality (fewer iterations and multiple starts). With Gurobi solver the performance is increased by a factor of 3-6.

You can calculate the estimated memory consumption with the following formula:

• Total memory consumption = Dima memory consumption + solver memory consumption

Dima memory consumption:

• Dima memory consumption = (number of locations) x (number of locations) x (8 bytes )

Solver memory consumption:

• Gurobi: flexible 4GB - 30GB takes as much as it gets, but also comes along with 4 GB RAM.
• CBC: 4-6 GB, depending on the problem. If it needs 6 GB, but only gets 4 GB, there's trouble.

Example:

• 50000 locations with CBC solver
• Total memory consumption = 50000 x 50000 x 8 byte + 6 GB = 24.62 GB RAM

Copyright © 2024 PTV Logistics GmbH All rights reserved. | Imprint