# \[ANN\] OptimalApplication.jl: Exact, approximate, and heuristic algorithms for the college application problem

**URL:** <https://discourse.julialang.org/t/ann-optimalapplication-jl-exact-approximate-and-heuristic-algorithms-for-the-college-application-problem/83556>\
**Category:** Package Announcements\
**Tags:** package, announcement, optimization\
**Created:** [June 30, 2022, 8:35am UTC](https://discourse.julialang.org/t/ann-optimalapplication-jl-exact-approximate-and-heuristic-algorithms-for-the-college-application-problem/83556 "2022-06-30T08:35:48Z")\
**Posts on this page:** 1\
**Page:** 1

<div class="post-metadata">

**Author:** ![maxkapur](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/maxkapur/32/21208_2.png) [@maxkapur](https://discourse.julialang.org/u/maxkapur)\
**Post date:** [June 30, 2022, 8:35am UTC](https://discourse.julialang.org/t/ann-optimalapplication-jl-exact-approximate-and-heuristic-algorithms-for-the-college-application-problem/83556/1 "2022-06-30T08:35:48Z")

</div>

## The college application problem

… is a combinatorial portfolio optimization problem. It involves **deciding which colleges you should apply to,** given each school’s

- **probability** of admission,
- **utility** payoff, and
- **application fee,**

and an overall **budget** to spend on applications.

The problem is interesting because of its unique “maximax” form: Since the student’s utility is the utility associated with the _best_ school she gets into, the objective is to _maximize the expected maximum_ of a set of random variables. It has applications in job recruiting, investment pitches, and other competitive matching games.

## OptimalApplication.jl

… is a Julia package that provides **exact, approximate, and heuristic solvers** for the college application problem. Here is the [Github repo](https://github.com/maxkapur/OptimalApplication.jl) and the [documentation](https://maxkapur.com/OptimalApplication.jl/stable/). You can install it with `]install OptimalApplication`.

In typical cases, the best exact solver is `optimalportfolio_dynamicprogram`, which works as follows.

```julia
julia> using OptimalApplication
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> optimalportfolio_dynamicprogram(mkt)
([24, 23, 20, 48, 39, 17, 49, 44, 5, 1, 37, 31, 28, 13], 59.97580921925439)

```

`x` is the vector of schools to apply to, and `v` is the expected utility associated with this application portfolio.

For big instances, we may have to settle for an approximate solution. `optimalportfolio_fptas` produces a solution guaranteed to have an objective value at least `1 - ε` that of the global optimum, where `ε` is up to you! Using the same instance as above with `ε = 0.05`,

```julia
julia> optimalportfolio_fptas(mkt, 0.05) 
([24, 23, 20, 39, 17, 49, 13], 59.971909537915664)

```

(The computation time is proportional to `1/ε`.)

An important **special case** of the college application problem arises when every school has the same application fee. In this case, the budget is equivalent to a limit on the _number_ of schools you can apply to, and the optimal portfolios satisfy a special _nestedness_ property, which means that you can get the optimal application portfolios of every size, all in one go using a `SameCostsMarket` and `applicationorder_list` or `applicationorder_heap`.

## Feedback welcome

I am a theoretician by training, not a programmer. **I welcome feedback on ways to improve the OptimalApplication.jl interface as well as the underlying code.**

Try installing the package and running `]test OptimalApplication` and let me know if any tests fail. Many of the tests involve generating random problems and verifying that the math (i.e. the convergence properties of the algorithms) checks out, so the more samples I can get, the better.

You can submit PRs on GitHub or message me here on Discourse. I will also be giving a poster presentation about OptimalApplication.jl at JuliaCon next month.

## Theoretical background

In a sense, the college application problem is a static version of Martin Weitzman’s [Pandora’s Box Problem (paywall)](https://www.jstor.org/stable/1910412). The difference is that instead of opening the boxes one at a time, you have to decide at the outset which set of boxes to open.

A problem reducible to the same-costs case of the college application problem appeared as a subproblem in [Chao Fu’s equilibrium analysis (paywall)](https://www.journals.uchicago.edu/doi/10.1086/675503) of the US college market. Her estimation task dealt with a small instance of the problem that could be solved by enumeration (although she doesn’t identify the solution mechanism explicitly).

We can show that the objective function of the college application problem is a [submodular set function](https://en.wikipedia.org/wiki/Submodular_set_function).

[In my MS thesis](https://github.com/maxkapur/CollegeApplication), I analyze the computational complexity of the college application problem and prove the convergence of the algorithms above. My thesis also includes lots of numerical examples, plots, a benchmark of OptimalApplication.jl, and a few notes on the implementation.