研究者詳細 - 番原　睦則

論文 - 番原　睦則

分割表示 >> ／全件表示 26 件中 1 - 26 件目

Solving Rep-Tile by Computers: Performance of Solvers and Analyses of Solutions

Mutsunori Banbara, Kenji Hashimoto, Takashi Horiyama, Kosuke Oguri, Shin-ichi Minato, Masaaki Nishino, Masahiko Sakai, Ryuhei Uehara, Yushi Uno, and Norihito Yasuda

Algorithmic Foundations for Social Advancement: Recent Progress on Theory and Practice 頁： 187 - 207 2025年3月

Dominating Set Reconfiguration with Answer Set Programming 査読有り国際共著

Masato Kato, Torsten Schaub, Takehide Soh, Naoyuki Tamura, Mutsunori Banbara

THEORY AND PRACTICE OF LOGIC PROGRAMMING 24 巻 ( 4 ) 頁： 755 - 771 2025年1月

Fast enumeration of all cost-bounded solutions for combinatorial problems using ZDDs 査読有り国際誌

Shin-ichi Minato, Jun Kawahara, Mutsunori Banbara, Takashi Horiyama, Ichigaku Takigawa, Yutaro Yamaguchi

DISCRETE APPLIED MATHEMATICS 360 巻頁： 467 - 486 2025年1月

記述言語：英語掲載種別：研究論文（学術雑誌）出版者・発行元：Discrete Applied Mathematics

We propose a fast method for exactly enumerating a large number of all cost-bounded solutions for combinatorial problems using Zero-suppressed Binary Decision Diagrams (ZDDs). Enumerating cost-bounded solutions is an important task to know the exact ranking of any given solution, and it enables statistical p-value evaluation and quality-controlled random sampling. Our method is based on a backtracking search for a given ZDD representing the set of all feasible solutions. The key idea is to integrate “BDD operation cache” technique and “interval-memoizing” technique with a depth-first manner of backtracking procedure. The computation time of the algorithm is empirically bounded by the input and output sizes of ZDDs. It can be significantly faster than existing enumeration systems, especially when the input and output ZDDs are well-compressed and the range of the cost constraint is large. As application examples, we applied our method to a set of difficult instances of the Hamiltonian cycle/path problems. Although it is NP-hard to find any one feasible solution without cost constraints, we tried more difficult problems to enumerate all cost-bounded solutions, and succeeded in implicitly enumerating all cost-bounded solutions for many nontrivial instances which contain billions of solutions. As cost constraints often appear in many real-life situations, our method will be useful in various fields, including data mining, statistical testing, hardware/software design, and many other operations research problems.

DOI： 10.1016/j.dam.2024.10.003

Web of Science

Scopus

Large Neighborhood Prioritized Search for Combinatorial Optimization with Answer Set Programming 査読有り国際共著

Irumi Sugimori, Katsumi Inoue, Hidetomo Nabeshima, Torsten Schaub, Takehide Soh, Naoyuki Tamura, Mutsunori Banbara

Proceedings of the 21st International Conference on Principles of Knowledge Representation and Reasoning (KR 2024) 頁： 765 - 776 2024年11月

担当区分：最終著者,　責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

We propose Large Neighborhood Prioritized Search (LNPS) for solving combinatorial optimization problems in Answer Set Programming (ASP). LNPS is a metaheuristic that starts with an initial solution and then iteratively tries to find better solutions by alternately destroying and prioritized searching for a current solution. Due to the variability of neighborhoods, LNPS allows for flexible search without strongly depending on the destroy operators. We present an implementation of LNPS based on ASP. The resulting heulingo solver demonstrates that LNPS can significantly enhance the solving performance of ASP for optimization. Furthermore, we establish the competitiveness of our LNPS approach by empirically contrasting it to (adaptive) large neighborhood search.

DOI： 10.24963/kr.2024/72

Scopus

ASP-Based Large Neighborhood Prioritized Search for Course Timetabling 査読有り国際共著

Irumi Sugimori, Katsumi Inoue, Hidetomo Nabeshima, Torsten Schaub, Takehide Soh, Naoyuki Tamura, Mutsunori Banbara

Proceedings of the 17th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2024) LNAI 15245 巻頁： 57 - 70 2024年10月

担当区分：最終著者,　責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）

