Changes between Version 3 and Version 4 of Documentation/Reference/ExactOptimization


Ignore:
Timestamp:
01/31/19 15:45:47 (3 months ago)
Author:
ddorfmei
Comment:

--

Legend:

Unmodified
Added
Removed
Modified
  • Documentation/Reference/ExactOptimization

    v3 v4  
    44== Google OR-Tools ==
    55
    6 According to Google, "[https://developers.google.com/optimization/ OR-Tools] is an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming." OR-Tools are available for C++, Python, Java and .NET, the latter API can be used in HeuristicLab.
     6According to Google, "[https://developers.google.com/optimization/ OR-Tools] is an open source software suite for optimization, tuned for tackling the world's toughest problems in vehicle routing, flows, integer and linear programming, and constraint programming." OR-Tools is available for C++, Python, Java and .NET, the latter API can be used in HeuristicLab.
    77
    88OR-Tools includes solvers for
     
    1313 * Network Flows.
    1414
    15 For a complete overview, see https://developers.google.com/optimization/introduction/overview. You can use all solvers in HeuristicLab, just create a C# Script and make sure the [https://aka.ms/vs/15/release/VC_redist.x64.exe Microsoft Visual C++ 2017 Redistributable (x64)] is installed. Note that most linear and mixed-integer solvers must be installed (and licensed) separately, see the [#Mixed-IntegerLinearProgrammingMIPMILP next section] for details. The `HeuristicLab.OrTools` plugin is currently only available on 64-bit Windows.
     15For a complete overview, see https://developers.google.com/optimization/introduction/overview. You can use all solvers in HeuristicLab, just create a C# Script and make sure the [https://aka.ms/vs/15/release/VC_redist.x64.exe Microsoft Visual C++ 2017 Redistributable (x64)] is installed. Note that most linear and mixed-integer solvers must be installed (and licensed) separately, see the [#Mixed-IntegerLinearProgrammingMIPMILP next section] for details. The `HeuristicLab.OrTools` plugin is currently available only on 64-bit Windows.
    1616
    1717== Mixed-Integer (Linear) Programming (MIP, MILP) ==
    1818
    19 OR-Tools contains a [https://developers.google.com/optimization/reference/linear_solver/linear_solver/ linear solver wrapper] that can be used to define a MIP model once and solve it with a range of MIP solvers. Some solvers are already built into OR-Tools (BOP, Cbc, Clp, Glop) but for most solvers OR-Tools have to be built from source code, this version then has a dependency on the external solver. HeurisicLab includes a custom version of OR-Tools that allows users to simply install additional solvers without depending on them. Download the solvers here, they are free for academic use:
     19OR-Tools contains a [https://developers.google.com/optimization/reference/linear_solver/linear_solver/ linear solver wrapper] that can be used to define a MIP model once and solve it with a range of MIP solvers. Some solvers are already built into OR-Tools (BOP, Cbc, Clp, Glop) but for most solvers OR-Tools have to be built from source code, this version then has a dependency on the external solver. HeuristicLab includes a custom version of OR-Tools that allows users to simply install additional solvers without depending on them. Download the solvers here, they are free for academic use:
    2020 * [https://ibm.onthehub.com/WebStore/ProductSearchOfferingList.aspx?srch=ilog%20cplex CPLEX],
    2121 * [http://www.gurobi.com/downloads/download-center Gurobi],
     
    2323 * [https://scip.zib.de/index.php#download SCIP].
    2424
    25 Make sure that the solver you install is added to the environment variable `Path` and the `LibraryName` property of the solver in the Algorithm view is set to the correct name of the solver DLL (e.g. `cplex1280.dll` for version 12.8.0 of CPLEX). The default values for the solver DLLs can be set in the configuration file of HeuristicLab. Note that most solvers offer to change the `ProblemType` property to `LinearProgramming`, the solver then solves the linear programming relaxation of your model (all integer constraints are removed).
    26 
    27 [[Image(MixedIntegerLinearProgramming.png)]]
    28 
    29 For a general introduction to MIP and a simple model implemented using the linear solver wrapper, see https://developers.google.com/optimization/mip/integer_opt. For further examples demonstrating more advanced usage of the linear solver wrapper using the C# API, see https://github.com/google/or-tools/tree/master/examples/dotnet.
    30 
    31 The `HeuristicLab.ExactOptimization` plugin provides a GUI for MIP, just create a new ''Mixed-Integer Linear Programming (LP, MIP)'' algorithm, found under ''Algorithms'', ''Exact''. You can either load your model from a file (MPS, Google OR-Tools Protocol Buffers files) or define your model using C# and directly accessing the linear solver wrapper. The [#DefininaMIPModel next section] shows the implementation of a [#KnapsackProblemKSP Knapsack Problem (KSP)] and a [#TravelingSalesmanProblemTSP Traveling Salesman Problem (TSP)].
     25For a general introduction to MIP and a simple model implementation using the linear solver wrapper, see https://developers.google.com/optimization/mip/integer_opt. For further examples demonstrating more advanced usage of the linear solver wrapper using the C# API, see https://github.com/google/or-tools/tree/master/examples/dotnet.
     26
     27The `HeuristicLab.ExactOptimization` plugin provides a GUI for MIP, just create a new ''Mixed-Integer Linear Programming (LP, MIP)'' algorithm, found under ''Algorithms'', ''Exact''. In the ''Problem'' tab, you can either load your model from a file (MPS, Google OR-Tools Protocol Buffers files) or define your model in C# by directly accessing the linear solver wrapper. The [#DefiningaMIPModel next section] shows the implementation of a [#KnapsackProblemKSP Knapsack Problem (KSP)] and a [#TravelingSalesmanProblemTSP Traveling Salesman Problem (TSP)]. Furthermore, have a look at the [#SettingtheSolverParameters solver parameters] you can set in the ''Algorithm'' tab. 
    3228
    3329=== Defining a MIP Model ===
     
    211207}
    212208}}}
     209
     210=== Setting the Solver Parameters ===
     211
     212In the ''Algorithm'' tab of a ''Mixed-Integer Linear Programming (LP, MIP)'' algorithm, there are several parameters that are passed to the solvers. The most important parameter is the `LinearSolver` parameter, which lets you choose a solver. Note that all supported solvers are listed, even if they are not installed. Make sure that the additional solvers you install are added to the environment variable `Path` and the `LibraryName` parameter of the solver is set to the correct name of the solver DLL (e.g. `cplex1280.dll` for version 12.8.0 of CPLEX). The defaults for the solver DLLs can be set in the configuration file of HeuristicLab.
     213
     214[[Image(MixedIntegerLinearProgramming.png)]]
     215
     216The solver is terminated, once the time limit (parameter `TimeLimit`, set to `00:00:00` for unlimited runtime) is reached or the relative gap (between the best objective value and the bound) drops below the tolerance (parameter `RelativeGapTolerance`). Most solvers offer to change the `ProblemType` parameter to `LinearProgramming`, the solver then solves the linear programming relaxation of your model (all integer constraints are removed).
     217
     218To get intermediate results, use the parameter `QualityUpdateInterval`. Once the interval elapses, the solver is interrupted, the current solution is synchronized to the ''Results'' tab and the solver is resumed. To disable this behavior (and the slowdowns it causes), set the parameter to `00:00:00`.
     219
     220The parameter `SolverSpecificParameters` allows the user to set further parameters in the solver specific parameter file format. Have a look at the parameters supported by the solver you choose first, there are links in the comments. Note that the parameters you directly set in the user interface (`TimeLimit`, `RelativeGapTolerance` and the parameters for advanced usage that are hidden by default `Presolve`, `Scaling`, `PrimalTolerance` and `DualTolerance`) override the solver specific parameters.
    213221
    214222== Implementing New Models in HeuristicLab ==