Skip to content

coin-or/Vol

Repository files navigation

Welcome to the COIN Vol Project

Introduction

Vol (Volume Algorithm) is an open-source implementation of a subgradient method that produces primal as well as dual solutions. The primal solution comes from estimating the volumes below the faces of the dual problem. This is an approximate method so the primal vector might have small infeasiblities that are negligible in many practical settings. The original subgradient algorithm produces only dual solutions.

Background/Download

Vol is written in C++ and is released as open source code under the Eclipse Public License(EPL). To get all of the dependencies and build the Vol package, do

git clone https://github.com/coin-or/Vol 
Vol
git clone https://github.com/coin-or-tools/BuildTools
BuildTools/get.dependencies fetch
BuildTools/get.dependencies build

To test by building an application, do

cd build/Vol/examples/VolUfl
make
./ufl

Included Projects

If you download the Vol package, you get these additional projects.

Doxygen Documentation

If you have Doxygen available, you can build the html documentation by typing

make doxydoc

in the Vol directory. Then open the file coin-Vol/doxydoc/html/index.html with a browser.
Note that this creates the documentation for the Vol package as a whole. If you prefer to generate the documentation only for a subset of these projects, you can edit the file Vol/doxydoc/doxygen.conf to exclude directories
(using the EXCLUDE variable, for example).

If Doxygen is not available, you can use the link to the {{{Vol}}} html documentation listed below.

Documentation

FAQ

For what type of problems has VOL been used?

It has been tested with a variety of combinatorial problems like: Crew scheduling, Fleet assignment, Facility location, Steiner trees, Max-Cut, Quadratic knapsack.

Can one solve a linear program with VOL?

One can get good and fast approximate solutions for combinatorial linear programs. These are LP's where all variables are between 0 and 1.

Can one solve integer programs with VOL?

VOL gives bounds based on a relaxation of the IP. It also gives primal (fractional) solutions. With this information one can run a heuristic to produce an integer solution, or one can imbed VOL in a branch and bound code.

Can one do "branch and cut" with VOL?

Yes, as an example, there is an implementation of a cutting plane algorithm for the Max-cut problem, that combines BCP and Vol.

Can one use VOL for column generation?

Yes. VOL has been very useful for accelerating column generation procedures, in particular for Crew Scheduling. The dual solutions given by VOL seem to provide faster convergence than if one uses dual solutions given by the Simplex method.

What platforms does VOL run on?

VOL has been tested on:

  • AIX V4.3 using g++ V2.95.2
  • Linux using g++ V2.95.2.
  • Solaris (SunOS 5.6 and 5.8) using g++ V2.95.2

About

A C++ implementation of the volume algorithm for linear programming

Resources

License

Stars

Watchers

Forks

Packages

No packages published

Contributors 4

  •  
  •  
  •  
  •