We develop an approach to solve curriculum-based course timetabling (CB-CTT) problems with Large Neighborhood Prioritized Search (LNPS) based on Answer Set Programming (ASP). LNPS is a metaheuristic that starts with an initial solution and then iteratively tries to obtain improved solutions by alternately destroying and prioritized searching for a current solution. Our approach relies on high-level domain-specific LNPS configurations for efficient CB-CTT solving, and both the grounding and solving tasks are delegated to a heuristically-driven answer set optimizer implementing the LNPS algorithm. The resulting system teaspoon-lnps demonstrates that LNPS can significantly enhance the solving performance of ASP for CB-CTT solving. Furthermore, we show the competitiveness of our declarative approach by empirically contrasting it to the best known bounds obtained by more dedicated algorithms.

DOI： 10.1007/978-3-031-74209-5_5

Scopus

Combinatorial Reconfiguration with Answer Set Programming: Algorithms, Encodings, and Empirical Analysis 査読有り国際共著

Yuya Yamada, Mutsunori Banbara, Katsumi Inoue, Torsten Schaub, and Ryuhei Uehara

Proceedings of the 18th International Conference and Workshops on Algorithms and Computation (WALCOM 2024) LNCS 14549 巻頁： 242 - 256 2024年2月

On the Computational Complexity of Generalized Common Shape Puzzles 査読有り

Mutsunori Banbara, Shin-Ichi Minato, Hirotaka Ono, and Ryuhei Uehara

Proceedings of the 49th International Conference on Current Trends in Theory and Practice of Computer Science (SOFSEM 2024) 14519 LNCS 巻頁： 55 - 68 2024年2月

SAF: SAT-based Attractor Finder in Asynchronous Automata Networks 査読有り国際共著

Proceedings of the 21st International Conference on Computational Methods in Systems Biology (CMSB 2023) LNCS 14137 巻頁： 175 - 183 2023年9月

Hamiltonian Cycle Reconfiguration with Answer Set Programming 査読有り国際共著

Takahiro Hirate, Mutsunori Banbara, Katsumi Inoue, Xiao-Nan Lu, Hidetomo Nabeshima, Torsten Schaub, Takehide Soh, and Naoyuki Tamura

Proceedings of the 18th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2023) 14281 LNAI 巻頁： 262 - 277 2023年9月

担当区分：責任著者記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

The Hamiltonian cycle reconfiguration problem is defined as determining, for a given Hamiltonian cycle problem and two among its feasible solutions, whether one is reachable from another via a sequence of feasible solutions subject to certain transition constraints. We develop an approach to solving the Hamiltonian cycle reconfiguration problem based on Answer Set Programming (ASP). Our approach relies on a high-level ASP encoding and delegates both the grounding and solving tasks to an ASP-based solver. To show the effectiveness of our approach, we conduct experiments on the benchmark set of Flinders Hamiltonian Cycle Project.

DOI： 10.1007/978-3-031-43619-2_19

Scopus

その他リンク： https://link.springer.com/chapter/10.1007/978-3-031-43619-2_19

Recongo: Bounded Combinatorial Reconfiguration with Answer Set Programming 査読有り国際共著

Yuya Yamada, Mutsunori Banbara, Katsumi Inoue, and Torsten Schaub

Proceedings of the 18th Edition of the European Conference on Logics in Artificial Intelligence (JELIA 2023) 14281 LNAI 巻頁： 278 - 286 2023年9月

記述言語：英語掲載種別：研究論文（国際会議プロシーディングス）出版者・発行元：Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

DOI： 10.1007/978-3-031-43619-2_20

Scopus

その他リンク： https://link.springer.com/chapter/10.1007/978-3-031-43619-2_20

SAT-based Method for Finding Attractors in Asynchronous Multi-valued Networks 査読有り国際共著

Takehide Soh, Morgan Magnin, Daniel Le Berre, Mutsunori Banbara and Naoyuki Tamura

Proceedings of the 14th International Conference on Bioinformatics Models, Methods and Algorithms (BIOINFORMATICS 2023) 2023年2月

Solving Vehicle Equipment Specification Problems with Answer Set Programming 査読有り国際共著

Raito Takeuchi, Mutsunori Banbara, Naoyuki Tamura, and Torsten Schaub

Proceedings of the 25th International Symposium on Practical Aspects of Declarative Languages (PADL 2023) 頁： 232 - 249 2023年1月

teaspoon: Solving the Curriculum-Based Course Timetabling Problems with Answer Set Programming 査読有り

Mutsunori Banbara, Katsumi Inoue, Benjamin Kaufmann, Tenda Okimoto, Torsten Schaub, Takehide Soh, Naoyuki Tamura, and Philipp Wanko

Annals of Operations Research 275 巻 ( 1 ) 頁： 3–37 2019年4月

Solving Multiobjective Discrete Optimization Problems with Propositional Minimal Model Generation 査読有り

