Generators for Combinatorial Optimization
This python package offers functionality to easily create instances for combinatorial optimization problems like knapsack or facility location. By making use of well known open source libraries such as NetworkX for graphs and PySCIPOpt for mathematical programming, the created instances can be used directly or saved to disk in a variety of different file formats. Releases of GeCO get pushed to PyPI, which makes it easy to install it into the python distribution of your choice via pip.
Assume you want a knapsack instance like in this paper by Yang et al.
To generate an instance with 5 items and save it to disc you would simply run:
from geco import knapsack
knapsack_model = knapsack.yang.yang_instance(n=5, seed=1)
knapsack_model.writeProblem("yang_n5.mps")The mixed integer programming part of the code heavily depends on the python interface of SCIP: PySCIPOpt. The easiest way to install it is using conda
conda install -c scipopt pyscipoptIf you prefer installing SCIP yourself or using an existing installation of SCIP on your system, you can follow this guide for installing pyscipopt.
Then, once you have pyscipopt installed, you are ready to install the geco package.
pip install gecoThat's it, now you are ready to generate some instances!
Assume you want a knapsack instance like in the Yang et al. paper.
You start by looking through the knapsack package, then searching for a file with the name FIRSTAUTHOR.py.
In this case we find a yang.py file in the mips/knapsack package.
To generate an instance with 5 items you would run
from geco import knapsack
knapsack_model = knapsack.yang.yang_instance(n=5, seed=1)This, as all generators inside the mips subpackage, returns a PySCIPOpt model that makes use of the SCIP mixed
integer programming solver, refer to their docs to learn how to set params, solve the instance and a lot more.
As you might have noticed the generator function has a seed parameter, as a matter of fact this is common through out
all generators that exhibit random behavior, it is used to preserve the random state, in order to get a random instance
each time you can use seed=None.
In case you want to generate more than one instance, we have created some helpful generator functions in
the generator.py.
To generate n instances you can use the generate_n function, an example to generate 10 Yang knapsack instances would
be
from geco.generator import generate_n
from geco.mips.knapsack import yang
for model in generate_n(lambda seed: yang.yang_instance(n=5, seed=seed), n=10):
model.optimize()There is also another function generate which is more flexible, assuming you don't know exactly how many instance you
might require, it works the exact same way it just doesn't stop after n instances are generated.
MIPLIB 2017 instances can be loaded into a PySCIPOpt model using the Loader class.
from geco.mips.loading.miplib import Loader
instance = Loader().load_instance('INSTANCE_NAME.mps.gz')All the following instances are implemented following some of the generation techniques found in the literature, please refer to the modules corresponding to the generating function for a reference to where it was introduced.
- Capacitated Facility Location
- Scheduling
- Knapsack
- Set Packing
- Set Cover
- Production Planning
- Maximum Independent Set
- Maximum Cut
- Packing
- Graph Coloring
- Chimera (Selby)
- Pegasus
If you want to add some new generator, fix a bug or enhance the repository in some way, please refer to our guide.
React
Typescript
Django
Laravel
Facebook
Microsoft
Google
Alibaba
D3
Tencent