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.49808266633844134, 0.8771260796827868, 0.8481567273380942, 0.6368943482257573, 0.42971818696865494, 0.05306934508166883, 0.077088698455971, 0.46614064907670116, 0.3191845027990856, 0.6365661033566812, 0.782199173057167, 0.47653413093692076, 0.27868144310763165, 0.4403363585361546, 0.8303828847311476], [65, 65, 65, 66, 67, 67, 69, 70, 72, 72, 73, 75, 76, 78, 79], [9, 9, 9, 9, 10, 7, 8, 6, 5, 5, 5, 10, 6, 6, 7], 55, [10, 11, 12, 4, 8, 15, 1, 9, 7, 13, 3, 5, 6, 2, 14])

Enumeration solver

We can solve this problem using optimalportfolio_enumerate:

optimalportfolio_enumerate(mkt)

([11, 9, 13, 3, 5, 6, 2, 14], 78.46721253747991)

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)

([3, 14, 13, 2, 11, 6, 5, 9], 78.46721253747991)

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)

([14, 2, 6, 5, 3, 13, 9, 11], 78.46721253747991)

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)

([14, 2, 6, 3, 13, 11], 78.33896078641283)

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)

([11, 12, 9, 13, 3, 2, 14], 78.29511382658247)

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

optimalportfolio_simulatedannealing(mkt)

([11, 9, 13, 3, 5, 6, 2, 14], 78.46721253747991)