README.md

Operations research problems

Data, C++ parsers and solution checkers for various operations research problems.

These are the problems used as examples for fontanf/localsearchsolver, fontanf/treesearchsolver and fontanf/columngenerationsolver.

The data also include CSV files listing the instances for each problem and their best known bounds which can be used with the benchmark scripts from fontanf/optimizationtools.

Packing:

• Knapsack problem with conflicts / disjunctively constrained knapsack problem
• Multidimensional multiple-choice knapsack problem
• Cutting stock problem
• Multiple knapsack problem
• Quadratic multiple knapsack problem
• Bin packing problem with conflicts

Assignment:

• Quadratic assignment problem

Routing:

• Single vehicle
  • Traveling salesman problem with release dates
    • Release dates for the arrival of goods to the depot, the solution may require multiple trips.
  • Traveling repairman problem / minimum latency problem
    • Three field classification: 1 | sᵢⱼ | ∑Cⱼ
  • Time-dependent orienteering problem
  • Orienteering problem with hotel selection
• Multiple vehicles
  • Capacitated vehicle routing problem
  • Vehicle routing problem with time windows
    • Time windows / Capacity constraint / Maximum number of vehicles
  • Capacitated open vehicle routing problem
    • No need to return to the depot / Capacity constraint / Maximum route length / Maximum number of vehicles
  • Team orienteering problem

Scheduling:

• Single machine scheduling
  • Sequential ordering problem
    • Three fields classification: 1 | sᵢⱼ, prec | Cₘₐₓ
  • Single machine scheduling problem with sequence-dependent setup times, total weighted tardiness
    • Three field classification: 1 | sᵢⱼ | ∑wⱼTⱼ
  • Single machine order acceptance and scheduling problem with time windows and sequence-dependent setup times, total weighted tardiness
    • Three field classification: 1 | rⱼ, sᵢⱼ, reject, đⱼ | ∑wⱼTⱼ - ∑vⱼ
  • Job sequencing and tool switching
  • Single machine batch scheduling problem, total completion time
    • Three field classification: 1 | batch, sⱼ | ∑Cⱼ
  • Single machine batch scheduling problem, total weighted tardiness
    • Three field classification: 1 | batch, rⱼ, sⱼ, compt | ∑wⱼTⱼ
• (Unrelated) parallel machine scheduling
  • Identical parallel machine scheduling problem with family setup times, total weighted completion time
    • Three field classification: P | sᵢ | ∑wⱼCⱼ
• Flow shop scheduling
  • Permutation flow shop scheduling problem, makespan
    • Three field classification: Fm | prmu | Cₘₐₓ
  • Permutation flow shop scheduling problem, total completion time
    • Three field classification: Fm | prmu | ∑Cⱼ
  • Permutation flow shop scheduling problem, total tardiness
    • Three field classification: Fm | prmu | ∑Tⱼ
  • Distributed permutation flow shop scheduling problem, Makespan
    • Three field classification: DFm | prmu | Cₘₐₓ
  • Distributed permutation flow shop scheduling problem, Total completion time
    • Three field classification: DFm | prmu | ∑Cⱼ
• Job shop scheduling
  • No-wait job shop scheduling problem, makespan
    • Three field classification: Jm | no-wait | Cₘₐₓ
• Assembly Line Balancing
  • Simple assembly line balancing problem of type 1 (SALBP-1)
    • Bin Packing Problem with precedence constraints of the form bin(j1) <= bin(j2)
  • U-shaped assembly line balancing problem of type 1 (UALBP-1)