Scheduling seminar

Download

schedulingseminar@rtime.felk.cvut.cz

May 2024

1 participants
2 discussions

Matthias Mnich (TU Hamburg) | May 29 | New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
by Zdeněk Hanzálek 27 May '24

27 May '24

Dear scheduling researcher, We are delighted to announce the talk given by Matthias Mnich (TU Hamburg). The title is " New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines ". The seminar will take place on Zoom on Wednesday, May 29 at 13:00 UTC. Please be aware of summertime. Join Zoom Meeting https://cesnet.zoom.us/j/93008634528?pwd=b0JuTWdLaVpINFM3VGZPVFUydzIydz09 Meeting ID: 930 0863 4528 Passcode: 089440 You can follow the seminar online or offline on our Youtube channel as well: https://www.youtube.com/channel/UCUoCNnaAfw5NAntItILFn4A The abstract follows. Mixed-integer linear programming (MILP) is at the core of many advanced algorithms for solving fundamental problems in combinatorial optimization. The complexity of solving MILPs directly correlates with their support size, which is the minimum number of non-zero integer variables in an optimal solution. A hallmark result by Eisenbrand and Shmonin (Oper. Res. Lett., 2006) shows that any feasible integer linear program (ILP) has a solution with support size s ≤ 2m · log(4m∆), where m is the number of constraints, and ∆ is the largest absolute coefficient in any constraint. - Our main combinatorial result are improved support size bounds for ILPs. We show that any ILP has a solution with support size s ≤ m · (log(3∥A∥_1) + \sqrt{log(∥A∥_1)}), where ∥A∥_1 denotes the 1-norm of the constraint matrix A. Our upper bounds also hold with ∥A∥_1 replaced by \sqrt{m∆}, which improves on the previously best constants in the linearized form. - Our main algorithmic result are the fastest known approximation schemes for fundamental scheduling problems, which use the improved support bounds as one ingredient. We design an efficient approximation scheme (EPTAS) for makespan minimization on uniformly related machines (Q||Cmax). Our EPTAS yields a (1 + ε)-approximation for Q||Cmax on N jobs in time 2^{O(1/ε log^3(1/ε) log(log(1/ε)))} + O(N), which improves exponentially over the previously fastest algorithm by Jansen, Klein and Verschae (Math. Oper. Res., 2020). Arguably, our approximation scheme is also simpler than all previous EPTASes for Q||Cmax, as we reduce the problem to a novel MILP formulation with small support size. The next talk in our series will be: Ender Ozcan (Uni of Nottingham) | Jun 12 | Machine Learning meets Selection Hyper-heuristics For more details, please visit https://schedulingseminar.com/ With kind regards Zdenek, Mike and Guohua -- Zdenek Hanzalek Industrial Informatics Department, Czech Institute of Informatics, Robotics and Cybernetics, Czech Technical University in Prague, Jugoslavskych partyzanu 1580/3, 160 00 Prague 6, Czech Republic https://rtime.ciirc.cvut.cz/~hanzalek/

1 0

Matthias Mnich (TU Hamburg) | May 29 | New Support Size Bounds for Integer Programming, Applied to Makespan Minimization on Uniformly Related Machines
by Zdeněk Hanzálek 21 May '24

21 May '24

1 0