fdabrandao / vpsolver

Arc-flow Vector Packing Solver (VPSolver)

Arc-flow Vector Packing Solver (VPSolver)

Copyright (C) 2013-2022, Filipe Brandão [email protected]

---

VPSolver is a multiple-choice vector packing solver based on an arc-flow formulation with graph compression (see, e.g., [1]). 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., [2] and [3]). 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, macOS, and Windows. VPSolver can also be used in Docker containers.

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

Repositories

• Project Homepage: http://vpsolver.fdabrandao.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

• To use vpsolver scripts for various solvers:

  • MIP solver: Gurobi, CPLEX, GLPK, COIN-OR, SCIP, lp_solve, ...
  • UNIX-like operating system or a UNIX-like environment such as Cygwin on Windows
  • g++, clang, or Visual Studio; cmake >= 3.3; bash >= 3.0

• To build the vpsolver executable linked to Gurobi:

  • gurobi
  • cmake >= 3.3

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
• macOS
• Windows (note that vpsolver scripts require bash)

Setup

Without the python interface:

$ mkdir build
$ cd build/
$ cmake ..
$ cmake --build . --config Release

Note: In order to compile the components that require Gurobi, you need to have set the environment variable GUROBI_HOME or specify the location of the Gurobi installation in the third step:

• Linux: cmake .. -DGUROBI_DIR=/opt/gurobi952/linux64/
• macOS: cmake .. -DGUROBI_DIR=/Library/gurobi952/macos_universal2/
• Windows: cmake .. -DGUROBI_DIR=C:\\gurobi952\\win64

With the python interface:

$ pip install -r requirements.txt
$ pip install . --upgrade
$ cd examples; py.test -v --cov pyvpsolver

Or simply install from the repository:

$ pip install pyvpsolver

Python interface

The python interface is fully compatible with both python 2 and 3.

Jupyter Notebooks for a quick introduction:

• Simple VBP example
• Simple MVP example

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 https://github.com/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 binaries

• $ bin/vpsolver intance.vbp/.mvp: solves a multiple-choice vector packing instance using the method described in [1]. Note: requires Gurobi 5.0.0 or superior;
• $ bin/vbp2afg instance.vbp/.mvp graph.afg: builds an arc-flow graph graph.afg for instance.vbp/.mvp;
• $ 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  

For more details, please refer to the manual.

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/--mvp instance.vbp/.mvp
$ 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

For more details, please refer to the manual.

Folders

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

References

The current solution method is described in:

• [1] Brandão, F. (2016). VPSolver 3: Multiple-choice Vector Packing Solver. arXiv:1602.04876.

VPSolver was proposed in:

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

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

See also:

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

• [5] 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. arXiv:1502.02899.

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

• [7] Computational results on several benchmark test data sets:
  https://research.fdabrandao.pt/research/vpsolver/results/

---

Copyright © 2013-2022 Filipe Brandão < [email protected] >. All rights reserved.

vpsolver's Issues

Getting signal received 1 by vpsolver on MVP instance

I am getting the following output on running MVP solver for a large sample. It takes more than 3-4 hours for graph compression and finally gives the signal 1 error. How to solve it? I am using gurobi solver. Same is the issue with glpk solver.

>>> vbp2afg...
VPSolver 3.1.3, Copyright (C) 2013-2016, Filipe Brandao
Build (method = -3)
signal received: 1

Explanation on bin packing result generation time

Hello @fdabrandao ,
I have a doubt regarding time it takes to generate bin packing results. I am currently using gurobi solver.
The experiment setup is as follows:
I have 8K - 4D bins and close to 10K tasks (4D) . I am basically trying to simulate a cloud workload. In that workload task requests arrive anywhere in the range of 10-200. The scenario is as follows:

• First set of tasks come lets say 10 tasks, they are placed onto 8K bins and bin sizes are updated
• This updated set of bins are used for placing next set of tasks
  The issue I am facing is if task requests are anywhere between 10-30 VpSolver is able to provide a solution for it. But if task request groups go beyond 30~36 VpSolv takes a lot of time to provide the results. Sometimes even after 6hrs of running the solver I do not have the result. Sometimes, entire system RAM is exhausted and VpSolver halts. Can I know the reason for this? Is there a certain bound in what time results can be generated? It would be really helpful for me to understand this. Requesting your help.

