Wednesday, January 8, 2020

reached optimum and silver medal on santa 2019 kaggle

Found an optimum with xpress solver on interesting MIP problem,

Here is a way I approached optimum:
69400: iterative solution (about 5 iterations) based on cbc_solver and heuristics.
cbc_solver optimized only preference cost (used 5000x5 variables milp formulation),
also daily occupancies were constrained by (prev_iteration_daily_occupancies-band,prev_iteration_daily_occupancies+band), where band=[6-8]
heuristics was simular to @xhlulu kernel but in c++ choosing subsets of size <= 9, limiting family choices to choice_0,choice_1,choice_2.
69197: reached with cplex solver within two hours (actually was limited by two hours of usage in watson studio cloud)
used milp formulation simular to @hengck23 (100x176x176), removed vars with acc cost>6020
and also vars which are out of (optimal_lp_solution_daily_occupancy - band, optimal_lp_solution_daily_occupancy + band) where band = 60
total about 1.5M variables,
seeded with 69400 solution
68910: reached with xpress solver in 8 hours with reduced milp formulation simular to 69197 (band=80)
seeded with 69197 solution,
68888.04: reached with xpress solver in 8 hours with full milp formulation simular to @hengck23 (removed vars with acc cost>6020)
seeded with 68910 solution,
P.S. It was crucial to seed solver with good solution, reduce number of variables in formulation as much as possible and use a good commercial solver. I am not from academia, so could not get license for cplex or gurobi, lucky enough to get free 1 month full license for xpress on artelys.com:)

No comments:

Post a Comment