School assignment optimization problem

[angerona]

How would you approach the following problem:

You have N students to place into M schools. Each school has a limited number of spaces, such that the total number of spaces in all schools is equal to or more than N. Each student ranks k schools according to their preferences (k

Comments

[danillo]

так как у тебя много хитрых ограничений, то я бы не полез во всякие "graph matching" a сделал бы что-нибудь на основе "greedy" подхода.

1)написал бы "objective function" для оптимизации, -- как оценивается какой-либо расклад студентов по школам по шкале от 0 до 1.

2)Изначально все школы пустые. Нужно брать студентов по одному (случайным образом) и класть их в такую кучку, чтобы получить максимальное значение для этой функции и не нарушать дополнительные ограничения. Когда студенты закончатся -- получится приблизительный расклад (понятное дело, он зависит от порядка выбора студентов).

3) прогнал бы (2) сто миллионов раз и выбрал бы десять лучших результатов.

4) Попытался бы десять результатов слить в один -- либо вручную, либо случайными перестановками.

Ну, и на это сверху можно навернуть кучу всяких дополнительных украшений.

[igorlord]

What you need is use "simulated annealing" algorithms. http://en.wikipedia.org/wiki/Simulated_annealing

Basically, you start with the best approximation you can (your #2 run).

Then,

#3 - Remove a random set of students and reassign them via your #2. If your new objective function value is better, keep this assignment; otherwise, revert to the initial.

#4 - repeat #3, changing the random set size according to the annealing schedule you pick.

[danillo]

да, кстати, хорошая идея

хотя я к "simulated annealing" всегда с подозрением относился -- его обычно пытаются использовать, как панацею от всех бед. Но для данного случая как раз хорошо подходит.

[angerona]

а вот какая бы у тебя была optimization function? Мне именно интересно, что в этом случае получается у компании полная свобода в выборе оптимизации (поставить ли как можно больше детей в хоть одну из их выбранных школ, или так, чтоб максимизировать количество детей в их #1 школе...) -- потому что руководство не знает/не интерисуется/не понимает, что есть разница.

Интересно про "прогнать 2 миллиона раз..." -- вот делают ли они что-то такое подобное?

[krl_pgh]

Я сразу подумала, как интересно было бы эту программу оптимизации тестировать :-).

[angerona]

кому что :). А как насчет быть подопытным одним из зеленых/сиреневых студентов? :)

[krl_pgh]

Зависит от результата оптимизации. Если мой зеленый или сиреневый студент в результате окажется в школе, которая меня устраивает, то оптимизация прошла успешно :-).

[pro_sha]

I always think about brute force approaches. It is just easier to think about them.
Randomly pick students and check for restrictions. Assign to the best while not violating the requirements. If you stick with 65/35 distribution as the requirement than you would not violate it at the end of the process (you will not end up with a wrong distribution at the end).

[angerona]

Yes, that's called a greedy approach.

[pro_sha]

Yeap and it is not really an optimization :)

[anonymous]

Check references to chapter 6.
http://fmwww.bc.edu/ec-j/s2008/EC802.pdf

[angerona]

pretty cool. I'll have to try to find

Pathak and S¨onmez (2006), “Leveling the Playing Field: Sincere
and Strategic Players in the Boston Mechanism”

and
Ergin and S¨onmez (2006), “Games of School Choice under the
Boston Mechanism,” Journal of Public Economics, 90, 215-237.

It's all the same guy -- Sonmez, perhaps he's actually invovled in doing it, too

[danillo]

ага, далеко ходить на надо

http://www2.bc.edu/~sonmezt/

He does!

[anonymous]

Sonmez - профессор в Boston College. Я слушала этот курс в прошлом году. Он - один из главных в этой науке. Сейчас, насколько я понимаю, занимается kidney exchange в основном. Но раньше он точно школами занимался. Например, он участвовал в отмене Boston Mechanism в бостонской школьной системе.
Аня (что-то мне лень регистрироваться)

[danillo]

кстати, а кому они в нашем городке эти данные аутсорсят? А то можно подрядиться на общественных началах.

[angerona]

не знаю, можно узнать, но мне говорили, что аутсорсят. Было б действительно интересно прогнать по другим алгоритмам.

У них таки получается довольно большой процент людей в first choice, но как результат -- и большущий процент (на мой взгляд) тех, кому ни один из их choices не достается.