Thanks!

Run in different threads

Can I run separate mvp solver instances in different threads simultaneously? I tried using python's multiprocessing module for this. Every time I keep the number of processes/threads as 1, it works as expected but when I increase the number of threads, I get this error:
FileNotFoundError: [Errno 2] No such file or directory: '/tmp/tmpp105vrd2/1.tmp'

Here's the code for reference:

from pyvpsolver import VPSolver, MVP

def func(i):
    instance = MVP.from_file('demo.mvp')
    out, solution = VPSolver.script(
        "vpsolver_gurobi.sh", instance, verbose=False, options="Threads=12"
    )
    print(solution)

from multiprocessing import Pool

def run_parallel():
    
    list_ranges = [i for i in range(2)]

    pool = Pool(processes=len(list_ranges))
    pool.map(func, list_ranges)
  
if __name__ == '__main__':
    run_parallel()

MVP file (demo.mvp)

4
5
8 4 50 10 1 1
16 8 50 20 1 1
32 16 100 50 1 1
64 32 128 50 1 1
128 64 130 100 1 1
5
1 1
2 2 25 5
1 1
6 8 40 5
1 1
10 16 40 20
1 1
10 16 120 50
1 1
15 12 90 50

Getting Runtime error for the mvp

I am getting a runtime error for an MVP example. The file is: https://drive.google.com/file/d/1nC2VW7GcWXNxm38IHXr1X23rZwk1s7pw/view?usp=sharing
The error states:
>>> vbp2afg... VPSolver 3.1.3, Copyright (C) 2013-2016, Filipe Brandao AssertionError: assertion 'nfits >= 1' failed in "src/instance.cpp" line 236 Traceback (most recent call last): File "bin_packing.py", line 13, in <module> out, solution = VPSolver.script( File "/home/prathamesh/BinPacking/vbp_env/lib/python3.8/site-packages/pyvpsolver/vpsolver.py", line 570, in script VPSolver.run(cmd, tee=out_file, verbose=verbose) File "/home/prathamesh/BinPacking/vbp_env/lib/python3.8/site-packages/pyvpsolver/vpsolver.py", line 421, in run raise RuntimeError("failed to run '{}'".format(cmd)) RuntimeError: failed to run 'vpsolver_glpk.sh --mvp /tmp/tmpoo_hazgd/0.mvp --pyout'
Is it because file is to big to be solved by vpsolver? smaller subsets are solved by vpsolver

Multi-stage Cutting Stock

Hey, great work on VPSolver!

WebApp in Docker image is missing "Multi-stage Cutting Stock" and "Cost-based Cutting Stock" examples. Is there a specific reason for that?

Thanks.

VPSolver works faster in virtual machine than a bare metal server

I tried serving the solver via a flask application to do some benchmarking as this is a CPU-intensive job. Here's my flask snippet:

import uuid

from werkzeug.utils import secure_filename
from flask import Flask, request, jsonify, abort

from pyvpsolver import VPSolver, MVP

app = Flask(__name__)

@app.route('/bins', methods=['POST'])
def allocate_bins():
    tmpfile = f'temp/{str(uuid.uuid1())}'

    input_ = request.files['input']
    filename = secure_filename(input_.filename)
    input_.save(tmpfile + '_' + filename)

    instance = MVP.from_file(tmpfile + '_' + filename, verbose=False)
    out, solution = VPSolver.script("vpsolver_glpk.sh", instance, verbose=False)
    print(f"Bins: {solution[0]}")

    try:
        return jsonify({"bins": solution[0]}), 200
    except Exception as e:
        abort(404)

if __name__ == "__main__":
    app.run(host="0.0.0.0", port=5005)

The peculiar thing about this exercise is that for some MVP files, it takes a long time (as long as 20-30 minutes) to compute in bare metal, whereas executes almost instantaneously (in 0.2-0.5s) in virtual machines. Is there any explanation for this behaviour?

When I keep the MVP file constant, the CPU is 100% utilised at 30 concurrent users in the case of bare metal, whereas it takes around 40 users to achieve the same CPU utilisation virtual machine. Isn't this a bit counterproductive? If anything, a VM should take longer to process a job than it's bare metal counterpart

Can't find the vpsolver_scip.sh for SCIP optimizer

Hello,
I have completed the following in Ubuntu:
"sudo apt-get install make"
"sudo apt-get install bash"
"sudo apt-get install gcc"
"sudo pip3 install pyvpsolver"
However, running script suing SCIP optimizer providing me below error.
Did I miss some steps of pyvpsolver on Ubuntu?

vbpsol...
VPSolver 3.1.2, Copyright (C) 2013-2016, Filipe Brandao
free(): double free detected in tcache 2
/home/adilet/.local/bin/vpsolver_scip.sh: line 186: 6344 Aborted (core dumped) vbpsol $afg_file $TMP_DIR/vars.sol $vbpsol_opts
Traceback (most recent call last):
File "1s.py", line 107, in
raw_solution = solve(order_q, order_b, inventory, cost, solver)
File "1s.py", line 41, in solve
output, solution = VPSolver.script(solver_dict[solver], instance)
File "/home/adilet/.local/lib/python3.8/site-packages/pyvpsolver/vpsolver.py", line 570, in script
VPSolver.run(cmd, tee=out_file, verbose=verbose)
File "/home/adilet/.local/lib/python3.8/site-packages/pyvpsolver/vpsolver.py", line 421, in run
raise RuntimeError("failed to run '{}'".format(cmd))
RuntimeError: failed to run 'vpsolver_scip.sh --mvp /tmp/tmphk0uhzjl/0.mvp --pyout'

Error: free(): double free detected in tcache 2

Hello,
I am getting this wierd error stating:

>>> vbpsol...
VPSolver 3.1.3, Copyright (C) 2013-2016, Filipe Brandao
free(): double free detected in tcache 2
/data/prathamesh_home/bin_packing_heuristics/venv/bin/vpsolver_scip.sh: line 186: 2406799 Aborted                 
(core dumped) vbpsol $afg_file $TMP_DIR/vars.sol $vbpsol_opts

Even after optimizers like GUROBI or SCIP state optimal solution found, during vbpsol phase I get this error.

SCIP Status        : problem is solved [optimal solution found]
Solving Time (sec) : 148.32
Solving Nodes      : 1
Primal Bound       : +3.00000000000000e+00 (1 solutions)
Dual Bound         : +3.00000000000000e+00
Gap                : 0.00 %

How to fix?

k best targets instead of 1

Hi @fdabrandao,

Can the algorithm's implementation be modified in a way that it outputs 'k' (an argument of our choice) possible bins instead of the best bin?

Issue downloading

I'm a windows user. I've been trying to download using ubuntu. I'm trying to implement into a python project I've been working on.

I have up to date cmake, bash, g++, clang, and visual studio. I have scip installed on my machine.

However when I download on Ubuntu:
when it runs setup.py bdist_wheel

When it runs setup.py

Do you have any guidance that can help?

Order of items affects result

@fdabrandao How/why should the order of items affect the packing? I tried modifying the order in which the items were being listed in the .mvp file and got strikingly different results. However, changing the order of targets doesn't affect the output

How to add "blade width" parameter in CSP

Thank you for your hard work! Your product solves the CSP problem perfectly, but I would like to know how you can add the ability to take into account the width of the cutting blade for the correct calculation. Thanks.

Using .vbp file in Python

Hello,
I'm trying to use VPSolver with the Python API, I found out that the result of this script :

from pyvpsolver.solvers import vbpsolver

W = (5180, 2)
w = [(1120,1), (1250,1), (520,1), (1066,1), (1000,1), (1150,1)]
b = [9, 5, 91, 18, 11, 64]

# Solve a vector packing instance:
solution = vbpsolver.solve(
    W, w, b, script="vpsolver_glpk.sh", verbose=False
)
# Print the solution:
vbpsolver.print_solution(solution)

was not the same as the result sent by the webapp :

I think it is from the fact that in Python we need to add a second parameter to the W variable. If you can explane that to me.
And secondly i would like to know how can we use vbp file directly in Python, in this kind of format :

1
5180
6
1120 9
1250 5
520 91
1066 18
1000 11
1150 64

Thank you for your help.