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"
- solved with CLP
-
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
- solved with volume method
-
Lagrangian relaxation of assignment constraints
- solved with volume method
-a lagrelax-assignment-volume
- solved with L-BFGS method
-a lagrelax-assignment-lbfgs
- solved with volume method
-
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"
- Basic greedy
-
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"
- Greedy
-
Others heuristics:
- Random feasible solution found with a Local search
-a random
- Local search with LocalSolver
-a localsolver
- Random feasible solution found with a Local search
-
Mixed-Integer Linear Programs
- with CBC
-a milp-cbc
- with CPLEX
-a milp-cplex
- with Gurobi
-a milp-gurobi
- with Knitro
-a milp-knitro
- with CBC
-
Constraint programming
- with Gecode
-a constraint-programming-gecode
- with CPLEX
-a constraint-programming-cplex
- with Gecode
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/