OptimalApplication.jl

Solving the college application problem with Julia

The college application problem

Try to decide which colleges to apply to, given

• the utility associated with each school,
• the probability of being admitted,
• each school’s application fee, and
• a total budget to spend on applications.

Maximizing the expected maximum of a portfolio of random variables: a challenging combinatorial optimization problem.

Summary of solution algorithms

Special case: All application fees equal. applicationorder_list() and applicationorder_heap() are quadratic-time algorithms.

General case:

• Exact solution from optimalportfolio_dynamicprogram() or optimalportfolio_branchbound().
• ε-approximate solution from optimalportfolio_fptas().
• Heuristic solution from optimalportfolio_simulatedannealing().

Why Julia?

Multiple dispatch, parametric types ⇒ easy to accept different kinds of user input and preserve type stability

Easy to parallelize validation study with @threads

Simplicity of creating and sharing packages

Future work

OptimalApplication.jl could be a lot more generic, e.g. accept DataFrames.jl series as input.

Integrate with Bonobo.jl to handle more sophisticated constraint structures that arise in real-world admissions markets.

Graphical interface/web app.

Links

OptimalApplication.jl:

• ]install OptimalApplication
• Source code and documentation on GitHub.

Theory: github.com/maxkapur/CollegeApplication hosts an arXiv paper and various conference slides (including these).

Me: Julia Discourse, LinkedIn, GitHub, personal blog.