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

Warning

Enumeration algorithms have exponential time complexity and should only be used in small instances with m ≤ 20. Their intended use is to test the validity of more-efficient solvers.

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

Setting the tolerance ε to an extremely small value requires lots of system memory.

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)