LAPORTE, Mr Luc (2020) Coupe {0,1/2} pour le set-cover PRE - Research Project, ENSTA.



In order to solve the P-center problem, we can carry out aresolution with a dichotomy using the set-cover. The set-cover consists of the cover of an ensemble, minimizingthe number of subensemble which are used. Thisoptimization problem can be solve with a linear programwith integers. However, in order to speed up the resolutionof this linear program with integers, we desire to generate{0,12}-cuts. Then we have developped an heuristic methodin order to generate those cuts, because the generation ofthose cuts with a linear program with integers is possible,but it takes longer to generate them. However even thoughtthe cuts that have been generated are usable, they don’tmanage to speed up the resolution of the problem, becausethe are not necessarily the most efficient.

Item Type:Thesis (PRE - Research Project)
Subjects:Mathematics and Applications
ID Code:8195
Deposited By:Luc Laporte
Deposited On:23 avr. 2021 14:39
Dernière modification:23 avr. 2021 14:39

Repository Staff Only: item control page