Arc-flow Vector Packing Solver (VPSolver)
Copyright (C) 2013-2014, Filipe Brandão
Faculdade de Ciencias, Universidade do Porto
Porto, Portugal. All rights reserved. E-mail: <[email protected]>.
--
VPSolver is a vector packing solver based on an arc-flow formulation with graph
compression. VPSolver generates very strong models (equivalent to Gilmore and
Gomory's) that can be solved using general-purpose mixed-integer programming
solvers such as Gurobi and GLPK. VPSolver does not explicitly require any MIP
solver in particular, though a good MIP solver may be necessary for solving
large models.
For more details, please refer to the manual.
--
Project Homepage: http://code.google.com/p/vpsolver/
GitHub Mirror: https://github.com/fdabrandao/vpsolver
Bitbucket Mirror: https://bitbucket.org/fdabrandao/vpsolver
--
Requirements:
MIP solver: Gurobi, CPLEX, GLPK, COIN-OR, lp_solve, ...
Compiler: g++ >= 4.6
Python 2.7 for the python interface (optional)
It has been successfully compiled and run on the following platforms:
Linux
Mac OS X
Compiling VPSolver: ./compile.sh
--
VPSolver includes several scripts for solving arc-flow models using different
solvers:
scripts/vpsolver_gurobi.sh - Gurobi
scripts/vpsolver_cplex.sh - IBM CPLEX
scripts/vpsolver_coinor.sh - COIN-OR CBC Solver
scripts/vpsolver_glpk.sh - GLPK
scripts/vpsolver_lpsolve.sh - lp_solve
--
VPSolver includes several examples:
examples/example.sh - shell commands
examples/example.py - usage examples of pyvpsolver (the python interface)
examples/example_vbp.py - solves vector packing instances using pyvpsolver
examples/example_mvbp.py - solves multiple-choice vector packing instances
examples/example_vsbpp.py - solves variable-sized bin packing instances
--
Folders:
bin/ - vpsolver executables
scripts/ - vpsolver scripts
src/ - vpsolver source code in C++
pyvpsolver/ - pyvpsolver source code in Python 2.7
examples/ - vpsolver and pyvpsolver examples
reports/ - technical reports on the underlying algorithms and models
--
VPSolver was proposed in:
Brandão, F. and Pedroso, J. P. (2013). Bin Packing and Related Problems:
General Arc-flow Formulation with Graph Compression. Technical Report
DCC-2013-08, Faculdade de Ciências da Universidade do Porto, Universidade do
Porto, Portugal. Available at: http://arxiv.org/abs/1310.6887
See also:
Brandão, F. and Pedroso, J. P. (2013). Multiple-choice Vector Bin Packing:
Arc-flow Formulation with Graph Compression. Technical Report DCC-2013-13,
Faculdade de Ciências da Universidade do Porto, Universidade do Porto, Portugal.
Brandão, F. and Pedroso, J. P. (2013). Cutting Stock with Binary Patterns:
Arc-flow Formulation with Graph Compression. Technical Report DCC-2013-09,
Faculdade de Ciências da Universidade do Porto, Universidade do Porto, Portugal.
Brandão, F. (2012). Bin Packing and Related Problems: Pattern-Based Approaches.
Master’s thesis, Faculdade de Ciências da Universidade do Porto, Portugal.
--
Computational results on several benchmark test data sets:
http://www.dcc.fc.up.pt/~fdabrandao/research/vpsolver/results/
--
Filipe Brandão's Homepage: http://www.dcc.fc.up.pt/~fdabrandao/