[Contents]
Toggle当研究室で取り組んでいる研究に関する論文・講演などの情報（一部抜粋）です。
Here is a selection of our published papers on the research we’ve been working on in our laboratory.
Our Selected Papers and Keywords
2022
Kazuho Kanahara, Shun Ito, Kengo Katayama
The performance of a local search based on vertex coloring for the maximum clique problem Proceedings Article
In: ICCCM 2022: Proceedings of the 10th International Conference on Computer and Communications Management, pp. 79-83, 2022.
Abstract | BibTeX | タグ: Local search, Maximum clique problem, Vertex coloring | Links:
@inproceedings{KANAHARA-ICCCM-2022,
title = {The performance of a local search based on vertex coloring for the maximum clique problem},
author = {Kazuho Kanahara and Shun Ito and Kengo Katayama},
doi = {https://doi.org/10.1145/3556223.3556235},
year = {2022},
date = {2022-10-16},
urldate = {2022-10-16},
booktitle = {ICCCM 2022: Proceedings of the 10th International Conference on Computer and Communications Management},
pages = {79-83},
abstract = {The maximum clique problem (MCP) is a fundamental combinatorial optimization problem that has many practical applications. In the exact methods, the idea of approximate coloring of vertices has been employed in the one proposed by Tomita, et al. in 1970's in order to prune unnecessary searching, and it now has become the important idea in the field of developing efficient exact algorithms for solving MCP. On the other hand, in the heuristic and metaheuristic research fields, few heuristics have been presented for MCP that use vertex coloring, and the search performance of a local search using the degree of saturation based on vertex coloring information is not clear. In this paper, we investigate the performance of a Local Search based on vertex coloring for MCP. Experimental results on the benchmark graphs show that the proposed algorithm is more effective than other simple Local Search for several difficult graphs such as perfect graphs.},
keywords = {Local search, Maximum clique problem, Vertex coloring},
pubstate = {published},
tppubtype = {inproceedings}
}
The maximum clique problem (MCP) is a fundamental combinatorial optimization problem that has many practical applications. In the exact methods, the idea of approximate coloring of vertices has been employed in the one proposed by Tomita, et al. in 1970's in order to prune unnecessary searching, and it now has become the important idea in the field of developing efficient exact algorithms for solving MCP. On the other hand, in the heuristic and metaheuristic research fields, few heuristics have been presented for MCP that use vertex coloring, and the search performance of a local search using the degree of saturation based on vertex coloring information is not clear. In this paper, we investigate the performance of a Local Search based on vertex coloring for MCP. Experimental results on the benchmark graphs show that the proposed algorithm is more effective than other simple Local Search for several difficult graphs such as perfect graphs.
Kazuho Kanahara, Tetsuya Oda, Elis Kulla, Akira Uejima, Kengo Katayama
An efficient local search for the maximum clique problem on massive graphs Proceedings Article
In: EIDWT 2022: Advances in Internet, Data & Web Technologies, Proceedings of the 10th International Conference on Emerging Internet, Data & Web Technologies, Lecture Notes on Data Engineering and Communications Technologies (LNDECT, volume 118), pp. 201–211, 2022.
Abstract | BibTeX | タグ: Local search, Massive graphs, Maximum clique problem, Multi-start k-opt local search | Links:
@inproceedings{KANAHARA-EIDWT-2022,
title = {An efficient local search for the maximum clique problem on massive graphs},
author = {Kazuho Kanahara and Tetsuya Oda and Elis Kulla and Akira Uejima and Kengo Katayama},
doi = {https://doi.org/10.1007/978-3-030-95903-6_22},
year = {2022},
date = {2022-02-02},
urldate = {2022-02-02},
booktitle = {EIDWT 2022: Advances in Internet, Data & Web Technologies, Proceedings of the 10th International Conference on Emerging Internet, Data & Web Technologies, Lecture Notes on Data Engineering and Communications Technologies (LNDECT, volume 118)},
pages = {201–211},
abstract = {The Maximum Clique Problem (MCP) is one of the most important combinatorial optimization problems that has many practical applications such as community search in social networks. Since the MCP is known to be NP-hard, much effort has been devoted to the development of metaheuristic algorithms to find a high quality clique (solution) within reasonable running times. The Multi-start k-opt Local Search incorporating k-opt local search (MKLS) is well known as a simple and effective metaheuristic for MCP. However it takes long time to search the high-quality solution for difficult massive graphs such as real world social networks, because the search space is too large. In the case of applying metaheuristic algorithms for massive sparse graphs, adequate process such as reduction process is necessary to focus on promising search space. In this paper, we present a Multi-start k-opt Local Search with graph Reduction process (MKLS-R), for solving the maximum clique problem on massive graphs. MKLS-R is evaluated on difficult massive graphs of Network-Repository graphs. The experimental results showed that the graph reduction process in MKLS-R contributes to the improvement of the search performance of MKLS for the difficult massive graphs.},
keywords = {Local search, Massive graphs, Maximum clique problem, Multi-start k-opt local search},
pubstate = {published},
tppubtype = {inproceedings}
}
The Maximum Clique Problem (MCP) is one of the most important combinatorial optimization problems that has many practical applications such as community search in social networks. Since the MCP is known to be NP-hard, much effort has been devoted to the development of metaheuristic algorithms to find a high quality clique (solution) within reasonable running times. The Multi-start k-opt Local Search incorporating k-opt local search (MKLS) is well known as a simple and effective metaheuristic for MCP. However it takes long time to search the high-quality solution for difficult massive graphs such as real world social networks, because the search space is too large. In the case of applying metaheuristic algorithms for massive sparse graphs, adequate process such as reduction process is necessary to focus on promising search space. In this paper, we present a Multi-start k-opt Local Search with graph Reduction process (MKLS-R), for solving the maximum clique problem on massive graphs. MKLS-R is evaluated on difficult massive graphs of Network-Repository graphs. The experimental results showed that the graph reduction process in MKLS-R contributes to the improvement of the search performance of MKLS for the difficult massive graphs.
2020
Takafumi Miyake, Kengo Katayama, Kazuho Kanahara, Tetsuya Oda
Applying a local search for the uncapacitated p-median problem to the capacitated problem Proceedings Article
In: GCCE 2020: 2020 IEEE 9th Global Conference on Consumer Electronics, pp. 835-836, 2020.
Abstract | BibTeX | タグ: Capacitated p-median problem, Local search | Links:
@inproceedings{MIYAKE-GCCE-2020,
title = {Applying a local search for the uncapacitated p-median problem to the capacitated problem},
author = {Takafumi Miyake and Kengo Katayama and Kazuho Kanahara and Tetsuya Oda},
doi = {10.1109/GCCE50665.2020.9291874},
year = {2020},
date = {2020-10-13},
urldate = {2020-10-13},
booktitle = {GCCE 2020: 2020 IEEE 9th Global Conference on Consumer Electronics},
pages = {835-836},
abstract = {Capacitated p-Median Problem (CPMP) is an important combinatorial optimization problem with practical applications such as determining the location and scale of power generation facilities in green energy field. The objective of CPMP is to find p facilities and assign each area to exactly one facility such that the total distance of assigned areas to their corresponding facilities is minimized, and the capacity limit on the facilities is not exceeded. In the CPMP solution, it is important to satisfy the capacity constraints of all opened facilities. In searching high quality solutions, the effectiveness of allowing the search for infeasible space has not been fully investigated in CPMP. In this paper, we present a novel search approach called Extend Space Strategy (ESS) that extends the search to infeasible space by using algorithms for a simplified and related problem not including major constraints. Computational results show that ESS is more effective to obtain better solutions than the standard approach that searches only feasible space.},
keywords = {Capacitated p-median problem, Local search},
pubstate = {published},
tppubtype = {inproceedings}
}
Capacitated p-Median Problem (CPMP) is an important combinatorial optimization problem with practical applications such as determining the location and scale of power generation facilities in green energy field. The objective of CPMP is to find p facilities and assign each area to exactly one facility such that the total distance of assigned areas to their corresponding facilities is minimized, and the capacity limit on the facilities is not exceeded. In the CPMP solution, it is important to satisfy the capacity constraints of all opened facilities. In searching high quality solutions, the effectiveness of allowing the search for infeasible space has not been fully investigated in CPMP. In this paper, we present a novel search approach called Extend Space Strategy (ESS) that extends the search to infeasible space by using algorithms for a simplified and related problem not including major constraints. Computational results show that ESS is more effective to obtain better solutions than the standard approach that searches only feasible space.
2004
Peter Merz, Kengo Katayama
Memetic algorithms for the unconstrained binary quadratic programming problem Journal Article
In: Biosystems, vol. 78, no. 1, pp. 99-118, 2004, ISSN: 0303-2647.
Abstract | BibTeX | タグ: Combinatorial optimization, Evolutionary algorithm, Fitness landscape analysis, Local search, Memetic algorithms, Unconstrained binary quadratic programming problem | Links:
@article{MERZ-Biosystems-2004,
title = {Memetic algorithms for the unconstrained binary quadratic programming problem},
author = {Peter Merz and Kengo Katayama},
url = {https://www.sciencedirect.com/science/article/pii/S0303264704001376},
doi = {https://doi.org/10.1016/j.biosystems.2004.08.002},
issn = {0303-2647},
year = {2004},
date = {2004-01-01},
urldate = {2004-01-01},
journal = {Biosystems},
volume = {78},
number = {1},
pages = {99-118},
abstract = {This paper presents a memetic algorithm, a highly effective evolutionary algorithm incorporating local search for solving the unconstrained binary quadratic programming problem (BQP). To justify the approach, a fitness landscape analysis is conducted experimentally for several instances of the BQP. The results of the analysis show that recombination-based variation operators are well suited for the evolutionary algorithms with local search. Therefore, the proposed approach includes — besides a highly effective randomized k-opt local search — a new variation operator that has been tailored specially for the application in the hybrid evolutionary framework. The operator is called innovative variation and is fundamentally different from traditional crossover operators, since new genetic material is included in the offspring which is not contained in one of the parents. The evolutionary heuristic is tested on 35 publicly available BQP instances, and it is shown experimentally that the algorithm is capable of finding best-known solutions to large BQPs in a short time and with a high frequency. In comparison to other approaches for the BQP, the approach appears to be much more effective, particularly for large instances of 1000 or 2500 binary variables.},
keywords = {Combinatorial optimization, Evolutionary algorithm, Fitness landscape analysis, Local search, Memetic algorithms, Unconstrained binary quadratic programming problem},
pubstate = {published},
tppubtype = {article}
}
This paper presents a memetic algorithm, a highly effective evolutionary algorithm incorporating local search for solving the unconstrained binary quadratic programming problem (BQP). To justify the approach, a fitness landscape analysis is conducted experimentally for several instances of the BQP. The results of the analysis show that recombination-based variation operators are well suited for the evolutionary algorithms with local search. Therefore, the proposed approach includes — besides a highly effective randomized k-opt local search — a new variation operator that has been tailored specially for the application in the hybrid evolutionary framework. The operator is called innovative variation and is fundamentally different from traditional crossover operators, since new genetic material is included in the offspring which is not contained in one of the parents. The evolutionary heuristic is tested on 35 publicly available BQP instances, and it is shown experimentally that the algorithm is capable of finding best-known solutions to large BQPs in a short time and with a high frequency. In comparison to other approaches for the BQP, the approach appears to be much more effective, particularly for large instances of 1000 or 2500 binary variables.
2001
Kengo Katayama, Hiroyuki Narihisa
Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem Journal Article
In: European Journal of Operational Research, vol. 134, no. 1, pp. 103-119, 2001, ISSN: 0377-2217.
Abstract | BibTeX | タグ: Heuristics, Large-size problems, Local search, Simulated annealing, Unconstrained binary quadratic programming problem | Links:
@article{KATAYAMA-EJOR-2001,
title = {Performance of simulated annealing-based heuristic for the unconstrained binary quadratic programming problem},
author = {Kengo Katayama and Hiroyuki Narihisa},
url = {https://www.sciencedirect.com/science/article/pii/S0377221700002423},
doi = {https://doi.org/10.1016/S0377-2217(00)00242-3},
issn = {0377-2217},
year = {2001},
date = {2001-01-01},
urldate = {2001-01-01},
journal = {European Journal of Operational Research},
volume = {134},
number = {1},
pages = {103-119},
abstract = {The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported.},
keywords = {Heuristics, Large-size problems, Local search, Simulated annealing, Unconstrained binary quadratic programming problem},
pubstate = {published},
tppubtype = {article}
}
The unconstrained binary quadratic programming problem (BQP) is known to be NP-hard and has many practical applications. This paper presents a simulated annealing (SA)-based heuristic for the BQP. The new SA heuristic for the BQP is based on a simple (1-opt) local search heuristic and designed with a simple cooling schedule, but the multiple annealing processes are adopted. To show practical performances of the SA, we test on publicly available benchmark instances of large size ranging from 500 to 2500 variables and compare them with other heuristics such as multi-start local search, the previous SA, tabu search, and genetic algorithm incorporating the 1-opt local search. Computational results indicate that our SA leads to high-quality solutions with short times and is more effective than the competitors particularly for the largest benchmark set. Furthermore, the values of new best-known solutions found by the SA for several large instances are also reported.