Referees.Solver.Internal

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

Solving the Generalized Assignment Problem by approximation with GLPK

Formulation of the problem for GLPK

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

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

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

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

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

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

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

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

Wrapper to use getElem with extra type safety.

Runners and helpers

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

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)]

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