## OptimalApplication.jl

Exact, approximate, and heuristic algos for the college application problem.
Author maxkapur
Popularity
2 Stars
Updated Last
1 Year Ago
Started In
February 2022

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

### Used By Packages

No packages found.