[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
2026
Yuki Aoyama, Kengo Katayama
Performance Comparison of Local Searches based on N-neighborhoods for the Job Shop Scheduling Problem Proceedings Article
In: GECCO '26 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion, pp. 1277 - 1284, Association for Computing Machinery, 2026, ISBN: 979-8-4007-2488-6.
Abstract | BibTeX | タグ: Combinatorial optimization, Job shop scheduling problem, Local search, Neighborhood | Links:
@inproceedings{AOYAMA-GECCO-2026,
title = {Performance Comparison of Local Searches based on N-neighborhoods for the Job Shop Scheduling Problem},
author = {Yuki Aoyama and Kengo Katayama},
url = {https://dl.acm.org/doi/10.1145/3795101.3814697},
doi = {https://doi.org/10.1145/3795101.381469},
isbn = {979-8-4007-2488-6},
year = {2026},
date = {2026-08-13},
urldate = {2026-08-13},
booktitle = {GECCO '26 Companion: Proceedings of the Genetic and Evolutionary Computation Conference Companion},
pages = {1277 - 1284},
publisher = {Association for Computing Machinery},
abstract = {The Job-shop Scheduling Problem (JSSP) is a classical combinatorial optimization problem with significant implications for modern high-mix, low-volume manufacturing. Given its NP-hard complexity, local search based on critical-path-oriented neighborhood structures—specifically N5 through N8—has become a cornerstone of state-of-the-art metaheuristics. However, while existing literature focuses on their integration into complex frameworks like Tabu Search, their performance as standalone, basic local search (LS) is not yet fully understood. This obscures whether their efficacy is intrinsic to the neighborhood structures or dependent on the metaheuristic framework. Moreover, as these neighborhoods are nested, the incremental contribution of each additional move operator to objective function improvement has not been rigorously quantified. This paper presents a systematic empirical evaluation of the neighborhoods to elucidate their standalone effectiveness. Through extensive computational experiments on 28 standard benchmark instances, we comprehensively evaluate the impact of typical improvement strategies and neighborhood evaluation orders on search performance. Our findings demonstrate that the N8-based LS consistently outperforms other structures in terms of makespan reduction. Furthermore, a contribution analysis substantiates the practical utility of the nested neighborhood design, establishing the N8 structure as a potent intensification tool for manufacturing scheduling.},
keywords = {Combinatorial optimization, Job shop scheduling problem, Local search, Neighborhood},
pubstate = {published},
tppubtype = {inproceedings}
}
The Job-shop Scheduling Problem (JSSP) is a classical combinatorial optimization problem with significant implications for modern high-mix, low-volume manufacturing. Given its NP-hard complexity, local search based on critical-path-oriented neighborhood structures—specifically N5 through N8—has become a cornerstone of state-of-the-art metaheuristics. However, while existing literature focuses on their integration into complex frameworks like Tabu Search, their performance as standalone, basic local search (LS) is not yet fully understood. This obscures whether their efficacy is intrinsic to the neighborhood structures or dependent on the metaheuristic framework. Moreover, as these neighborhoods are nested, the incremental contribution of each additional move operator to objective function improvement has not been rigorously quantified. This paper presents a systematic empirical evaluation of the neighborhoods to elucidate their standalone effectiveness. Through extensive computational experiments on 28 standard benchmark instances, we comprehensively evaluate the impact of typical improvement strategies and neighborhood evaluation orders on search performance. Our findings demonstrate that the N8-based LS consistently outperforms other structures in terms of makespan reduction. Furthermore, a contribution analysis substantiates the practical utility of the nested neighborhood design, establishing the N8 structure as a potent intensification tool for manufacturing scheduling.
2022
Kazuho Kanahara, Kengo Katayama, Etsuji Tomita
Speeding-up construction algorithms for the graph coloring problem Journal Article
In: IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences, vol. E105.A, no. 9, pp. 1241-1251, 2022, ISSN: 1745-1337.
Abstract | BibTeX | タグ: Combinatorial optimization, Construction algorithm, DSATUR, Graph coloring problem, RLF | Links:
@article{KANAHARA-IEICE-2022,
title = {Speeding-up construction algorithms for the graph coloring problem},
author = {Kazuho Kanahara and Kengo Katayama and Etsuji Tomita},
doi = {10.1587/transfun.2021DMP0011},
issn = {1745-1337},
year = {2022},
date = {2022-09-01},
urldate = {2022-09-01},
journal = {IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences},
volume = {E105.A},
number = {9},
pages = {1241-1251},
abstract = {The Graph Coloring Problem (GCP) is a fundamental combinatorial optimization problem that has many practical applications. Degree of SATURation (DSATUR) and Recursive Largest First (RLF) are well known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph induced by uncolored vertices when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. The purposes of this paper are to propose a degree updating method called Adaptive Degree Updating (ADU for short) that improves the issue, and to evaluate the effectiveness of ADU for DSATUR and RLF on DIMACS benchmark graphs as well as random graphs having a wide range of sizes and densities. Experimental results show that the construction algorithms with ADU are faster than the conventional algorithms for many graphs and that the ADU method yields significant speed-ups relative to the conventional algorithms, especially in the case of large graphs with higher edge density.},
keywords = {Combinatorial optimization, Construction algorithm, DSATUR, Graph coloring problem, RLF},
pubstate = {published},
tppubtype = {article}
}
The Graph Coloring Problem (GCP) is a fundamental combinatorial optimization problem that has many practical applications. Degree of SATURation (DSATUR) and Recursive Largest First (RLF) are well known as typical solution construction algorithms for GCP. It is necessary to update the vertex degree in the subgraph induced by uncolored vertices when selecting vertices to be colored in both DSATUR and RLF. There is an issue that the higher the edge density of a given graph, the longer the processing time. The purposes of this paper are to propose a degree updating method called Adaptive Degree Updating (ADU for short) that improves the issue, and to evaluate the effectiveness of ADU for DSATUR and RLF on DIMACS benchmark graphs as well as random graphs having a wide range of sizes and densities. Experimental results show that the construction algorithms with ADU are faster than the conventional algorithms for many graphs and that the ADU method yields significant speed-ups relative to the conventional algorithms, especially in the case of large graphs with higher edge density.
2005
Kengo Katayama, Akihiro Hamamoto, Hiroyuki Narihisa
An effective local search for the maximum clique problem Journal Article
In: Information Processing Letters, vol. 95, no. 5, pp. 503-511, 2005, ISSN: 0020-0190.
Abstract | BibTeX | タグ: Combinatorial optimization, Graph algorithms, Maximum clique problem, Neighborhood, Variable depth search | Links:
@article{KATAYAMA-IPL-2005,
title = {An effective local search for the maximum clique problem},
author = {Kengo Katayama and Akihiro Hamamoto and Hiroyuki Narihisa},
url = {https://www.sciencedirect.com/science/article/pii/S0020019005001444},
doi = {https://doi.org/10.1016/j.ipl.2005.05.010},
issn = {0020-0190},
year = {2005},
date = {2005-01-01},
urldate = {2005-01-01},
journal = {Information Processing Letters},
volume = {95},
number = {5},
pages = {503-511},
abstract = {We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.},
keywords = {Combinatorial optimization, Graph algorithms, Maximum clique problem, Neighborhood, Variable depth search},
pubstate = {published},
tppubtype = {article}
}
We propose a variable depth search based algorithm, called k-opt local search (KLS), for the maximum clique problem. KLS efficiently explores the k-opt neighborhood defined as the set of neighbors that can be obtained by a sequence of several add and drop moves that are adaptively changed in the feasible search space. Computational results on DIMACS benchmark graphs indicate that KLS is capable of finding considerably satisfactory cliques with reasonable running times in comparison with those of state-of-the-art metaheuristics.
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.