Binary Integer Programming

Solve a small system with Binary Integer Programming (BIP) exactly. Use pulp python package with COIN library.

We first import all necessary modules

from prp.solvers.simple import CheapestPlaceSolver, PlaybackSolver
import prp.recorder as recorder
import prp.xy as xy
import prp.stats
import prp.utils as utils
import prp.solvers.bip as bip

Parameters

We define paths to JSON files of a small warehouse system:

LAYOUT_FILE = "../data/10-layout.json"
INITIAL_STATE_FILE = "../data/10-initial-state.json"
COSTS_FILE = "../data/10-costs.json"
DEPARTURES_FILE = "../data/10-departures.json"

and store the results to a JSON file:

SOLUTION_FILE = "../data/solutions/10-bip-solution.json"

Load a warehouse model from JSON files:

def load_problem():
    """Load a test system with 10 places and 10 pods randomly distributed among them."""
    layout = xy.Layout()
    with open(LAYOUT_FILE, 'r') as infile:
        layout.load_from_json(infile)
    warehouse = layout.get_empty_warehouse()
    with open(INITIAL_STATE_FILE, 'r') as infile:
        recorder.load_initial_state_from_json(infile, warehouse)
    with open(DEPARTURES_FILE, 'r') as infile:
        departures = recorder.load_departures_from_json(infile)
    warehouse.set_departure_generator(departures)
    costs = layout.get_costs()

Calculate

Sometimes we can solve a problem a little bit faster if we provide an upper bound for the objective function. We can obtain a simple bound if we solve this problem with another method – for example Cheapest place.

def get_cheapest_place_costs(warehouse):
    """Return costs when using cheapest-place solver with costs from station."""
    warehouse = prp.stats.copy_warehouse(warehouse)
    solver = CheapestPlaceSolver(warehouse, warehouse.costs)

    while not warehouse.finished():
        place_id = solver.decide_new_place()
        warehouse.next(place_id)

    return warehouse.total_costs

Optionally, you can switch on logging.

import logging

logging.basicConfig(level=logging.DEBUG)

We use the optional parameter costs_upper_bound to speed up calculation.

upper_costs = get_cheapest_place_costs(warehouse)
(solution, problem) = bip.solve(warehouse, threads=4, costs_upper_bound=upper_costs)

Finally we save the results.

utils.create_missing_directories_of_file(SOLUTION_FILE)
with open(SOLUTION_FILE, 'w') as outfile:
    recorder.store_solution_to_json(solution, outfile)

Test

Optionally, we can test our optimal solution for consistency

for place_id in solution:
    warehouse.next(place_id)

if not warehouse.finished():
    print("Problem is NOT solved completely")

and print the results.

print("Total costs {c} at time {t}, average costs {avg}".format(c=warehouse.total_costs,