Working with varied-costs markets

The varied-costs market is the general case of the college application problem in which schools may have different application costs. The optimization problem is as follows:

\[ \begin{align*} \text{maximize}\quad & v(\mathcal{X}) = \sum_{j\in \mathcal{X}} \Bigl( f_j t_j \prod_{\substack{i \in \mathcal{X}: \\ i > j}} (1 - f_{i}) \Bigr) \\ \text{subject to}\quad & \mathcal{X} \subseteq \mathcal{C}, ~~\sum_{j\in \mathcal{X}} g_j \leq H \end{align*}\]

Let's consider a random instance of this problem with $m = 15$ schools.

using OptimalApplication
f = rand(15)
t = rand(60:80, 15)     # must be integers
g = rand(5:10, 15)      # must be integers
H = sum(g) ÷ 2
mkt = VariedCostsMarket(f, t, g, H)

VariedCostsMarket(15, [0.7024670873214487, 0.706491578543984, 0.4522435711488295, 0.13036414632936955, 0.2274065558102092, 0.9511714847607354, 0.813120017152639, 0.2872600257164116, 0.2581261100255652, 0.603685152258545, 0.12244046880352832, 0.2697835997582022, 0.622824761279225, 0.5704230289981732, 0.3982816295846624], [61, 62, 69, 71, 71, 71, 71, 71, 73, 73, 75, 77, 77, 78, 79], [5, 8, 9, 6, 8, 8, 6, 7, 5, 10, 6, 6, 5, 8, 5], 51, [1, 14, 5, 4, 9, 11, 13, 15, 2, 8, 6, 7, 12, 3, 10])

Enumeration solver

We can solve this problem using optimalportfolio_enumerate:

optimalportfolio_enumerate(mkt)

([11, 13, 8, 7, 12, 3, 10], 77.78032260266107)

This function returns the optimal portfolio as a vector X of school indices, and its valuation v.

A somewhat better kind of enumeration the branch-and-bound scheme, implemented as optimalportfolio_branchbound:

optimalportfolio_branchbound(mkt)

([13, 12, 10, 3, 11, 7, 8], 77.78032260266107)

We can see that the results are the same (up to permutation).

Fast solver

OptimalApplication implements a dynamic program that solves this problem exactly in pseudopolynomial-time. The computation time of optimalportfolio_dynamicprogram depends on the values of $g_j$; smaller is better.

optimalportfolio_dynamicprogram(mkt)

([10, 3, 12, 7, 8, 13, 11], 77.78032260266107)

Approximation algorithms

The college application problem admits a fully polynomial-time approximation scheme (FPTAS). Given a market and tolerance $\varepsilon$, optimalportfolio_fptas(mkt, ε): produces a solution that is guaranteed to have an objective value of at least $1 - \varepsilon$ times the optimum, in time $O(m^3 / \varepsilon)$.

optimalportfolio_fptas(mkt, 0.2)

([10, 3, 12, 7, 8, 11, 1], 77.75982156514205)

Heuristic algorithms

OptimalApplication also includes two heuristic algorithms. Although they offer no accuracy guarantee, their computation time is low and they can be quite effective in practice.

optimalportfolio_greedy adds schools in descending order by f_j t_j / g_j until the budget is exhausted.

optimalportfolio_greedy(mkt)

([1, 14, 11, 13, 12, 3, 10], 77.54182688293241)

optimalportfolio_simulatedannealing starts with the greedy solution, then searches locally according to a randomized scheme for an improvement.

optimalportfolio_simulatedannealing(mkt)

([11, 13, 8, 7, 12, 3, 10], 77.78032260266107)