Solving hard optimization problems of packing, covering, and tiling via clique search
Solving hard optimization problems of packing, covering, and tiling via clique search
Oct 7, 2024 23 views 
0.25
0.5
0.75
1.25
1.5
1.75
2
In the paper we propose to convert NP-hard combinatorial optimization problems of packing, covering, and tiling types into maximum or k-clique problems. The key step is to come up with a tactically constructed auxiliary graph whose maximum or k-cliques correspond to the sought combinatorial structure. As an example, we will consider the problem of packing a given cube by copies of a brick. The aim of the paper is two fold to illustrate (i) the modeling power and (ii) the feasibility of the clique approach. Since theoretical tools are not readily available to study the effectiveness of the solution of the resulting clique problems we will carry out carefully conducted numerical experiments.