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

Package Announcements
, ,
1

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 and the documentation. You can install it with ]install OptimalApplication.

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

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

In my MS thesis, 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.

14 Likes