Column Generation Solver

A solver based on column generation.

image source

Description

The goal of this repository is to provide a simple framework to quickly implement heuristic algorithms based on column generation.

It is only required to provide the description of the linear program of the Dantzig–Wolfe decomposition of the master problem as well as the algorithm solving the pricing problem. No branching rule implementation is required.

The currently implemented algorithms are based on the algorithms from "Primal Heuristics for Branch and Price: The Assets of Diving Methods" (Sadykov et al., 2019).

This package does not implement any exact algorithm. However, if the pricing algorithm is exact, it provides a valid dual bound. If the pricing algorithm is heuristic, the primal algorithms still works, but then the dual bound is not valid.

Solving a problem only requires a couple hundred lines of code (see examples).

A linear programming solver is required. Currently, CLP and CPLEX are supported.

Features:

• Algorithms:
  • Column generation column_generation
  • Greedy greedy
  • Limited Discrepancy Search limited_discrepancy_search
  • Heuristic Tree Search heuristic_tree_search
• Sabilization technics:
  • Static and self-adjusting Wentges smoothing
  • Static and automatic directional smoothing

Examples

Data can be downloaded from fontanf/orproblems

Packing

Cutting Stock Problem

• Pricing problem: Bounded Knapsck Problem solved with the minknap algorithm from fontanf/knapsacksolver

Benchmarks

• Benchmarks:
  • python3 ../optimizationtools/optimizationtools/bench_run.py --main ./bazel-bin/examples/cuttingstock_main --csv ../ordata/cuttingstock/data.csv -l cuttingstock -a "heuristic_tree_search" -t 60

Multiple Knapsack Problem

• Pricing problem: Knapsck Problem solved with the minknap algorithm from fontanf/knapsacksolver

Benchmarks

• Benchmarks:
  • python3 ../optimizationtools/optimizationtools/bench_run.py --main ./bazel-bin/examples/multipleknapsack_main --csv ../ordata/multipleknapsack/data.csv -l multipleknapsack -a "heuristic_tree_search" -t 10

Generalized Assignment Problem from fontanf/generalizedassignmentsolver

• Pricing problem: Knapsck Problem solved with the minknap algorithm from fontanf/knapsacksolver

Geometrical Cutting Stock and Variable-sized Bin Packing Problems from fontanf/packingsolver

• Pricing problem: Geometrical Knapsack Problems solved with the algorithms from the same repository

Bin Packing Problem with Conflicts

• Pricing problem: Knapsack Problem with Conflicts solved with the Heuristic Tree Search algorithm from fontanf/treesearchsolver

Routing

Capacitated Vehicle Routing Problem

• Pricing problem: Elementary Shortest Path Problem with Resource Constraint solved by Heuristic Tree Search using fontanf/treesearchsolver

Vehicle Routing Problem with Time Windows

• Pricing problem: Elementary Shortest Path Problem with Resource Constraint and Time Windows solved by Heuristic Tree Search using fontanf/treesearchsolver

Capacitated Open Vehicle Routing Problem

• Pricing problem: Elementary Open Shortest Path Problem with Resource Constraints solved by Heuristic Tree Search using fontanf/treesearchsolver

Scheduling

Identical parallel machine scheduling problem with family setup times, Total weighted completion time

• Pricing problem: Single machine order acceptance and scheduling problem with family setup times, Total weighted completion time solved by Heuristic Tree Search using fontanf/treesearchsolver

Benchmarks

• Benchmarks:
  • python3 ../optimizationtools/optimizationtools/bench_run.py --main ./bazel-bin/examples/parallelschedulingwithfamilysetuptimestwct_main --csv ../ordata/parallelschedulingwithfamilysetuptimestwct/data.csv -l parallelschedulingwithfamilysetuptimestwct -a "heuristic_tree_search" -t 60

Star Observation Scheduling Problem

• Pricing problem: Single Night Star Observation Scheduling Problem solved by dynamic programming

Benchmarks

• Benchmarks:
  • python3 ../optimizationtools/optimizationtools/bench_run.py --main ./bazel-bin/examples/starobservationscheduling_main --csv ../ordata/starobservationscheduling/data.csv -l starobservationscheduling -a "heuristic_tree_search" -t 60

Graphs

Graph Coloring Problem from fontanf/coloringsolver

• Pricing problem: Maximum-Weight Independent Set Problem solved with the localsearch algorithm from fontanf/stablesolver implemented with fontanf/localsearchsolver

Usage, running examples from command line

You need to have a linear programming solver already installed. Then update the corresponding entry in the WORKSPACE file. You may only need to update the path attribute of the solver you are using. Then, compile with one of the following command:

bazel build --define clp=true -- //...
bazel build --define cplex=true -- //...

Then, examples can be executed as follows:

./bazel-bin/examples/cuttingstock_main -v -a "column_generation" -i "../ordata/cuttingstock/falkenauer1996/T/Falkenauer_t120_00.txt"
./bazel-bin/examples/multipleknapsack_main -v -a "limited_discrepancy_search" -i "../ordata/multipleknapsack/fukunaga2011/FK_1/random10_100_4_1000_1_1.txt"

Usage, C++ library

See examples.