Wednesday, 15:15 - 15:40 h, Room: H 3005


Noriyoshi Sukegawa
Lagrangian relaxation and pegging test for clique partitioning problems

Coauthors: Yoshitsugu Yamamoto, Liyuan Zhang


We develop a relaxation method to solve the clique partitioning problem (CPP), as it is done customarily by the Lagrangian relaxation, but in a new approach we have aimed at overcoming the burden imposed by the number of constraints. Since the binary integer linear programming formulation of CPP has a huge number of inequality constraints, we propose a modified Lagrangian relaxation which discards some of the multipliers and the modified subgradient method to solve the Lagrangain dual problem defined by the modified Lagrangian relaxation. This modification enables us to apply the Lagrangian relaxation to large instances. Computational results show that only a small fraction of all constraints are considered eventually. We also propose an improvement of the ordinary pegging test by using the structural property of CPP. The pegging test reduces the size of given instances, often significantly, and contributes to finding a very tight upper bound for several instances.


Talk 1 of the contributed session Wed.3.H 3005
"Graph coloring" [...]
Cluster 2
"Combinatorial optimization" [...]


  There are three major facts that should be watched out for in all payday loans in the United States. But it is worth noting that these tests were carried out on the blood cells. Therefore, it's too early to say about scientific evidence of Viagra Without Prescription influence on blood clots.