Solving the college application problem with Julia

✍️ Max Kapur

📜 Master’s student

🏛️ Management Science/Optimization Lab, Seoul National University

✉️ maxkapur@gmail.com

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.



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

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