# 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.4829065454107446, 0.6478021701445329, 0.3369089883124584, 0.1363669029056339, 0.009742056132721832, 0.887684716184415, 0.6699803616600022, 0.7410772282313656, 0.2276191525858875, 0.6913064625823016, 0.07955478769148339, 0.004960968117211029, 0.6209744728006577, 0.46058366485426216, 0.277366448729782], [60, 61, 61, 63, 63, 68, 69, 70, 70, 70, 73, 73, 76, 76, 79], [8, 5, 7, 5, 7, 6, 10, 8, 5, 9, 9, 9, 5, 7, 7], 53, [11, 6, 14, 7, 9, 5, 8, 2, 12, 13, 3, 15, 1, 10, 4])

# Enumeration solver

We can solve this problem using optimalportfolio_enumerate:

optimalportfolio_enumerate(mkt)
([5, 8, 2, 13, 1, 10, 4], 75.90016330881208)

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)
([5, 1, 10, 4, 2, 13, 8], 75.9001633088121)

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)
([4, 10, 1, 13, 2, 8, 5], 75.90016330881208)

# 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)
([4, 10, 1, 2, 5, 6], 75.74674175260917)
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)
([6, 5, 8, 2, 13, 1, 10], 74.73429694524671)

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

optimalportfolio_simulatedannealing(mkt)
([5, 8, 2, 13, 1, 10, 4], 75.90016330881208)