Git Product home page Git Product logo

docker-scip's Introduction

docker-scip

Building a docker container with the SCIP Optimization Suite (v7.0.2) + Solving optimization (0-1 knapsack problem) with PySCIPOpt inside the container.

Why to choose SCIP

SCIP is currently one of the fastest non-commercial solvers for mixed integer programming (MIP) and mixed integer nonlinear programming (MINLP). It's regularly updated releasing a new version several times a year. In addition, it provides an easy-to-use Python API to the SCIP optimization software (PySCIPOpt).

How to build docker

Before building a container, you need to download the latest version of the SCIP Optimization Suite, currently it's 7.0.2 version. SCIP is distributed under the Academic License, and you can download it from the official website.

Note, that you need to download deb installer. Copy it to the root directory (where the Dockerfile is located).

Then to build a docker image, you can issue docker-compose from the root directory:

$ docker-compose build

When building process is over, you can see the new image.

$ docker images
REPOSITORY          TAG                 IMAGE ID            CREATED             SIZE
scip                v0.1                78791bbde634        14 hours ago        519MB

Packing knapsack

To demonstrate how to use PySCIPOpt, we show how to solve a small-scale knapsack problem for the case of multiple knapsacks.

Let's assume, that we have a collection of items with different weights and values, and we want to pack a subset of items into five knapsacks (bins), where each knapsack has a maximum capacity 100, so the total packed value is a maximum.

Define a simple container class to store item parameters and initialize 15 items.

class Item:
    def __init__(self, index, weight, value):
        self.index = index
        self.weight = weight
        self.value = value

items = [
    Item(1, 48, 10), Item(2, 30, 30), Item(3, 42, 25), Item(4, 36, 50), Item(5, 36, 35), 
    Item(6, 48, 30), Item(7, 42, 15), Item(8, 42, 40), Item(9, 36, 30), Item(10, 24, 35), 
    Item(11, 30, 45), Item(12, 30, 10), Item(13, 42, 20), Item(14, 36, 30), Item(15, 36, 25)
]

Introduce bins (knapsacks) in the similar fashion.

class Bin:
    def __init__(self, index, capacity):
        self.index = index
        self.capacity = capacity

bins = [Bin(1, 100), Bin(2, 100), Bin(3, 100), Bin(4, 100), Bin(5, 100)]

As a next step, we create a solver instance.

from pyscipopt import Model, quicksum

model = Model()

We introduce the binary variables x[i, j] indicating that item i is packed into bin j.

x = dict()
for _item in items:
    for _bin in bins:
        x[_item.index, _bin.index] = model.addVar(vtype="B")

Now we add the constraints which prevent the situations when the same item is packed into multiple bins. It says that each item can be placed in at most one bin.

for _item in items:
    model.addCons(quicksum(x[_item.index, _bin.index] for _bin in bins) <= 1)

The following constraints require that the total weight packed in each knapsack don't exceed its maximum capacity.

for _bin in bins:
    model.addCons(
        quicksum(
            _item.weight * x[_item.index, _bin.index] for _item in items
        ) <= _bin.capacity)

Finally, we define an objective function as a total value of the packed items and run the optimization.

model.setObjective(
    quicksum(
        _item.value * x[_item.index, _bin.index]
        for _item in items for _bin in bins
    ), 
    sense="maximize")

model.optimize()

See script knapsack.py for more details.

Running SCIP solver inside docker

We copy script knapsack.py to /home/user/scripts directory inside the container when building an image:

RUN mkdir /home/user/scripts
ADD knapsack.py /home/user/scripts

To launch the script, we start the container in the detached mode:

$ docker-compose up -d

To run the script inside the container, we use docker exec command. The optimization displays the following output:

$ docker exec -it scip python scripts/knapsack.py
...
Bin 1
Item 6: weight 48, value 30
Item 13: weight 42, value 20
Packed bin weight: 90
Packed bin value : 50

Bin 2
Item 3: weight 42, value 25
Item 8: weight 42, value 40
Packed bin weight: 84
Packed bin value : 65

Bin 3
Item 4: weight 36, value 50
Item 5: weight 36, value 35
Item 10: weight 24, value 35
Packed bin weight: 96
Packed bin value : 120

Bin 4
Item 2: weight 30, value 30
Item 11: weight 30, value 45
Item 14: weight 36, value 30
Packed bin weight: 96
Packed bin value : 105

Bin 5
Item 9: weight 36, value 30
Item 15: weight 36, value 25
Packed bin weight: 72
Packed bin value : 55

Total packed value: 395.0

To stop the running container, use down command:

docker-compose down

Read the tutorial for more.

docker-scip's People

Contributors

viktorsapozhok avatar

Stargazers

 avatar  avatar  avatar  avatar

Watchers

 avatar

Recommend Projects

  • React photo React

    A declarative, efficient, and flexible JavaScript library for building user interfaces.

  • Vue.js photo Vue.js

    ๐Ÿ–– Vue.js is a progressive, incrementally-adoptable JavaScript framework for building UI on the web.

  • Typescript photo Typescript

    TypeScript is a superset of JavaScript that compiles to clean JavaScript output.

  • TensorFlow photo TensorFlow

    An Open Source Machine Learning Framework for Everyone

  • Django photo Django

    The Web framework for perfectionists with deadlines.

  • D3 photo D3

    Bring data to life with SVG, Canvas and HTML. ๐Ÿ“Š๐Ÿ“ˆ๐ŸŽ‰

Recommend Topics

  • javascript

    JavaScript (JS) is a lightweight interpreted programming language with first-class functions.

  • web

    Some thing interesting about web. New door for the world.

  • server

    A server is a program made to process requests and deliver data to clients.

  • Machine learning

    Machine learning is a way of modeling and interpreting data that allows a piece of software to respond intelligently.

  • Game

    Some thing interesting about game, make everyone happy.

Recommend Org

  • Facebook photo Facebook

    We are working to build community through open source technology. NB: members must have two-factor auth.

  • Microsoft photo Microsoft

    Open source projects and samples from Microsoft.

  • Google photo Google

    Google โค๏ธ Open Source for everyone.

  • D3 photo D3

    Data-Driven Documents codes.