Takehide Soh, Mutsunori Banbara, Naoyuki Tamura, Daniel Le Berre

Proceedings of the 23rd International Conference on Principles and Practice of Constraint Programming (CP 2017), Lecture Notes in Computer Science 10416 巻頁： 596-614 2017年8月

Clingcon: The Next Generation 査読有り

Mutsunori Banbara, Benjamin Kaufmann, Max Ostrowski, and Torsten Schaub

Theory and Practice of Logic Programming 17 巻 ( 4 ) 頁： 408-461 2017年7月

catnap: Generating Test Suites of Constrained Combinatorial Testing with Answer Set Programming 査読有り

Mutsunori Banbara, Katsumi Inoue, Hiromasa Kaneyuki, Tenda Okimoto, Torsten Schaub, Takehide Soh, Naoyuki Tamura

Proceedings of the 14th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2017), Lecture Notes in Artificial Intelligence 10377 巻頁： 265-278 2017年6月

Proposal and Evaluation of Hybrid Encoding of CSP to SAT Integrating Order and Log Encodings 査読有り

Takehide Soh, Mutsunori Banbara and Naoyuki Tamura

International Journal on Artificial Intelligence Tools 26 巻 ( 1 ) 2017年2月

teaspoon: Solving the Curriculum-Based Course Timetabling Problems with Answer Set Programming 査読有り

Mutsunori Banbara, Katsumi Inoue, Benjamin Kaufmann, Torsten Schaub, Takehide Soh, Naoyuki Tamura, Philipp Wanko

Proceedings of the 11th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2016) 頁： 13-32 2016年8月

\sum_x-Optimal Solutions in Highly Symmetric Multi-Objective Timetabling Problems 査読有り

Maxime Clement, Tenda Okimoto, Katsumi Inoue, Mutsunori Banbara

Proceedings of the 11th International Conference on the Practice and Theory of Automated Timetabling (PATAT 2016) 頁： 63-79 2016年8月

A Hybrid Encoding of CSP to SAT Integrating Order and Log Encodings 査読有り

Takehide Soh, Mutsunori Banbara, Naoyuki Tamura

Proceedings of the 27th IEEE International Conference on Tools with Artificial Intelligence (ICTAI 2015) 頁： 421-428 2015年11月

aspartame: Solving Constraint Satisfaction Problems with Answer Set Programming 査読有り

Mutsunori Banbara, Martin Gebser, Katsumi Inoue, Max Ostrowski, Andrea Peano, Torsten Schaub, Takehide Soh, Naoyuki Tamura, Matthias Weise

Proceedings of the 13th International Conference on Logic Programming and Nonmonotonic Reasoning (LPNMR 2015), Lecture Notes in Artificial Intelligence 9345 巻頁： 112-126 2015年9月

Incremental SAT-based Method with Native Boolean Cardinality Handling for the Hamiltonian Cycle Problem 査読有り

Takehide Soh, Daniel Le Berre, Stephanie Roussel, Mutsunori Banbara, Naoyuki Tamura

Proceedings of the 14th European Conference on Logics in Artificial Intelligence (JELIA 2014), Lecture Notes in Artificial Intelligence 8761 巻頁： 684-693 2014年9月

Answer Set Programming as a Modeling Language for Course Timetabling 査読有り

Mutsunori Banbara, Takehide Soh, Naoyuki Tamura, Katsumi Inoue and Torsten Schaub

Theory and Practice of Logic Programming 13 巻 ( 4-5 ) 頁： 783-798 2013年7月

A SAT-Based Method for Solving the Two-dimensional Strip Packing Problem 査読有り

Takehide Soh, Katsumi Inoue, Naoyuki Tamura, Mutsunori Banbara and Hidetomo Nabeshima

Fundamenta Informaticae 102 巻 ( 3-4 ) 頁： 467-487 2010年

Compiling finite linear CSP into SAT 査読有り

Naoyuki Tamura, Akiko Taga, Satoshi Kitagawa, and Mutsunori Banbara

CONSTRAINTS 14 巻 ( 2 ) 頁： 254-272 2009年6月

A Competitive and Cooperative Approach to Propositional Satisfiability 査読有り

Katsumi Inoue, Takehide Soh, Seiji Ueda, Yoshito Sasaura, Mutsunori Banbara, and Naoyuki Tamura

Discrete Applied Mathematics 154 巻 ( 16 ) 頁： 2291-2306 2006年11月

　前のページ - 次のページ　

<番原 睦則>

論文 - 番原 睦則

<番原　睦則>

論文 - 番原　睦則