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

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

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