# OptimalApplication.jl

Optimal college application strategy with homogeneous and heterogeneous application costs.

Basic usage:

```
julia> using OptimalApplication
julia> mkt = SameCostsMarket(
# Probability of getting into each school
[0.2, 0.5, 0.1, 0.6, 0.1],
# Utility values
[1, 4, 9, 1, 8],
# Number of schools `h` to apply to. By nestedness property,
# we can obtain the solution for all `h` by setting `h = m`,
# where `m` is the number of schools in the market.
5
);
julia> x, v = applicationorder_list(mkt)
([2, 3, 5, 4, 1], [2.0, 2.7, 3.24, 3.483, 3.5154])
julia> x[1:4], v[4]
([2, 3, 5, 4], 3.483)
```

This means that when `h = 4`

, the optimal portfolio is `{2, 3, 5, 4}`

and its valuation is `5.408`

.

The function `applicationorder_heap()`

works the same way but uses a different internal data structure and may be faster for certain instances.

Example with varied costs:

```
julia> mkt = VariedCostsMarket(
# Probability of getting into each school
rand(50),
# Utility values
rand(40:60, 50),
# Cost of applying to each school
rand(5:10, 50),
# Budget to spend on applications
100
);
julia> x, v = optimalportfolio_dynamicprogram(mkt)
([50, 49, 48, 47, 46, 45, 44, 43, 42, 41, 40, 38, 35, 28], 59.66127736008859)
```

For a large market like this, we may be content with an ε-approximate solution:

```
julia> x, v = optimalportfolio_fptas(mkt, 0.25)
([26, 46, 50], 59.623041055190996)
```

The value `ε = 0.25`

means that the value is guaranteed to be no worse than `1 - 0.25`

times the value of the optimal portfolio. As we can see above, the typical optimality gap is often much tighter.

The package also includes `optimalportfolio_enumerate()`

and `optimalportfolio_branchbound()`

, which are inefficient algorithms of primarily theoretical interest.

Finally, we can check the expected value of an arbitrary portfolio using `valuation()`

:

```
julia> valuation([20, 16, 35], mkt)
35.33785503577366
```

## arXiv paper

If you found this package useful, please consider citing our arXiv paper. Rolling updates to the paper can be found on the companion repository CollegeApplication.