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" [...]


  The deal is that Payday Loans Indiana online can save your time, nerves and make a solution of all your financial problems. But at the same time, it acts only with sexual arousal. Viagra Online has a number of advantages in comparison with injections in the sexual organ or other procedures aimed at treatment of impotency.