Arc-flow Vector Packing Solver (VPSolver)

Copyright (C) 2013-2016, Filipe Brandão
Faculdade de Ciências, 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 (see, e.g., [1] and [2]). VPSolver does not explicitly require any MIP solver in particular, though a good MIP solver may be necessary for solving large models.

For modelling other problems easily, VPSolver includes a Python API, a modelling toolbox (PyMPL), and a Web App. VPSolver has been successfully compiled and run on Linux and Mac OS X. VPSolver also runs on a large variety of platforms including Windows using a Docker container.

For more details, please refer to the project wiki or to the manual.

Repositories

• Project Homepage: http://vpsolver.dcc.fc.up.pt
• GiHub repository: https://github.com/fdabrandao/vpsolver
• BitBucket repository: https://bitbucket.org/fdabrandao/vpsolver
• Docker repository: https://hub.docker.com/r/fdabrandao/vpsolver
• PyPI repository: https://pypi.python.org/pypi/pyvpsolver

Requirements

Mandatory

• MIP solver: Gurobi, CPLEX, GLPK, COIN-OR, SCIP, lp_solve, ...
• UNIX-like operating system or a UNIX-like environment such as Cygwin
• g++ >= 4.8; make >= 3.0; bash >= 3.0

Optional

For the Python API and Web App:

• python-2.7 or python-3.x
• python-pip
• python-dev
• glpk-utils

Platforms

It has been successfully compiled and run on the following platforms:

• Linux
• Mac OS X
• On a large variety of platforms including Windows using a Docker container
• It also runs on Windows using Cygwin (a Unix-like environment and command-line interface)

Setup

Without the python interface:

$ ./configure
$ make
$ sudo make install

With the python interface:

$ pip install -r requirements.txt
$ pip install . --upgrade
$ bash test.sh

Or simply install from the repository:

$ pip install pyvpsolver

Note: use pip install pyvpsolver --pre if you want to install the latest pre-release.

Docker

Docker Setup

Docker is an open platform for building, shipping and running applications. Docker allows VPSolver to run on a large variety of platforms with very little effort.

Install Docker [Docker installation instructions].

Option 1: simply pull VPSolver from Docker repository (without building):

$ docker pull fdabrandao/vpsolver

Option 2: clone VPSolver and build locally:

$ git clone [email protected]:fdabrandao/vpsolver.git vpsolver
$ docker build -t fdabrandao/vpsolver vpsolver

Usage

Directly using the command line interface:

$ docker run --rm -it fdabrandao/vpsolver bash
root@55d14f6b6f32:~# source venv2.7/bin/activate # load a virtualenv
(venv2.7)root@55d14f6b6f32:~# python examples/vpsolver/example_vbp.py
...

or through the VPSolver Web App (example URL: http://172.17.0.60:5555/):

$ docker run --rm -it -p 5555 fdabrandao/vpsolver 
eth0      Link encap:Ethernet  HWaddr 02:42:ac:11:00:3c  
          inet addr:172.17.0.60  Bcast:0.0.0.0  Mask:255.255.0.0
          inet6 addr: fe80::42:acff:fe11:3c/64 Scope:Link
          UP BROADCAST  MTU:1500  Metric:1
          RX packets:2 errors:0 dropped:0 overruns:0 frame:0
          TX packets:2 errors:0 dropped:0 overruns:0 carrier:0
          collisions:0 txqueuelen:0 
          RX bytes:168 (168.0 B)  TX bytes:180 (180.0 B)

URL: http://172.17.0.60:5555/
 * Running on http://0.0.0.0:5555/
...

For more details, please refer to the project wiki.

VPSolver Web App

VPSolver includes a Web App that can be started as follows:

$ python -m pyvpsolver.webapp.app

The Web App can then be accessed on a web browser at http://127.0.0.1:5555/.

VPSolver binaries

• $ bin/vpsolver intance.vbp: solves a vector packing instance using the method proposed in [1]. Note: requires Gurobi 5.0.0 or superior;
• $ bin/vbp2afg instance.vbp graph.afg: builds an arc-flow graph graph.afg for instance.vbp;
• $ bin/afg2mps graph.afg model.mps: creates a MPS model model.mps for graph.afg;
• $ bin/afg2lp graph.afg model.lp: creates a LP model model.lp for graph.afg;
• $ bin/vbpsol graph.afg vars.sol: extracts a vector packing solution from an arc-flow solution vars.sol associated with the graph graph.afg.

Usage:

# 1. Build the arc-flow graph graph.afg for example.vbp:  
$ bin/vbp2afg example.vbp graph.afg  
# 2. Convert the arc-flow graph into a .mps file model.mps:  
$ bin/afg2mps graph.afg model.mps  
# 3. Solve the MIP model and store the solution in vars.sol:
$ scritps/vpsolver_gurobi.sh --mps model.mps --wsol vars.sol
# 4. Extract the vector packing solution:  
$ bin/vbpsol graph.afg vars.sol  

VPSolver Scripts

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
• scripts/vpsolver_glpk.sh: GLPK
• scripts/vpsolver_scip.sh: SCIP
• scripts/vpsolver_lpsolve.sh: lp_solve

Usage:

$ vpsolver_X.sh --vbp instance.vbp
$ vpsolver_X.sh --afg graph.afg
$ vpsolver_X.sh --mps/--lp model.mps/.lp
$ vpsolver_X.sh --mps/--lp model.mps/.lp --afg graph.afg

Folders

• docs/: documentation
• scripts/: vpsolver scripts
• bin/: vpsolver executables
• src/: vpsolver source code in C++
• pyvpsolver/: pyvpsolver source code in Python
• examples/: vpsolver and pyvpsolver examples
• docs/reports/: technical reports on the underlying algorithms and models

Reports

VPSolver was proposed in:

• [1] Brandão, F. and Pedroso, J. P. (2016). Bin packing and related problems: General arc-flow formulation with graph compression. Computers & Operations Research, 69:56 – 67.
  doi: http://dx.doi.org/10.1016/j.cor.2015.11.009.

• [2] 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:

• [3] 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.

• [4] 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.

• [5] Brandão, F. (2012). Bin Packing and Related Problems: Pattern-Based Approaches Master’s thesis, Faculdade de Ciências da Universidade do Porto, Portugal.

• [6] Computational results on several benchmark test data sets:
  http://www.dcc.fc.up.pt/~fdabrandao/research/vpsolver/results/

---

Copyright © Filipe Brandão. All rights reserved.
E-mail: [email protected]. [Homepage]