Information and Communication Sciences

Miyamoto Yuichiro

  (宮本 裕一郎)

Profile Information

Affiliation
Associate Professor, Faculty of Science and Technology, Department of Information and Communication Sciences, Sophia University
Degree
修士(工学)(東京大学)
博士(情報理工学)(東京大学)

Researcher number
20323850
J-GLOBAL ID
200901028424108863
researchmap Member ID
5000008983

External link

私は主に組合せ最適化問題を研究しています.産業で生じる問題を組合せ最適化問題としてモデル化する方法,モデル化した問題を効率的に解くためのアルゴリズムの開発,さらには計算機科学におけるアルゴリズムの基礎などを研究しています.


Papers

 50
  • 根本 俊男, 宮本 裕一郎
    選挙研究, 39(2) 171-189, Mar, 2024  Peer-reviewed
  • Ken-ichi TANAKA, Ryuhei MIYASHIRO, Yuichiro MIYAMOTO
    Journal of Advanced Mechanical Design, Systems, and Manufacturing, 12(3) JAMDSM0065-JAMDSM0065, Jul 20, 2018  Peer-reviewed
  • Tomomi Matsui, Yuichiro Miyamoto
    Journal of the Operations Research Society of Japan, 61(1) 151-162, Jan 1, 2018  Peer-reviewed
    This paper discusses the problem of determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangulation. There exist theorems which characterize Delaunay graphs and yield polynomial time algorithms for the problem only by solving some linear inequality systems. A polynomial time algorithm proposed by Hodgson, Rivin and Smith solves a linear inequality system given by Rivin, which is based on sophisticated arguments about hyperbolic geometry. Independently, Hiroshima, Miyamoto and Sugihara gave another linear inequality system and a polynomial time algorithm. Although their discussion is based on primitive arguments on Euclidean geometry, their proofs are long and intricate, unfortunately. In this paper, we give a simple proof of the theorem shown by Hiroshima et al. by employing the fixed point theorem.
  • Ken-ichi Tanaka, Ryuhei Miyashiro, Yuichiro Miyamoto
    GEOGRAPHICAL ANALYSIS, 48(4) 448-464, Oct, 2016  Peer-reviewed
    This study uses a mathematical optimization approach to design safe walking routes from school to home for children. Children are thought to be safer when walking together in groups rather than alone. Thus, we assume that the risk of walking along a given road segment in a group is smaller than that of walking the same segment alone. At the same time, the walking route between school and home for each child should not deviate substantially from the shortest route. We propose a bi-objective model that minimizes both the total risk (particularly, the total distance walked alone) and the total walking distance for all children. We present an integer programming formulation of the proposed problem and apply this formulation to two instances based on actual road networks. We obtain Pareto optimal solutions using a mathematical programming solver and analyze the characteristics of the solutions and their potential applicability to real situations. The results show that the proposed model produces much better solutions compared with the solution where each child walks along the shortest path from school to home. In some optimal solutions, only a small deviation from the shortest path results in a dramatic reduction of the risk objective.
  • Atsushi Miyauchi, Yuichiro Miyamoto
    EUROPEAN PHYSICAL JOURNAL B, 86(7), Jul, 2013  Peer-reviewed
    Modularity proposed by Newman and Girvan is a quality function for community detection. Numerous heuristics for modularity maximization have been proposed because the problem is NP-hard. However, the accuracy of these heuristics has yet to be properly evaluated because computational experiments typically use large networks whose optimal modularity is unknown. In this study, we propose two powerful methods for computing a nontrivial upper bound of modularity. More precisely, our methods can obtain the optimal value of a linear programming relaxation of the standard integer linear programming for modularity maximization. The first method modifies the traditional row generation approach proposed by Grotschel and Wakabayashi to shorten the computation time. The second method is based on a row and column generation. In this method, we first solve a significantly small subproblem of the linear programming and iteratively add rows and columns. Owing to the speed and memory efficiency of these proposed methods, they are suitable for large networks. In particular, the second method consumes exceedingly small memory capacity, enabling us to compute the optimal value of the linear programming for the Power Grid network (consisting of 4941 vertices and 6594 edges) on a standard desktop computer.

Misc.

 11
  • 渡邉一生, 宮本裕一郎
    日本オペレーションズ・リサーチ学会2018年春期研究発表会アブストラクト集, 1-A-6-1-A-6, Mar 15, 2018  
  • 宮本裕一郎
    オペレーションズ・リサーチ, 60(12) 706-713, Dec 1, 2015  Peer-reviewedInvited
    この記事は,オペレーションズ・リサーチの中でも特に組合せ最適化,あるいは離散アルゴリズムでよく用いられるグラフ理論の記法の手ほどきを目的としている.グラフ理論の記法では,集合や関数の使い方が重要である.よって,まず集合や関数についても少しだけ紹介した後に,グラフ理論の初歩を紹介する.そして,グラフ理論の記法の使い方の例として美術館定理を扱う.高校数学程度の論理的議論はできるがグラフ理論の数理的記述には慣れていないという読者を想定している.
  • Tomomi Matsui, Yuichiro Miyamoto
    Proceedings of the 24th Canadian Conference on Computational Geometry, CCCG 2012, 241-246, Dec 1, 2012  
    This paper discusses a problem for determining whether a given plane graph is a Delaunay graph, i.e., whether it is topologically equivalent to a Delaunay triangula- Tion. There exists a theorem which characterizes De- launay graphs and yields a polynomial time algorithm for the problem only by solving a certain linear inequal- ity system. The theorem was proved by Rivin based on arguments of hyperbolic geometry. Independently, Hi- roshima, Miyamoto and Sugihara gave another proof of the theorem based on primitive arguments on Euclidean geometry. Unfortunately, the existing proofs of the the- orem are rather difficult or long. In this paper, we give a simple proof of the theorem characterizing Delaunay graphs, which is based on the fixed point theorem.
  • 松井 知己, 宮本 裕一郎
    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2012 182-183, Sep 12, 2012  
  • 田中 健一, 宮代 隆平, 宮本 裕一郎
    日本オペレーションズ・リサーチ学会秋季研究発表会アブストラクト集, 2011 198-199, Sep 13, 2011  

Books and Other Publications

 1

Presentations

 22

Research Projects

 8