Copyright	(c) Pablo Couto 2014
License	GPL-3
Maintainer	pablo@infty.in
Stability	experimental
Safe Haskell	None
Language	Haskell2010

Referees.Solver.Internal

Contents

Solving the Generalized Assignment Problem by approximation with GLPK

Description

This module contains the core functions used in solving the Generalized Assignment Problem with the help of the GLPK toolkit.

Synopsis

Solving the Generalized Assignment Problem by approximation with GLPK

Formulation of the problem for GLPK

lpGAP :: ProfitMatrix -> [Capacity] -> Bounds Copies -> LP String Double Source

lpGAP is based on Martello & Toth 1990’s linear integer programming formulation of the Generalized Assignment Problem (GAP). This function, in addition, excludes all combinations whose profit is 0. lpGAP interfaces with the GLPK toolkit through glpk-hs.

In lpGAP profitM caps bounds, profitM is a profit matrix (which can be computed by mkProfitMatrix, using a ProfitFunction), caps stands for a list of items’ capacities (computable by toCap), and bounds encodes in a Bounds Copies value (producible with mkBounds) both the lower and upper bounds on the number of copies to distribute per each item.

Cf. Martello, S. and Toth, P.: Knapsack Problems: Algorithms and Computer Implementations, ch. 7, John Wiley & Sons, 1990.

x :: Row -> Col -> String Source

x i j, for i = {1, …, m}, j = {1, …, n}, where m stands for the number of items, and n for the number of bins. These “variables” are to be used only within the GAP formulation in lpGAP.

objFun :: ProfitMatrix -> LinFunc String Double Source

Objective function to maximize in lpGAP. It stands for the overall profit accrued by a given distribution of items among bins.

Cf. Martello, S. and Toth, P.: op. cit.

subFunCap :: ProfitMatrix -> Col -> LinFunc String Double Source

Constraint function. It is used, in lpGAP, to specify the capacity of each bin. Note that items are not divisible, and therefore their cost, as detracted from a given bin’s capacity, is fixed at 1.

Cf. Martello, S. and Toth, P.: op. cit.

subFunMult :: ProfitMatrix -> Row -> LinFunc String Double Source

Constraint function. It is used, in lpGAP, to specify how many copies of each item can be distributed.

Cf. Martello, S. and Toth, P.: op. cit.

Formulation accessories

mkProfitMatrix Source

Arguments

:: ProfitFunction a b c
-> [a]	Items
-> [b]	Bins
-> Maybe c	Optional quality
-> ProfitMatrix

Given a ProfitFunction, mkProfitMatrix computes a profit matrix between bins and items, optionally taking a quality as being by default shared between them. The values in a ProfitMatrix serve to distribute items among bins according to the capacities of the latter and the values of the former.

safeMatrix Source

Arguments

:: Row
-> Col
-> ((Row, Col) -> Double)	Specializes the `((Int, Int) -> a)` function used with `matrix`
-> ProfitMatrix

Wrapper to use matrix with extra type safety.

safeGetElem :: ProfitMatrix -> (Row, Col) -> Double Source

Wrapper to use getElem with extra type safety.

Runners and helpers

run_lpGAP :: ProfitMatrix -> [Capacity] -> Bounds Copies -> IO (ReturnCode, Maybe (Double, Map String Double)) Source

Simple helper function to run the glpk-hs interface to GLPK, as constructed with lpGAP. Takes the same arguments as lpGAP.

fromGLPKtoList :: (ReturnCode, Maybe (Double, Map String Double)) -> Maybe [(Col, Row)] Source

fromGLPKtoList turns the (unIOd) output of run_lpGAP into a more usable format.