Tuesday, 16:15 - 16:40 h, Room: H 3012


Yong-Hong Kuo
On the mixed set covering, partitioning and packing problem

Coauthor: Janny M. Y. Leung


Set covering, set partitioning and set packing problems have already been studied for more than 40 years. However, researchers usually consider the problems individually and very few literatures have mentioned the mixed set covering, partitioning and packing problem, where the three kinds of constraints are present simultaneously in the formulation. The problems with such kind of structures play an important role in the real-life applications, e.g., staff scheduling problems. In this talk, we will discuss the polyhedral structure of the problem and present a way, which we call "implicit edges generation'' approach, to further tighten the feasible region and, as a result, makes the LP optimal closer to the IP optimal. We will also present some classes of facet-defining inequalities produced by this approach. Computational results show that, using our proposed methodology, a tighter formulation can be obtained and, consequently significant reductions of computational efforts are made.


Talk 3 of the contributed session Tue.3.H 3012
"LP relaxations" [...]
Cluster 2
"Combinatorial optimization" [...]


  online loans . In this section we give only a brief summary recommendation for admission of Levitra Sale. Full information can be found in the instructions for receiving medications with vardenafil.