A solver for the generalized assignment problem.

This problem is interesting because many different optimization methods can and have been applied to solve it (Branch-and-cut, Branch-and-price, Branch-and-relax, Local search, Constraint programming, Column generation heuristics...). Thus, the main goal of this repository is for me to have reference implementations for classical algorithms and optimization solvers.

The variant handled here is the variant:

• with a minimization objective (items have costs)
• where all items have to be assigned

It is possible to solve the variant with a maximization objective (items have profits) by setting the cost of assigning item an j to agent an i to maximum profit of item j - profit of assigning item j to agent i.

It is possible to solve the variant where not all items have to be assigned by adding an additional dummy agent i such that the weight of assigning an item j to this agent i is equal to 0 and the cost of assigning an item j to this agent i is equal to maximum profit of item j

• Linear relaxation

  • solved with CLP -a linrelax-clp
  • solved with Gurobi -a "milp-gurobi --only-linear-relaxation"
  • solved with Cplex -a "milp-cplex --only-linear-relaxation"

• Lagrangian relaxation of knapsack constraints. The value of this relaxation is the same as the value of the linear relaxation. However, it might be cheaper to compute, especially on large instances.

  • solved with volume method -a lagrelax-knapsack-volume
  • solved with L-BFGS method -a lagrelax-knapsack-lbfgs

• Lagrangian relaxation of assignment constraints

  • solved with volume method -a lagrelax-assignment-volume
  • solved with L-BFGS method -a lagrelax-assignment-lbfgs

• Column generation -a "column-generation --linear-programming-solver clp" -a "column-generation --linear-programming-solver cplex"

• Polynomial algorithms from "Generalized Assignment Problems" (Martello et al., 1992), options -f cij -f wij -f cij*wij -f -pij/wij -f wij/ti:

  • Basic greedy -a "greedy -f wij"
  • Greedy with regret measure -a "greedy-regret -f wij"
  • MTHG, basic greedy (+ n shifts) -a "mthg -f wij"
  • MTHG, greedy with regret measure (+ n shifts) -a "mthg-regret -f wij"

• Local search algorithm implemented with fontanf/localsearchsolver -a "local-search --threads 3"

• Tree search algorithms based on the Dantzig-Wolfe reformulation branching scheme (i.e. column generation heuristics) implemented with fontanf/columngenerationsolver:

  • Greedy -a "column-generation-heuristic-greedy --linear-programming-solver cplex"
  • Limited discrepency search -a "column-generation-heuristic-limited-discrepancy-search --linear-programming-solver cplex"

• Others heuristics:

  • Random feasible solution found with a Local search -a random
  • Local search with LocalSolver -a localsolver

• Mixed-Integer Linear Programs

  • with CBC -a milp-cbc
  • with CPLEX -a milp-cplex
  • with Gurobi -a milp-gurobi
  • with Knitro -a milp-knitro

• Constraint programming

  • with Gecode -a constraint-programming-gecode
  • with CPLEX -a constraint-programming-cplex

The only required dependency is Boost:

sudo apt-get install libboost-all-dev

Compile:

bazel build -- //...

However, most algorithms require additional libraries (see below). Compile with additional libraries (or just uncomment the corresponding lines in .bazelrc):

bazel build \
    --define coinor=true \
    --define cplex=true \
    --define gurobi=true \
    --define gecode=true \
    --define dlib=true \
    --define localsolver=true \
    --define knitro=true \
    -- //...

Solve:

./bazel-bin/generalizedassignmentsolver/main -v 1 -a 'mthg -f -pij/wij' -i "data/chu1997/a05100" -o "a05100_output.json" -c "a05100_solution.txt"

=====================================
     GeneralizedAssignmentSolver     
=====================================

Instance
--------
Number of agents:         5
Number of items:          100

Algorithm
---------
MTHG

Parameters
----------
Desirability:  -pij/wij

       T (s)          UB          LB         GAP     GAP (%)                 Comment
       -----          --          --         ---     -------                 -------
       0.000         inf        1694         inf         inf                        
       0.000        1713        1694          19        1.12                        

Final statistics
----------------
Value:                        1713
Bound:                        1694
Absolute optimality gap:      19
Relative optimality gap (%):  1.12161
Time (s):                     0.000140967

Solution
--------
Number of items:  100 / 100 (100%)
Feasible:         1
Cost:             1713

Unit tests:

bazel test --compilation_mode=dbg -- //...

Checker:

./bazel-bin/generalizedassignmentsolver/checker data/a05100 output/best/a05100_solution.txt

Run benchmarks:

python3 ../optimizationtools/optimizationtools/bench_run.py --algorithms "mthg -f cij" "mthg -f wij" "mthg -f cij*wij" "mthg -f -pij/wij" "mthg -f wij/ti" "mthg-regret -f cij" "mthg-regret -f wij" "mthg-regret -f cij*wij" "mthg-regret -f -pij/wij" "mthg-regret -f wij/ti" "random"
python3 ../optimizationtools/optimizationtools/bench_process.py --benchmark heuristicshort --labels "mthg -f cij" "mthg -f wij" "mthg -f cij*wij" "mthg -f -pij/wij" "mthg -f wij/ti" "mthg-regret -f cij" "mthg-regret -f wij" "mthg-regret -f cij*wij" "mthg-regret -f -pij/wij" "mthg-regret -f wij/ti" "random" --timelimit 0.1

To enable a dependency, uncomment the corresponding line in the .bazelrc file and adapt its path in the WORKSPACEi file.

Here are some notes for their installations:

Install (https://coin-or.github.io/coinbrew/):

git clone https://www.github.com/coin-or/coinbrew
cd coinbrew
./coinbrew fetch build Vol --no-prompt

Download latest version: download https://www.gecode.org/download.html

Compile (more info https://www.gecode.org/doc/2.2.0/reference/PageComp.html):

./configure
make

After installing, execute the following commands:

cd ${GUROBI_HOME}/linux64/src/build/
make
cp libgurobi_c++.a ../../lib/