2026/04/22 更新

写真a

シオウラ　アキヨシ
塩浦　昭義
SHIOURA AKIYOSHI
所属
工学院 教授
職名
教授
ホームページ
http://www.iee.e.titech.ac.jp/~shioura/index.html
外部リンク

News & Topics

研究キーワード

  • 組合せ最適化

  • 数理最適化

  • 離散最適化

研究分野

  • 自然科学一般 / 数学基礎

  • 自然科学一般 / 応用数学、統計数学

  • 情報通信 / 情報学基礎論

  • 情報通信 / 数理情報学

学歴

  • 東京工業大学   大学院情報理工学研究科   数理・計算科学専攻

    1995年4月 - 1997年3月

    　 詳細を見る

    国名： 日本国

    備考： 中退

    researchmap

  • 東京工業大学   大学院理工学研究科   情報科学専攻

    1993年4月 - 1995年3月

    　 詳細を見る

  • 東京工業大学   理学部   情報科学科（1類）

    1989年4月 - 1993年3月

    　 詳細を見る

経歴

  • 東京工業大学   工学院経営工学系   教授

    2020年4月 - 現在

    　 詳細を見る

  • 東京工業大学   工学院経営工学系   准教授

    2016年4月 - 2020年3月

    　 詳細を見る

  • 東京工業大学   大学院社会理工学研究科社会工学専攻   准教授

    2015年4月 - 2016年3月

    　 詳細を見る

  • 東北大学 大学院情報科学研究科 システム情報科学専攻   准教授

    2001年6月 - 2015年3月

    　 詳細を見る

  • 上智大学   理工学部，機械工学科   助手

    1997年4月 - 2001年5月

    　 詳細を見る

所属学協会

  • Society for Industrial and Applied Mathematics

    　 詳細を見る

  • Institute for Operations Research and the Management Sciences

    　 詳細を見る

  • 日本オペレーションズ・リサーチ学会

    　 詳細を見る

  • Japan Society for Industrial and Applied Mathematics

    　 詳細を見る

  • 日本オペレーションズリサーチ学会編集委員会

    　 詳細を見る

  • 日本オペレーションズ・リサーチ学会研究普及委員会

    　 詳細を見る

  • 電子情報通信学会英文論文誌A離散数学とその応用小特集号編集委員会

    　 詳細を見る

  • 日本オペレーションズ・リサーチ学会東北支部

    　 詳細を見る

  • 日本オペレーションズ・リサーチ学会研究普及委員会

    　 詳細を見る

  • 電子情報通信学会英文論文誌A離散数学とその応用小特集号編集委員会

    　 詳細を見る

  • Mathematical Programming Society

    　 詳細を見る

  • Society for Industrial and Applied Mathematics

    　 詳細を見る

  • Institute for Operations Research and the Management Sciences

    　 詳細を見る

  • 日本オペレーションズ・リサーチ学会

    　 詳細を見る

  • 応用数理学会

    　 詳細を見る

  • 日本オペレーションズリサーチ学会編集委員会

    　 詳細を見る

  • Mathematical Programming Society

    　 詳細を見る

  • 日本オペレーションズ・リサーチ学会東北支部

    　 詳細を見る

▼全件表示

委員歴

  • 日本オペレーションズ・リサーチ学会   論文誌編集委員会  

    2021年5月 - 現在   

    　 詳細を見る

    団体区分：学協会

    researchmap

  • 日本オペレーションズ・リサーチ学会   2021年春季研究発表会実行委員会  

    2020年4月 - 2021年4月   

    　 詳細を見る

    団体区分：学協会

    researchmap

  • RAIRO-Operations Research   Associate Editor  

    2020年 - 現在   

    　 詳細を見る

    団体区分：学協会

    researchmap

  • 日本オペレーションズ・リサーチ学会   表彰委員会  

    2016年5月 - 2023年4月   

    　 詳細を見る

    団体区分：学協会

    researchmap

  • Journal of Mechanism and Institution Design   Associate Editor  

    2015年 - 現在   

    　 詳細を見る

    団体区分：学協会

    researchmap

  • 日本オペレーションズリサーチ学会編集委員会   委員  

    2009年 - 2011年   

    　 詳細を見る

    団体区分：学協会

    日本オペレーションズリサーチ学会編集委員会

    researchmap

  • 日本オペレーションズ・リサーチ学会東北支部   幹事  

    2002年   

    　 詳細を見る

    団体区分：学協会

    日本オペレーションズ・リサーチ学会東北支部

    researchmap

  • 日本オペレーションズ・リサーチ学会研究普及委員会   委員  

    2002年   

    　 詳細を見る

    団体区分：学協会

    日本オペレーションズ・リサーチ学会研究普及委員会

    researchmap

  • 電子情報通信学会英文論文誌A離散数学とその応用小特集号編集委員会   委員  

    2001年 - 2003年   

    　 詳細を見る

    団体区分：学協会

    電子情報通信学会英文論文誌A離散数学とその応用小特集号編集委員会

    researchmap

  • 日本オペレーションズ・リサーチ学会   庶務幹事(1997-2001)  

    1997年 - 2001年   

    　 詳細を見る

    団体区分：学協会

    日本オペレーションズ・リサーチ学会

    researchmap

▼全件表示

論文

  • NOTE ON POLYNOMIAL-TIME APPROXIMATION SCHEMES FOR INTEGRATED NETWORK DESIGN AND SCHEDULING PROBLEMS

    Kaito Miura, Yusuke Saito, Akiyoshi Shioura

    Journal of the Operations Research Society of Japan   67 ( 4 )   111 - 125   2024年10月

    　詳細を見る

    掲載種別：研究論文（学術雑誌）   出版者・発行元：The Operations Research Society of Japan  

    DOI： 10.15807/jorsj.67.111

    researchmap

  • Preemptive scheduling of parallel jobs of two sizes with controllable processing times.

    Akiyoshi Shioura, Vitaly A. Strusevich, Natalia V. Shakhlevich

    Journal of Scheduling   27 ( 2 )   203 - 224   2024年4月

    　詳細を見る

    掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s10951-023-00782-w

    researchmap

  • Generalizing Horn's conditions for preemptive scheduling on identical parallel machines via network flow techniques.

    Akiyoshi Shioura, Vitaly A. Strusevich, Natalia V. Shakhlevich

    Networks   83 ( 3 )   527 - 546   2024年4月

    　詳細を見る

    掲載種別：研究論文（学術雑誌）  

    DOI： 10.1002/net.22202

    researchmap

  • Characterization and algorithm for bivariate multi-unit assignment valuations

    Takafumi Otsuka, Akiyoshi Shioura

    Japan Journal of Industrial and Applied Mathematics   41 ( 1 )   359 - 380   2023年7月

    　詳細を見る

    掲載種別：研究論文（学術雑誌）   出版者・発行元：Springer Science and Business Media LLC  

    Abstract

    A multi-unit assignment valuation is a function represented by a weighted bipartite graph. In this paper, we provide a characterization of such a function in terms of maximizer sets of perturbed functions. We then present an algorithm that checks whether a given bivariate function is a multi-unit assignment valuation, and if the answer is “yes,” computes a weighted bipartite graph representing the function.

    DOI： 10.1007/s13160-023-00597-4

    researchmap

    その他リンク： https://link.springer.com/article/10.1007/s13160-023-00597-4/fulltext.html

  • Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines 査読

    Yusuke Saito, Akiyoshi Shioura

    Lecture Notes in Computer Science   13526   324 - 335   2022年11月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：Springer International Publishing  

    DOI： 10.1007/978-3-031-18530-4_24

    researchmap

  • M-Convex Function Minimization Under L1-Distance Constraint and Its Application to Dock Reallocation in Bike-Sharing System 査読

    Akiyoshi Shioura

    Mathematics of Operations Research   47 ( 2 )   1566 - 1611   2022年5月

    　詳細を見る

    掲載種別：研究論文（学術雑誌）   出版者・発行元：Institute for Operations Research and the Management Sciences (INFORMS)  

    In this paper, we consider a problem of minimizing an M-convex function under an L1-distance constraint (MML1); the constraint is given by an upper bound for L1-distance between a feasible solution and a given “center.” This is motivated by a nonlinear integer programming problem for reallocation of dock capacity in a bike-sharing system discussed by Freund et al. (2017). The main aim of this paper is to better understand the combinatorial structure of the dock reallocation problem through the connection with M-convexity and show its polynomial-time solvability using this connection. For this, we first show that the dock reallocation problem and its generalizations can be reformulated in the form of (MML1). We then present a pseudo-polynomial-time algorithm for (MML1) based on the steepest descent approach. We also propose two polynomial-time algorithms for (MML1) by replacing the L1-distance constraint with a simple linear constraint. Finally, we apply the results for (MML1) to the dock reallocation problem to obtain a pseudo-polynomial-time steepest descent algorithm and also polynomial-time algorithms for this problem. For this purpose, we develop a polynomial-time algorithm for a relaxation of the dock reallocation problem by using a proximity-scaling approach, which is of interest in its own right.

    DOI： 10.1287/moor.2021.1180

    researchmap

  • Time bounds of basic steepest descent algorithms for M-convex function minimization and related problems 査読

    Norito Minamikawa, Akiyoshi Shioura

    Journal of Operations Research Society of Japan   Vol. 64   2021年4月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    researchmap

  • A fast algorithm for multiprocessor speed-scaling problem minimizing completion time and energy consumption 査読

    Yusei Fujimori, Yasushi Kawase, Tomomi Matsui, Akiyoshi Shioura

    Information processing letters   2020年10月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.ipl.2020.105991

    researchmap

  • オークションと画像処理と物流と離散凸解析

    塩浦昭義

    電子情報通信学会誌 = The journal of the Institute of Electronics, Information and Communication Engineers   2020年3月

    　詳細を見る

    記述言語：日本語  

    researchmap

  • Separable convex resource allocation problem with L1-distance constraint 査読

    Norito Minamikawa, Akiyoshi Shioura

    Journal of Operations Research Society of Japan   62 ( 3 )   109 - 120   2019年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.15807/jorsj.62.109

    researchmap

  • Models and algorithms for energy-efficient scheduling with immediate start of jobs 査読

    Akiyoshi Shioura, Natalia Shakhlevich, Vitaly Strusevich, Primas Bernhard

    Journal of Global Optimization   Vol. 21 ( No. 5 )   pp. 505 - 516   2018年10月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    researchmap

  • Scheduling problems with controllable processing times and a common deadline to minimize maximum compression cost 査読

    Akiyoshi Shioura, Natalia Shakhlevich, Vitaly Strusevich

    Journal of Scheduling   Vol. ( No. )   pp.   2018年7月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    researchmap

  • Preemptive models of scheduling with controllable processing times and of scheduling with imprecise computation: A review of solution approaches 査読

    Akiyoshi Shioura, Natalia V. Shakhlevich, Vitaly A. Strusevich

    European Journal of Operational Research   266 ( 3 )   795 - 818   2018年5月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Elsevier B.V.  

    DOI： 10.1016/j.ejor.2017.08.034

    Scopus

    researchmap

  • On equivalence of M#-concavity of a set function and submodularity of its conjugate 査読

    Kazuo Murota, Akiyoshi Shioura

    Journal of the Operations Research Society of Japan   61 ( 2 )   163 - 171   2018年4月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：Operations Research Society of Japan  

    DOI： 10.15807/jorsj.61.163

    Scopus

    researchmap

  • Colored spanning graphs for set visualization 査読

    Ferran Hurtado, Matias Korman, Marc van Kreveld, Maarten Loffler, Vera Sacristan, Akiyoshi Shioura, Rodrigo I. Silveira, Bettina Speckmann, Takeshi Tokuyama

    COMPUTATIONAL GEOMETRY-THEORY AND APPLICATIONS   68   262 - 276   2018年3月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.comgeo.2017.06.006

    Web of Science

    researchmap

  • Simpler Exchange Axioms for M-concave Functions on Generalized Polymatroids 査読

    Kazuo Murota, Akiyoshi Shioura

    Japan Journal of Industrial and Applied Mathematics (JJIAM)   Vol. 35 ( No. )   pp. 235 - 259   2017年12月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    researchmap

  • On the Partnership Formation Problem 査読

    Akiyoshi Shioura

    Journal of Mechanism and Institution Design   Vol. 2   pp. 105 - 140   2017年12月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    researchmap

  • Buyback problem with discrete concave valuation functions 査読

    Shun Fukuda, Akiyoshi Shioura, Takeshi Tokuyama

    DISCRETE OPTIMIZATION   26 ( No. )   78 - 96   2017年11月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.disopt.2017.07.002

    Web of Science

    researchmap

  • Machine speed scaling by adapting methods for convex optimization with submodular constraints 査読

    Akiyoshi Shioura, Natalia V. Shakhlevich, Vitaly A. Strusevich

    INFORMS Journal on Computing   29 ( 4 )   724 - 736   2017年9月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：INFORMS Inst.for Operations Res.and the Management Sciences  

    DOI： 10.1287/ijoc.2017.0758

    Scopus

    researchmap

  • Note on time bounds of two-phase algorithms for L-convex function minimization 査読

    Kazuo Murota, Akiyoshi Shioura

    JAPAN JOURNAL OF INDUSTRIAL AND APPLIED MATHEMATICS   34 ( 2 )   429 - 440   2017年8月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s13160-017-0246-z

    Web of Science

    researchmap

  • Algorithms for L-convex Function Minimization: Connection Between Discrete Convex Analysis and Other Research Fields

    Akiyoshi Shioura

    Journal of Operations Research Society of Japan   Vol. 60 ( No. 3 )   2017年7月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    researchmap

  • Application of Submodular Optimization to Single Machine Scheduling with Controllable Processing Times Subject to Release Dates and Deadlines

    Akiyoshi Shioura, Natalia V. Shakhlevich, Vitaly A. Strusevich

    INFORMS Journal on Computing   Vol. 28 ( No. 1 )   2016年2月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    researchmap

  • Time bounds for iterative auctions: A unified approach by discrete convex analysis 査読

    Kazuo Murota, Akiyoshi Shioura, Zaifu Yang

    Discrete Optimization   19 ( No. )   36 - 62   2016年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.disopt.2016.01.001

    researchmap

  • Handling scheduling problems with controllable parameters by methods of submodular optimization

    Akiyoshi Shioura, Shakhlevich, N.V., Strusevich, V.A.

    Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)   Vol. 9869 LNCS   2016年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/978-3-319-44914-2_7

    researchmap

  • Decomposition algorithms for submodular optimization with applications to parallel machine scheduling with controllable processing times 査読

    Akiyoshi Shioura, Natalia V. Shakhlevich, Vitaly A. Strusevich

    MATHEMATICAL PROGRAMMING   153 ( 2 )   495 - 534   2015年11月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s10107-014-0814-9

    Web of Science

    researchmap

  • Buyback Problem with Discrete Concave Valuation Functions 査読

    Shun Fukuda, Akiyoshi Shioura, Takeshi Tokuyama

    Springer LNCS 9499: Approximation and Online Algorithms - 13th International Workshop   Vol. 9499   72 - 83   2015年9月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（その他学術会議資料等）  

    DOI： 10.1007/978-3-319-28684-6_7

    researchmap

  • Stability and Competitive Equilibria in Multi-unit Trading Networks with Discrete Concave Utility Functions

    Yoshiko T. Ikebe, Yosuke Sekiguchi, Akiyoshi Shioura, Akihisa Tamura

    Japan Journal of Industrial and Applied Mathematics   Vol. 32 ( No. 2 )   2015年7月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    researchmap

  • Monotonicity in steepest ascent algorithms for polyhedral L-concave functions 査読

    藤重悟, 室田一雄, 塩浦昭義

    Journal of the Operations Research Society of Japan   58 ( 2 )   184 - 208   2015年4月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：The Operations Research Society of Japan  

    For the minimum cost flow problem, Hassin (1983) proposed a dual algorithm, which iteratively updates dual variables in a steepest ascent manner. This algorithm is generalized to the minimum cost submodular flow problem by Chung and Tcha (1991). In discrete convex analysis, the dual of the minimum cost flow problem is known to be formulated as maximization of a polyhedral L-concave function. It is recently pointed out by Murota and Shioura (2014) that Hassin's algorithm can be recognized as a steepest ascent algorithm for polyhedral L-concave functions. The objective of this paper is to show some monotonicity properties of the steepest ascent algorithm for polyhedral L-concave functions. We show that the algorithm shares a monotonicity property of Hassin's algorithm. Moreover, the algorithm finds the "nearest" optimal solution to a given initial solution, and the trajectory of the solutions generated by the algorithm is a "shortest" path from the initial solution to the "nearest" optimal solution. The algorithm and its properties can be extended for polyhedral \Lnat-concave functions.

    DOI： 10.15807/jorsj.58.184

    CiNii Books

    researchmap

    その他リンク： http://hdl.handle.net/2433/198549

  • Gross Substitutes Condition and Discrete Concavity for Multi-Unit Valuations: A Survey

    Akiyoshi Shioura, Akihisa Tamura

    Journal of Operations Research Society of Japan   Vol. 58 ( No. 1 )   2015年3月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    researchmap

  • Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility Under Budget Constraints 査読

    Akiyoshi Shioura

    MATHEMATICS OF OPERATIONS RESEARCH   40 ( 1 )   192 - 225   2015年2月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1287/moor.2014.0668

    Web of Science

    researchmap

  • EQUILIBRIUM, AUCTION, AND GENERALIZED GROSS SUBSTITUTES AND COMPLEMENTS

    Shioura Akiyoshi, Yang Zaifu

    日本オペレーションズ・リサーチ学会論文誌   Vol. 58 ( No. 4 )   410 - 435   2015年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）   出版者・発行元：The Operations Research Society of Japan  

    We study a market model where there are many different types of indivisible goods for sale. The goods can be substitutable or complementary. There are multiple units of each good. Each agent may consume several goods and has quasi-linear utilities in money. A general condition is introduced to guarantee the existence of a Walrasian equilibrium and generalize gross substitutes, strong substitutes, and gross substitutes and complements conditions. Several characterizations of this new condition are identified. A price adjustment process is proposed which converges globally to a Walrasian equilibrium.

    DOI： 10.15807/jorsj.58.410

    CiNii Books

    researchmap

    その他リンク： https://jlc.jst.go.jp/DN/JLC/20017139517?from=CiNii

  • Special section on discrete mathematics and its applications

    Akiyoshi Shioura

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   Vol. E98A ( No. 6 )   2015年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1587/transfun.E98.A.1144

    researchmap

  • Exact bounds for steepest descent algorithms of L-convex function minimization 査読

    Kazuo Murota, Akiyoshi Shioura

    OPERATIONS RESEARCH LETTERS   42 ( 5 )   361 - 366   2014年7月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1016/j.orl.2014.06.005

    Web of Science

    researchmap

  • Dijkstra's algorithm and L-concave function maximization 査読

    Kazuo Murota, Akiyoshi Shioura

    MATHEMATICAL PROGRAMMING   145 ( 1-2 )   163 - 177   2014年6月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1007/s10107-013-0643-2

    Web of Science

    researchmap

  • A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks 査読

    Jinhee Chun, Akiyoshi Shioura, Truong Minh Tien, Takeshi Tokuyama

    IEICE TRANSACTIONS ON FUNDAMENTALS OF ELECTRONICS COMMUNICATIONS AND COMPUTER SCIENCES   E97A ( 6 )   1220 - 1230   2014年6月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1587/transfun.E97.A.1220

    Web of Science

    researchmap

  • Computing a Walrasian Equilibrium in Iterative Auctions with Multiple Differentiated Items. 査読

    Kazuo Murota, Akiyoshi Shioura, Zaifu Yang

    Algorithms and Computation - 24th International Symposium, ISAAC 2013, Hong Kong, China, December 16-18, 2013, Proceedings   468 - 478   2013年

    　詳細を見る

    出版者・発行元：Springer  

    DOI： 10.1007/978-3-642-45030-3_44

    researchmap

  • A Unified View to Greedy Geometric Routing Algorithms in Ad Hoc Networks 査読

    Jinhee Chun, Akiyoshi Shioura, Truong Minh Tien, Takeshi Tokuyama

    Proc. ALGOSENSORS Springer LNCS   112 ( 272 )   54 - 65   2012年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）   出版者・発行元：一般社団法人電子情報通信学会  

    The main aim of this paper is to give a unified view to greedy geometric routing algorithms in ad hoc networks. For this, we firstly present a general form of greedy routing algorithm using a class of objective functions which are invariant under congruent transformations of a point set. We show that some known greedy routing algorithms such as Greedy Routing, Compass Routing, and Midpoint Routing can be regarded as special cases of the generalized greedy routing algorithm. In addition, inspired by the unified view of greedy routing, we propose three new greedy routing algorithms. We then derive a sufficient condition for our generalized greedy routing algorithm to guarantee packet delivery on every Delaunay graph. This condition makes it easier to check whether a given routing algorithm guarantees packet delivery, and it is closed under convex linear combination of objective functions. We show that Greedy Routing, Midpoint Routing, and the three new greedy routing algorithms proposed in this paper satisfy the sufficient condition, i.e., they guarantee packet delivery on Delaunay graphs, and then discuss comparison of these methods.

    DOI： 10.1007/978-3-642-36092-3_7

    CiNii Books

    researchmap

  • Polynomial-Time Approximation Schemes for Maximizing Gross Substitutes Utility under Budget Constraints 査読

    Akiyoshi Shioura

    ALGORITHMS - ESA 2011   6942   1 - 12   2011年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

    Web of Science

    researchmap

  • Optimal Allocation in Combinatorial Auctions with Quadratic Utility Functions 査読

    Akiyoshi Shioura, Shunya Suzuki

    THEORY AND APPLICATIONS OF MODELS OF COMPUTATION, TAMC 2011   6648   142 - 153   2011年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

    Web of Science

    researchmap

  • Neighbor Systems, Jump Systems, and Bisubmodular Polyhedra 査読

    Akiyoshi Shioura

    ALGORITHMS AND COMPUTATION, PT I   6506   169 - 181   2010年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

    Web of Science

    researchmap

  • A Fast Algorithm for Computing a Nearly Equitable Edge Coloring with Balanced Conditions 査読

    Akiyoshi Shioura, Mutsunori Yagiura

    COMPUTING AND COMBINATORICS, PROCEEDINGS   5609   116 - +   2009年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

    Web of Science

    researchmap

  • Fast Divide-and-Conquer Algorithms for Preemptive Scheduling Problems with Controllable Processing Times - A Polymatroid Optimization Approach 査読

    Natalia V. Shakhlevich, Akiyoshi Shioura, Vitaly A. Strusevich

    ALGORITHMS - ESA 2008   5193   756 - +   2008年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

    Web of Science

    researchmap

  • Special section on discrete mathematics and its applications

    Keiko Imai, Hisashi Koga, Mitsuru Matsui, Tomomi Matsui, Atsuko Miyaji, Kunihiko Sadakane, Tetsuo Shibuya, Akiyoshi Shioura, Tsuyoshi Takagi, Yasuhiko Takenaga, Eiji Takimoto, Keisuke Tanaka, Tatsuie Tsukiji, Ryuhei Uehara, Takeaki Uno, Koichi Yamazaki, Satoshi Fujita

    IEICE Transactions on Fundamentals of Electronics, Communications and Computer Sciences   E89-A ( 5 )   1159   2006年1月

    　詳細を見る

    掲載種別：研究論文（学術雑誌）  

    DOI： 10.1093/ietfec/e89.a.5.1159

    Scopus

    researchmap

  • Efficiently Pricing European-Asian Options - Ultimate Implementation and Analysis of the AMO Algorithm 査読

    Akiyoshi Shioura, Takeshi Tokuyama

    LNCS3521(Proc. AAIM 2005)   LNCS3521   291 - 300   2005年8月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

    DOI： 10.1007/11496199_32

    researchmap

  • Substitutes and complements in network flows viewed as discrete convexity. 査読

    Kazuo Murota, Akiyoshi Shioura

    Discrete Optimization   2 ( 3 )   256 - 268   2005年

    　詳細を見る

  • A Fast, Accurate and Simple Method for Pricing European-Asian and Saving-Asian Options. 査読

    K. Ohta, K. Sadakane, A. Shioura, T. Tokuyama

    Proceedings of ESA2001, LNCS2461   2461   772 - 784   2002年1月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

    researchmap

  • Minimum ratio canceling is oracle polynomial for linear programming, but not strongly polynomial, even for networks 査読

    ST McCormick, A Shioura

    PROCEEDINGS OF THE ELEVENTH ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS   944 - 958   2000年

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（国際会議プロシーディングス）  

    Web of Science

    researchmap

  • An Optimal Algorithm for Scanning all Spanning Trees of Undirected Graphs 査読

    Akiyoshi Shioura, Akihisa Tamura, Takeaki Uno

    SIAM Journal on Computing   26 ( 3 )   678 - 692   1997年1月

    　詳細を見る

    記述言語：英語   掲載種別：研究論文（学術雑誌）  

    DOI： 10.1137/S0097539794270881

    researchmap

  • 木構造ネットワークでの道配置問題に対する最適な算法

    塩浦 昭義, 宇野 毅明

    電子情報通信学会回路とシステム研究会   63 - 70   1995年11月

    　詳細を見る

    記述言語：日本語   掲載種別：研究論文（研究会，シンポジウム資料等）  

    researchmap

  • k-tree-core を線形時間で求めるアルゴリズム

    宇野 毅明, 塩浦 昭義

    最適化：モデリングとアルゴリズム5   57 - 61   1994年3月

    　詳細を見る

    記述言語：日本語   掲載種別：研究論文（研究会，シンポジウム資料等）  

    researchmap

▼全件表示

書籍等出版物

  • Handbook of Combinatorial Optimization, 2nd Edition

    Springer  2013年  （ ISBN:9781441979964 ）

    　詳細を見る

  • 応用数理ハンドブック

    朝倉書店  2013年  （ ISBN:9784254111415 ）

    　詳細を見る

  • 離散凸解析と最適化アルゴリズム

    朝倉書店  2013年  （ ISBN:9784254116823 ）

    　詳細を見る

  • OR事典2000

    日本オペレーションズ・リサーチ学会  2000年 

    　詳細を見る

講演・口頭発表等

  • Steepest Descent Algorithm for M-convex Function Minimization Using Long Step Length

    Akiyoshi Shioura

    13th Hungarian-Japanese Symposium on Discrete Mathematics and Its Applications  2025年5月 

    　詳細を見る

    開催年月日： 2025年5月

    researchmap

  • 準M♮凸関数の最小化に関する諸性質

    塩浦昭義

    京都大学数理解析研究所 共同研究(公開型) 数理最適化: 理論と実践  2023年8月 

    　詳細を見る

    開催年月日： 2023年8月

    会議種別：口頭発表（一般）  

    researchmap

  • Characterization and Algorithm for Bivariate Multi-Unit Assignment Valuations

    Akiyoshi Shioura

    Fifth Conference on Discrete Optimization and Machine Learning  2023年8月 

    　詳細を見る

    開催年月日： 2023年8月

    会議種別：口頭発表（一般）  

    researchmap

  • Algorithm for Computing Representation of Bivariate Multi-Unit Assignment Valuations

    第193回アルゴリズム研究発表会  2023年5月 

    　詳細を見る

    開催年月日： 2023年5月

    記述言語：日本語   会議種別：口頭発表（一般）  

    researchmap

  • Understanding Horn's conditions for preemptive scheduling on identical parallel machines -- Viewpoint from Network Flows --

    電子情報通信学会コンピュテーション研究会  2024年10月 

    　詳細を見る

  • On the monotonicity in steepest descent algorithm for M-convex functions

    25th International Symposium on Mathematical Programming  2024年7月 

    　詳細を見る

  • Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines 国際会議

    International Symposium on Combinatorial Optimization  2022年5月 

    　詳細を見る

    開催地：オンライン  

    researchmap

  • 重み付き二部グラフで表現可能な関数に対する判定と表現の計算

    大塚貴郁, 塩浦昭義

    日本応用数理学会第19回研究部会連合発表会  2023年3月 

    　詳細を見る

    記述言語：日本語   会議種別：口頭発表（一般）  

    researchmap

  • Connection Between Discrete Convex Analysis and Auction Theory 招待

    Akiyoshi Shioura

    International Workshop on Discrete Convex Analysis and Economics  2023年3月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（招待・特別）  

    researchmap

  • A Characterization of Bivariate Multi-unit Assignment Valuations

    Takafumi Otsuka, Akiyoshi Shioura

    12th Japanese-Hungarian Symposium on Discrete Mathematics and Its Applications  2023年3月 

    　詳細を見る

    記述言語：英語   会議種別：口頭発表（一般）  

    researchmap

  • Polynomial-Time Approximation Schemes for a Class of Integrated Network Design and Scheduling Problems with Parallel Identical Machines

    第188回アルゴリズム研究発表会  2022年5月 

    　詳細を見る

    開催地：オンライン  

    researchmap

  • Using Long Step Length in Steepest Descent Algorithm for M-convex Function Minimization

    Taihei Oki, Akiyoshi Shioura

    電子情報通信学会コンピュテーション研究会  2025年10月 

    　詳細を見る

▼全件表示

受賞

  • 日本オペレーションズ・リサーチ学会 60周年記念論文賞

    2018年9月  

    　詳細を見る

  • 日本オペレーションズ・リサーチ学会 論文賞

    2016年9月  

    　詳細を見る

  • 日本オペレーションズ・リサーチ学会フェロー

    2015年3月  

    　詳細を見る

  • 日本オペレーションズ・リサーチ学会 研究賞

    2012年  

    　詳細を見る

  • 石田記念財団研究奨励賞

    2009年  

    　詳細を見る

  • 日本オペレーションズ・リサーチ学会論文賞奨励賞

    2006年  

    　詳細を見る

  • 日本オペレーションズ・リサーチ学会学生論文賞

    1995年  

    　詳細を見る

▼全件表示

共同研究・競争的資金等の研究課題

  • 離散凸最適化問題に対する多様な解の計算

    研究課題/領域番号：23K10995  2023年4月 - 2027年3月

    日本学術振興会  科学研究費助成事業  基盤研究(C)

    塩浦 昭義

    　 詳細を見る

    配分額：4680000円 （ 直接経費：3600000円 、 間接経費：1080000円 ）

    researchmap

  • プロダクトミックスオークション実装のためのアルゴリズムの構築

    研究課題/領域番号：21H05848  2021年9月 - 2023年3月

    日本学術振興会  科学研究費助成事業 学術変革領域研究(A)  学術変革領域研究(A)

    塩浦 昭義

    　 詳細を見る

    配分額：3250000円 （ 直接経費：2500000円 、 間接経費：750000円 ）

    本年度は主に，「入札者の代替的評価関数を正確に表現する重み付き評価値ベクトル集合を求める」という課題に取り組んだ．評価関数が「需要オラクル」により表現される場合についてはGoldberg et al. (2021)により解決済みであり，本研究では評価関数が「関数値オラクル」で表現されるときに，どの程度高速に計算可能かを明らかにし，実際に高速に計算を行うアルゴリズムの構築を目指す．
    この目標を実現するための手がかりとして，代替的評価関数の特殊ケースについて，その構造を理解することから始めた．まずは対称凹評価関数という部分クラスについて，その関数の多面体構造を調査しつつ，その関数を表現する重み付き評価値ベクトルの表現について調べたが，陽な形での表現を得ることは困難であった．
    次に，正の重み付き評価値ベクトルのみで表現可能な評価関数のクラスに注目し，とくに財が2つのみの場合に注目して研究を進めた．まずは関数値の情報が所与のときに，その評価関数を表現する評価値ベクトルの計算方法について調査を行った．評価関数に対してある種の非退化性の仮定をおいた場合には，逐次的な計算により，関数を表現する評価値ベクトルの計算が比較的容易にできることを確認した．一方で，非退化性の仮定を置かないより一般的な場合については，同様の手法は使えない可能性が高いことが判明した．
    そのため，正の重み付き評価値ベクトルのみで表現可能な評価関数の多面体的な構造について，より詳細な調査を行い，関数の多面体構造に基づく非自明な特徴付けを得ることができた．また，その特徴付けを用いることにより，所与の評価関数が正の重み付き評価値ベクトルのみで表現可能か否かを判定することが高速にできることを確認した．ここで得られた成果については，現在論文にまとめており，査読付き論文誌に投稿する予定である．

    researchmap

  • ロバスト非線形整数計画問題に対する離散凸解析アプローチの研究

    研究課題/領域番号：18K11177  2018年4月 - 2022年3月

    日本学術振興会  科学研究費助成事業 基盤研究(C)  基盤研究(C)

    塩浦 昭義

    　 詳細を見る

    配分額：4420000円 （ 直接経費：3400000円 、 間接経費：1020000円 ）

    本年度はコロナ渦で，例年のように国内外の出張が全く出来なくなり，研究計画の大幅な変更を余儀なくされたが，一方で国際会議のほとんどがオンライン開催となり，これまで参加できなかった会議にも参加でき，効率的に情報収集を出来るようになった．また，出張が出来ない分，大学や自宅にてじっくり考える時間を確保することが出来た．これにより研究を進めることができ，様々な成果を得ることが出来た．
    具体的な成果としては，まずＭ凸関数およびその一般化に対する貪欲アルゴリズムについて検討を行った．Ｍ凸関数の貪欲アルゴリズムの反復回数が，初期解と最適解のＬ１距離に一致することが知られているが，この事実に対する簡潔な別証明を与えた．この証明を踏まえ，ジャンプＭ凸関数というより一般的な離散凸関数に対しても，同様の結果を得ることができた．
    さらに，関連する問題として，ジャンプシステム上での分離凸関数最小化問題に対する貪欲アルゴリズムの反復回数について，初期解と最適解のＬ１距離でバウンドできるかどうか，検討を行った．上述の結果と同様の証明を試みたが，解析対象のアルゴリズムにおける解の更新方法が異なることから，同様の結果を得ることが現時点まで出来ていない．一方で検討を重ねるごとに，この問題に対する理解が進み，この問題およびアルゴリズムの本質を理解しつつある．
    また，複数のＭ凸関数の最大値を最小にする，という問題についても検討を始めた．この種の問題は近年，計算的社会選択の分野において，不可分財の公平配分という文脈で盛んに研究されているが，既存研究において，与えられた関数が線形という非常に特殊な場合でも一般には計算困難なことが示されている．そのため，解の計算をより容易にしつつ，元の問題の本質を失わないようにする問題設定の修正について検討している．

    researchmap

  • 情報通信のための頑健なネットワーク設計および効率的なネットワーク運用の研究

    研究課題/領域番号：17F17727  2017年10月 - 2020年3月

    日本学術振興会  科学研究費助成事業 特別研究員奨励費  特別研究員奨励費

    塩浦 昭義, BAFFIER JEAN-FRANCOIS

    　 詳細を見る

    配分額：1400000円 （ 直接経費：1400000円 ）

    In this year we have focused on the transmission of knowledge in information networks. A typical property of those networks is their massive scale, making classical algorithms difficult to apply. In previous research, we have introduced a model to evaluate the influence of the different actors (for instance, the articles in a citation network) in the transmission of this knowledge.
    We encountered (and solved) several difficulties. The two major difficulties come from the temporal property of information networks. In our citation network example, we had considered that articles were static once submitted. However, it is not the case of pre-print articles that can be freely updated. First, cycles of influence exist, allowing self-gratification. Second, it also raises the question of the amount of knowledge produced by each version of an article.
    We provided a method to decycle networks with small cycles. This method is also used to approximate the transmission of knowledge in networks with any cycle size. Such an extension is possible due to the nature of knowledge influence to fade at each interaction.
    To handle the updates of articles (versioning) and dynamic citations, we needed a temporal model for interactions that can capture any arbitrary timeframe. We extended the definition of the classical flow and cut in graphs to stream graphs.

    researchmap

  • 離散ＤＣ関数最小化問題に対する大域的最適化手法の構築

    研究課題/領域番号：15K00030  2015年4月 - 2019年3月

    日本学術振興会  科学研究費助成事業 基盤研究(C)  基盤研究(C)

    塩浦 昭義

    　 詳細を見る

    配分額：4680000円 （ 直接経費：3600000円 、 間接経費：1080000円 ）

    離散ＤＣ関数最小化問題に対して，解きやすい問題クラスの検出や精度保証付き近似アルゴリズムの構築を目指した．また，DC関数を構成するM凸関数，L凸関数自体の構造をより良く理解することを目的として，M凸関数およびL凸関数の最小化問題という，基本的な問題の再検討を行い，アルゴリズムの改良を行うと同時に，計算量の解析方法の改善を実現した．さらに，離散凸関数の制約なし最小化問題と離散DC関数最小化問題の中間に位置する問題についても調査し，これらの問題の構造を明らかにするとともに，その結果を利用して高速なアルゴリズムを提案した．

    researchmap

  • 非線形整数計画問題の組合せ構造解析による計算限界の解明

    研究課題/領域番号：15H00848  2015年4月 - 2017年3月

    日本学術振興会  科学研究費助成事業 新学術領域研究(研究領域提案型)  新学術領域研究(研究領域提案型)

    塩浦 昭義

    　 詳細を見る

    配分額：4550000円 （ 直接経費：3500000円 、 間接経費：1050000円 ）

    本研究では，整数格子点上で定義される非線形な関数（以下，離散関数）が与えられ，それを最小化する整数ベクトルを求める，という非線形整数計画問題を扱う．本研究では，離散関数の多面体構造に注目し，効率的に最小化可能な離散関数のクラスを，その凸閉包関数の多面体構造によって特徴付けることを目的とする．
    本年度は，ある種のスケジューリング問題から生じる非線形整数計画問題の解法構築に取り組んだ．このスケジューリング問題では，機械の消費エネルギー量を増やすことにより，処理スピードを上げることができる．したがって，各ジョブの処理時間は変化させることができるが，処理時間を短くすると消費エネルギー量が増えることになる．このスケジューリング問題の目的は，各ジョブの処理開始時間，処理締切時間に関する制約を守りつつ，消費エネルギー量の総量が最小になるようなスケジュールを求めよ，という問題である．
    この問題に対し，昨年度の研究で得られた，スケジューリング問題の解集合が劣モジュラ多面体というよい構造をもつという結果を利用して，効率的な解法を得ることができた．このスケジューリング問題は，劣モジュラ多面体上での分離凸関数最小化問題の特殊ケースとみることができるので，後者の問題に対する各種解法がスケジューリング問題に適用できることがわかった．さらに問題の特殊性を利用することにより，それらの解法の計算時間を短縮することに成功した．また，この研究の副産物として，扱ったスケジューリング問題に対する既存のアルゴリズムが，劣モジュラ多面体上での分離凸関数最小化問題のある種の解法と密接な関係をもつことが判明した．

    researchmap

  • 離散凸解析に基づく劣モジュラ最適化問題の計算限界の解明

    研究課題/領域番号：25106503  2013年4月 - 2015年3月

    日本学術振興会  科学研究費助成事業 新学術領域研究(研究領域提案型)  新学術領域研究(研究領域提案型)

    塩浦 昭義

    　 詳細を見る

    配分額：4030000円 （ 直接経費：3100000円 、 間接経費：930000円 ）

    本研究では，劣モジュラ関数を様々な制約条件の下で最小化または最大化するという離散最適化問題（劣モジュラ最適化問題）を扱った．劣モジュラ性は様々な状況で自然に現れる概念であり，数多くの応用をもつことから，近年アルゴリズム開発の研究が盛んに行われている．しかし，その問題の数学的構造や計算複雑度については十分に解明されていない． 本研究の目的は，劣モジュラ最適化問題を離散凸解析の視点から調査することにより，劣モジュラ最適化問題の計算限界を明らかにすることである．研究代表者は科研費による援助を受けながら，離散凸解析の研究に10年以上携わってきた．その成果を踏まえ，この問題の構造解析および計算複雑度の解明に取り組んだ．
    本年度は，昨年度に引き続き，L凸関数の最小化問題に対する，最急降下アルゴリズムの解析を行った．昨年度は整数格子点集合上で定義されたL凸関数の場合を主に扱ったが，本年度は実数空間上で定義された多面体的L凸関数の場合へ一般化して解析を行った．最小費用流問題に対し Hassin (1983) が提案した双対アルゴリズムでは，双対変数を最急上昇方向へ繰り返し更新する．離散凸解析においては，最小費用流問題の双対問題は，多面体的L凸関数の最小化として定式化できることが知られており，Hassinのアルゴリズムは多面体的L凸関数に対する最急降下アルゴリズムと見なすことができる．本研究では，多面体的L凸関数に対する最急降下アルゴリズムのもつ様々な単調性を明らかにした．まず，最急降下アルゴリズムがHassinのアルゴリズムと同様の単調性を持つことを示した．また，任意の初期点から出発したときに，最急降下アルゴリズムが初期点から「最も近い」最適解を求めると共に，アルゴリズムで生成された解の軌跡が初期点から最適解への「最短路」であることを証明した．

    researchmap

  • 非線形制約をもつ整数計画問題に対する理論保証付き近似解法の開発

    研究課題/領域番号：24500002  2012年4月 - 2016年3月

    日本学術振興会  科学研究費助成事業 基盤研究(C)  基盤研究(C)

    塩浦 昭義

    　 詳細を見る

    配分額：5330000円 （ 直接経費：4100000円 、 間接経費：1230000円 ）

    本研究では，非線形な不等式制約の下で非線形関数を最大化するという整数計画問題に対し，解の精度および計算時間に関する理論的な保証を与える近似解法を開発することを目指した．本研究の主結果として，ナップサック制約の下で１つのM凹関数を最大化するという問題に対し，制約が複数個の場合でも，連続緩和アプローチを用いて任意の精度の近似解を多項式時間で求められることを示した．また，目的関数が２つのM凹関数の和の場合には，ラグランジュ緩和アプローチを用いて任意の精度の近似解が得られることを示した．

    researchmap

  • 数理経済学における離散凸解析の応用

    2010年

    　 詳細を見る

    資金種別：競争的資金

    researchmap

  • 離散凸パラダイムによる最適化統一理論

    研究課題/領域番号：21360045  2009年4月 - 2015年3月

    日本学術振興会  科学研究費助成事業 基盤研究(B)  基盤研究(B)

    室田 一雄, 田村 明久, 岩田 覚, 塩浦 昭義, 森口 聡子, 垣村 尚徳, 小林 佑輔, 土村 展之

    　 詳細を見る

    配分額：17810000円 （ 直接経費：13700000円 、 間接経費：4110000円 ）

    工学や社会科学の諸分野における最適化の理論と応用を「離散凸パラダイム」に よって統合する研究を行った．離散凸解析の理論と応用を， 連続・離散軸，凸・非凸軸，分野横断軸，の３つの観点から整理することによって，個々の数 理的技法や応用諸問題の相互関係を明確にし，数理の深化，応用の開拓，ソフト ウェアの整備の３つの観点から研究を行い，新たな展開を達成した．とくに，数理の深化については，Ｌ凸関数最小化アルゴリズムの詳細な解析やＤＣ計画の枠組みの提示などの成果をあげた．

    researchmap

  • 離散凸関数の制約付き最適化問題に対する高速高精度なアルゴリズムの構築

    研究課題/領域番号：21740060  2009年 - 2011年

    日本学術振興会  科学研究費助成事業 若手研究(B)  若手研究(B)

    塩浦 昭義

    　 詳細を見る

    配分額：4420000円 （ 直接経費：3400000円 、 間接経費：1020000円 ）

    本研究では, 申請者が近年携わってきた離散凸解析の理論に基づき, 計算時間や解の精度の面で理論的な保証をもつアルゴリズムを構築することを目的とした. 3年間の間に様々な結果を得ることが出来たが, とくに, 複数のナップサック制約の下でのM凹関数の最大化問題に対して, 多項式時間近似スキームを構築することに成功した. また, 近傍システムという, 一般的な解集合の構造を明らかにするとともに, 近傍システムに関する分離凸最適化問題が多項式時間で解けることを示した.

    researchmap

  • 離散凸パラダイムの深化と拡大

    研究課題/領域番号：18360048  2006年 - 2008年

    日本学術振興会  科学研究費助成事業 基盤研究(B)  基盤研究(B)

    室田 一雄, 田村 明久, 岩田 覚, 土村 展之, 森口 聡子, 塩浦 昭義

    　 詳細を見る

    配分額：13260000円 （ 直接経費：11100000円 、 間接経費：2160000円 ）

    経済学,システム工学,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立し,それを広範囲の応用分野に浸透させる研究を行った.「離散凸パラダイム」の横糸を成す,構造定理やアルゴリズムを代表とする離散関数に関する数理の研究と,縦糸を成す,諸応用分野における具体的な諸問題に対する研究を行った.

    researchmap

  • 離散凸解析アプローチに基づく非線形整数計画問題の実用的解法の研究

    研究課題/領域番号：18740042  2006年 - 2008年

    日本学術振興会  科学研究費助成事業 若手研究(B)  若手研究(B)

    塩浦 昭義

    　 詳細を見る

    配分額：3760000円 （ 直接経費：3400000円 、 間接経費：360000円 ）

    整数計画問題とは,与えられた制約条件を満たす整数ベクトルの中から,与えられた目的関数を最小化(または最大化)する解を求める問題である.一般に整数計画問題は短時間で解くことが困難である,ということが理論的にも現実的にも知られている.とくに,目的関数と条件が非線形関数で与えられる非線形整数計画問題は,解くことが最も困難な整数計画のクラスである.本研究では,様々な非線形整数計画問題に対して,その良質な近似解を短時間で求めるアルゴリズムを提案した.

    researchmap

  • スケジューリング問題に対する効率的なアルゴリズム

    2006年

    　 詳細を見る

    資金種別：競争的資金

    researchmap

  • 計算理論的設計による知識抽出モデルに関する研究

    研究課題/領域番号：16092202  2004年 - 2007年

    日本学術振興会  科学研究費助成事業 特定領域研究  特定領域研究

    徳山 豪, 塩浦 昭義, 河原林 健一, 全 眞嬉

    　 詳細を見る

    配分額：13100000円 （ 直接経費：13100000円 ）

    本研究の目的はデータマイニングにおける現在の精度限界を打破するための知識抽出モデルの提案と、それに関する理論研究及び実際のシステムの構築である。特に、研究代表者の持つ先端技術である計算幾何学的手法を中心に、計算理論手法による限界突破を目指した。継続中の研究テーマについては研究をさらに進めると共に、過去3年間に行った研究の取りまとめを行った。
    新たに得られた研究成果については、国内外の会議や研究会にてを発表するとともに、論文に纏めて学術論文誌に投稿をした。以下、新たに得られた結果について簡単に紹介する。
    昨年までの研究における重要な成果として、ゾーン図に関する結果が挙げられるが、これは点と点の間の3等分線によって描かれる図であった。本年度はこれをさらに発展させ、点と線分の間の3等分線について考え、そのような等分線の一意的存在性を示すと共に、3等分線を効率的に計算するアルゴリズムを提案した。
    次に、平面上に辺を曲線として描画されたグラフにおいて、辺が交差しない全域部分木を計算する問題を考えた。非交差な全域部分木を持つかどうかの判定はNP困難問題であり、交差数を最小化する問題は近似困難である事が知られている。本研究では、自然なパラメタに対し、パラメトリック計算量(パラメタへの依存度を考慮する計算量)を考察した。対象とするパラメタは、入力されるトポロジカルグラフにおける交差辺対の数、交差辺の数、頂点集合の凸包の内点である頂点数である。また、3-SAT問題への帰着により、この問題に対して計算困難性を示した。

    researchmap

  • 離散構造の凸近似に関する研究

    研究課題/領域番号：16654019  2004年 - 2005年

    日本学術振興会  科学研究費助成事業 萌芽研究  萌芽研究

    室田 一雄, 土村 展之, 森口 聡子, 塩浦 昭義, 松浦 史郎

    　 詳細を見る

    配分額：3500000円 （ 直接経費：3500000円 ）

    離散最適化問題は,生産計画,ロジスティクス,システム設計,ファイナンスなどの様々な応用分野で現れるが,最適解を効率的に求めることは多くの場合に困難である.本研究では,研究代表者によって提唱された離散凸解析という理論体系を踏まえて,非線形離散関数の離散凸関数による近似の理論構築を目的とした.さらに,この離散凸近似理論を基にして,非線形目的関数に関する離散最適化問題という扱いにくい問題を,離散凸関数最小化という扱いやすい問題で繰り返し近似して解くという新たなアプローチを提案する.しかし離散凸関数最小化は,連続凸関数の場合と異なり,より詳細な細分化を行わないと,扱いやすい問題が得られない.離散凸近似による効率的な最適化アプローチの実現には,離散凸関数の細分化の緻密さと,与えられた非線形目的関数に対してどの離散凸性による近似を採用するかが,重要な鍵となる.このため,本年度行った具体的な研究内容は以下の通りである.
    ・これまで離散凸解析で扱ってきたM凸性という概念を,ジャンプシステム上で定義された関数にまで拡張した.ジャンプシステム上のM凸関数最小化問題に対する最適性規準を導出した.
    ・離散関数に対するヘッセ行列および局所2次展開の概念を導入し,これらを用いたL凸関数およびM凸関数の特徴づけを与えた.この特徴づけは,連続凸関数に対する特徴づけとよく対応している.さらに,離散凸解析とは独立して研究されてきたmultimodularityという概念が,実質的にL凸性と等価な概念であることを,L凸関数の特徴づけを用いて簡単に示した.
    ・上記の結果に基づき,2次のL凸,M凸関数を用いた凸近似手法を構築した.さらに,一般のL凸,M凸関数による最良凸近似について検討を行った.

    researchmap

  • 計算困難な整数計画問題に対する主算法アプローチに基づく厳密解法の構築

    研究課題/領域番号：15740050  2003年 - 2005年

    日本学術振興会  科学研究費助成事業 若手研究(B)  若手研究(B)

    塩浦 昭義

    　 詳細を見る

    配分額：2700000円 （ 直接経費：2700000円 ）

    本研究の目的は,計算困難な整数計画問題に対して,主算法によるアプローチを使って,効率的な厳密解法を構築する,というものである.一般の非線形整数計画問題に対する効率的なアルゴリズムの完成には至らなかったが,それまでの研究において効率的なアルゴリズムの構築に有用と思われる興味深い結果を得ることができた.その内容を以下に述べる.
    ・完全ユニモジュラ行列と呼ばれる行列により制約条件が表現される非線形整数計画問題が,M凸関数,L凸関数などの離散凸関数と密接な関係をもつことがわかった.この結果は論文誌に掲載された.この結果のように,一般の非線形整数計画問題も局所的には何らかの良い構造をもっていることが期待され,これを利用することで効率的な解法が構築できるのではないかと考えられる.
    ・L凸関数最小化アルゴリズムに対する検討を行った.2005年9月にKolmogorovにより提案されたアルゴリズムと,2003年の室田のアルゴリズムの比較を行い,室田のアルゴリズムはKolmogorovのアルゴリズムを特殊化したものと見なせることを明らかにした.Kolmogorovのアルゴリズムは各反復での探索方向に自由度があるので,それを利用してより一般的な問題が解けるかどうかさらに検討した.
    ・ジャンプシステム上の分離凸関数最小化問題について検討を行った.基多面体上での分離凸関数最小化についてはすでに多項式時間アルゴリズムが知られているが,基多面体を一般化した概念であるジャンプシステムについてはまだ多項式時間で解けるかどうかわかっていない.そのため,研究代表者がこれまでに提案した領域縮小法やスケーリング法などの最小化手法が適用可能かどうか調べた.

    researchmap

  • 離散凸パラダイムの確立

    研究課題/領域番号：15360043  2003年 - 2005年

    日本学術振興会  科学研究費助成事業 基盤研究(B)  基盤研究(B)

    室田 一雄, 田村 明久, 岩田 覚, 土村 展之, 塩浦 昭義, 松浦 史郎

    　 詳細を見る

    配分額：10200000円 （ 直接経費：10200000円 ）

    本研究課題の目的は,経済学,システム工学,オペレーションズ・リサーチ,最適化理論,アルゴリズム理論などの広汎な分野における基礎的諸問題に関わる離散構造を,離散凸性という横断的視点から整理し,「離散凸」という新しいパラダイムを確立することにある.本研究課題では下記に挙げた研究成果を得ることが出来た.いずれの研究成果も査読つき国際会議や学術雑誌に採択されている.
    (1)離散双対性に関わる最適化問題,とくに,M凸関数を目的関数に含む劣モジュラ流問題に対して,容量スケーリング手法に基づくアルゴリズムを提案した.一般のM凸劣モジュラ流問題に対して,このアルゴリズムはこれまでで最良の時間計算量をもつ.
    (2)離散凸解析の枠組みとは独立に研究されてきたマルチモジュラー性という概念が,実質的にL凸性と等価な概念であることを示した.この結果をふまえ,整数格子点上で定義されたマルチモジュラー関数に対する離散分離定理などの諸性質を導いた.
    (3)2次のM凸関数と木距離の間の密接な関係を示した.より具体的には,2次のM凸関数のヘッセ行列は実質的に木距離行列(にマイナスを掛けたもの)であることを証明した.
    (4)整凸集合上の離散不動点定理を与えた.これは,数理経済学における一般均衡理論ならびに非協力ゲームへの応用をもつ.
    (5)M凸関数の概念が,数理経済学で良く知られた粗代替性や単改良性と等価であることを明らかにした.
    (6)離散凸解析の数理経済学への応用として,複数の不可分財と貨幣からなる市場において競争均衡が存在するための条件を与えるなどの理論構築を行うとともに,競争均衡を求めるアルゴリズムをM凸劣モジュラ流問題の枠組みを利用して開発した.

    researchmap

  • 離散最適化における準凸性の理論の構築と社会工学への応用

    研究課題/領域番号：13874016  2001年 - 2003年

    日本学術振興会  科学研究費助成事業 萌芽研究  萌芽研究

    室田 一雄, 塩浦 昭義, 田村 明久

    　 詳細を見る

    配分額：2100000円 （ 直接経費：2100000円 ）

    まず,数理経済学における離散凸関数の応用について研究を進めた.不可分な財を含む経済均衡モデルにおいて,供給者の費用関数がM凸関数かつ消費者の効用関数がM凹関数の場合に競争均衡が存在することが,研究代表者らの昨年度までの研究において証明されていた.本年度はさらにこの研究を進めて,競争均衡を実際に求める方法について検討し,多項式時間で競争均衡が求められることを示した.具体的には,競争均衡を求める問題を元にしてM凸劣モジュラ流問題をつくり,これを既存の多項式時間アルゴリズムで解いて得られた出力を適切に変換することで競争均衡が得られる,という手法である.これはM凸劣モジュラ流問題の応用としても興味深い結果である.
    次に,最適配分問題に対する効率的な解法の研究を行った.生産ラインでのバッファ配分や労働力・資源の配分など,生産システム設計の際に頻繁に現れる最適配分問題は,離散準凸性の理論を適用しやすい問題の一つである.離散準凸関数の理論を踏まえて,現実に現れる最適配分問題を定式化し,その離散構造を明らかにすると共に効率的な解法を提案した,具体的には,劣モジュラ制約の元での最適配分問題に対するHochbaumの高速解法がなぜうまく働くのかを離散凸性の視点から検討し,その結果を元にM凸関数に対する高速な最小化アルゴリズムを提案した.
    また,dial-a-ride transit system, isotone regressionなどに応用をもつ,双対最小費用流問題について研究を進めた.この問題が準L凸関数最小化問題の特殊ケースである,という事実を踏まえ,既存の解法を見直し,準L凸関数に対する解法へと拡張した.

    researchmap

  • 組合せ凸関数理論の構築と組合せ最適化問題に対する非線形計画アプローチの研究

    研究課題/領域番号：13740079  2001年 - 2002年

    日本学術振興会  科学研究費助成事業 若手研究(B)  若手研究(B)

    塩浦 昭義

    　 詳細を見る

    配分額：1800000円 （ 直接経費：1800000円 ）

    本年度は,組合せ凸関数の理論を構築するとともに,様々な組合せ最適化問題に対して非線形計画アプローチを用いた効率的なアルゴリズムを提案することを目指した.
    1.組合せ凸関数の理論において中心的な役割を果たすのがM凸関数という概念であるが,組合せ凸関数理論に基づく効率的な解法の基礎として,M凸関数最小化に対する高速算法の構築が必須となる.本年度はM凸関数最小化およびその特殊ケースに対する高速算法を提案し,下記の論文にまとめた.
    A.Shioura : Fast Scaling Algorithms for M-convex Function Minimization with Application to the Resource Allocation Problem, S.Moriguchi, A.Shioura : On Hochbaum's Scaling Algorithm for the General Resource Allocation Problem
    2.これまで組合せ凸関数の概念は主に整数格子点上で定義された関数を対象としていたが,組合せ最適化問題の中には実変数に関する問題が少なくない.この事実を踏まえて,組合せ凸関数の概念を実数空間上の関数へと拡張し,その関数に関する様々な性質を導いた.この結果は下記の論文にまとめられている.
    K.Murota, A.Shioura : M-convex and L-convex Functions over the Real Space : Two Conjugate Classes of Combinatorial Convex Functions
    3.組合せ凸関数の理論を利用して一般の組合せ最適化問題を解くためには,その問題の部分的な構造からM凸性,L凸性のような良い構造を見出すことが必要である.本年度は,最小費用流問題という,組合せ最適化においては基本的な問題からM凸性,L凸性が生じることがわかり,下記の論文にまとめた.
    K.Murota, A.Shioura : Substitutes and Complements in Network Flows Viewed as Discrete Convexity

    researchmap

  • 離散凸解析の応用開拓の研究

    研究課題/領域番号：12450040  2000年 - 2002年

    日本学術振興会  科学研究費助成事業 基盤研究(B)  基盤研究(B)

    室田 一雄, 田村 明久, 松浦 史郎, 松井 知己, 降旗 大介, 塩浦 昭義

    　 詳細を見る

    配分額：7600000円 （ 直接経費：7600000円 ）

    本研究課題の主題,研究代表者が1990年代の中頃から提唱している離散凸解析の応用開拓である.本研究課題では下記に挙げた研究成果を得ることが出来た.いずれの研究成果も査読つき国際会議や学術雑誌に採択されている.
    (1)数理経済学において,離散凸解析の応用研究として3つの成果を上げた.第1の成果は,複数の不可分財と貨幣からなる市場において競争均衡が存在するための十分条件を与えるなど,理論構築を行なった.第2の成果は,離散凸解析のおいて中心的役割をなすM凸関数の新しい特徴付けを与えた.この特徴付けは,数理経済学では良く知られた粗代替性や単改良性を用いたものである.第3の成果は,先に述べた不可分財と貨幣からなる市場において,競争均衡を求めるアルゴリズムの開発である.このアルゴリズムは,離散凸解析における最適化問題の一つであるM凸劣モジュラ流問題を利用したもので,多項式時間で均衡の存在判定を行ない,均衡が存在する場合はその一つを求める.
    (2)離散凸解析において中心的な役割を果たすM凸関数の最小化問題に対する近接定理を示すとともに,高速なアルゴリズムを開発した.
    (3)工学システムのもつ組合せ構造を離散凸解析の立場から論じた.特に,電気回路や制御システムの取扱いを目的として,混合多項式行列を考察し,効率的な組合せ緩和アルゴリズムを提案した.
    (4)オペレーションズ・リサーチの諸問題に対し,離散凸解析の結果を利用した解法が適用可能か否かを検証した.その結果を踏まえて,ネットワークデザインや最大カット問題に対して効率的な解法を提案した.

    researchmap

  • 生産システム設計への組合せ凸解析の応用

    研究課題/領域番号：11878069  1999年 - 2000年

    日本学術振興会  科学研究費助成事業 萌芽的研究  萌芽的研究

    室田 一雄, 塩浦 昭義

    　 詳細を見る

    配分額：1400000円 （ 直接経費：1400000円 ）

    本研究の目的は,組合せ凸解析の理論に基づいて,生産システム設計に現れる最適化問題の組合せ構造を明確にすると共に,最適な生産システムを設計するための実用的な解法を構築することである.この目的を実現するため,本年度は以下の研究を行った.
    ・スケーリング技法によるM凸関数最小化アルゴリズムの研究.M凸関数の最小化問題に対しては,最急降下法や領域縮小法が提案されているが,本研究においては,組合せ最適化のアルゴリズムにおいて基本的な技法であるスケーリング技法をM凸関数最小化に用いる可能性を研究した.一般にM凸関数はスケーリングに関して閉じていないが,ツリー型M凸関数や2次のM凸関数などのクラスのM凸関数がスケーリングに関して閉じていることを示すとともに,スケーリング技法と最急降下法とを組み合わせた効率的な算法を提案した.
    ・M凸関数の運搬経路問題への応用.時間枠制約つき運搬経路問題とは,各顧客への訪問時間枠制約をなるべく満たし,かつ運搬費用を最小にする経路及びスケジュールを求める問題である.経路決定とスケジューリングを分離するタイプのヒューリスティックにおいて,最適なスケジュールを求める問題がツリー型M凸関数の最小化問題として定式化できることを示した.
    ・2次のM凸関数・L凸関数の特徴付け.一般に2次の凸関数は半正定値対称行列で表現されるが,本研究では,どのような付加的条件がM凸性・L凸性を特徴づけかという問題意識をもち,この問題に対して完全な解答を与えた.その副産物として,確率過程論などで研究されてきたディリクレ形式との関連が明らかとなった.

    researchmap

  • 付値マトロイド理論の離散最適化問題への応用

    研究課題/領域番号：11740074  1999年 - 2000年

    日本学術振興会  科学研究費助成事業 奨励研究(A)  奨励研究(A)

    塩浦 昭義

    　 詳細を見る

    配分額：1600000円 （ 直接経費：1600000円 ）

    本年度は,前年度の研究結果に基づき,離散最適化問題に対するアルゴリズムの枠組みを提案するとともに,これまでの研究結果を論文誌や学会にて発表した.
    1.平成11年度の計画のうち,予定通りに終了しなかった部分については継続して研究を進めた.
    2.前年度の結果を踏まえて,付値マトロイドの理論に基づいた,離散最適化問題に対する解法の枠組みを提示した.さらに,その手法を現実の大規模な問題に適用するために必要なアルゴリズムを開発した.特に,スケーリングという技法を用いた効率的な算法を提案した.
    3.上記で得られたアルゴリズムをプログラム化し,その特徴を得るために実験により解析を行った.さらに,その結果を元にして,理論的な解析へ繋げようと試みている.
    4.以上の成果を専門分野の研究者に紹介し,討論を通じてその意義を明かにし,学術論文として学術論文誌に投稿した.いくつかの結果についてはDiscrete Applied Mathematics,Advances in Applied Mathematicsなどの論文誌に掲載されており,その他の論文については現在審査中である.また,2000年8月の国際数理計画シンポジウム,2000年11月の京都大学数理解析研究所の研究集会など,国内外の学会にて研究結果を発表するとともに,他の研究者と有意義な討論を行った.2001年2月には研究のまとめを行うために,カナダ・ブリティッシュコロンビア大学のMcCormick教授を訪問し,数多くの議論を行った.

    researchmap

  • 離散凸解析を軸とする離散最適化アルゴリズム

    研究課題/領域番号：10205212  1998年 - 2000年

    日本学術振興会  科学研究費助成事業  特定領域研究(B)

    室田 一雄, 田村 明久, 降旗 大介, 塩浦 昭義, 藤江 哲也

    　 詳細を見る

    配分額：5800000円 （ 直接経費：5800000円 ）

    非線形最適化の分野では,凸解析がその理論的なコアとなっている.一方,離散最適化の分野では,このような統一的な視点は存在しない.しかし,マトロイド的構造が良い性質と認知されている.「離散凸解析」は,連続変数に関する最適化と離散変数に関する最適化を統一的視点から捉える試みとして,研究代表者が提唱した理論体系であり,凸解析の理論とマトロイド理論の両者を結ぶ枠組みである.
    現実問題として現れる離散最適化問題は,マトロイド的な構造をもつものばかりではないので,分枝限定法のような列挙型の算法や,近似算法などを利用することになる.どのようなアプローチにおいても,問題特有の離散構造の中から扱いやすい部分をうまく抽出することが肝要である.例えば,一般の離散最適化問題を解く際に,ネットワーク的な構造を部分問題として抽出する手法は多くの場合に有効である.
    本研究の基本的なアイディアは,一般の離散最適化問題を解くために,離散凸解析で扱える問題を部分問題(子問題)として抽出しようというものである.本研究グループではこのアイディアに基づき,一般の離散最適化問題に対する効率的な解法の構築に取り組んだ.本研究グループの研究活動の成果として、以下のようなものが挙げられる:
    ●離散凸解析の枠組みにおいて中心的な役割を果たすM凸関数とL凸関数という概念の諸性質を示した。
    ●M凸関数の最小化問題に対する効率的な算法を提案した。
    ●整数格子点上で定義されているM凸/L凸関数の概念を、実数空間上の関数へと拡張した。
    ●M凸/L凸関数の定義を緩和することにより、準M凸/準L凸関数の概念を提案した。
    ●離散凸解析の経済均衡への応用について粗代替性とM凸性の同値性などの結果を得た。

    researchmap

  • 離散凸解析の社会科学への展開

    研究課題/領域番号：10874018  1998年

    日本学術振興会  科学研究費助成事業  萌芽的研究

    室田 一雄, 塩浦 昭義, 降旗 大介

    　 詳細を見る

    配分額：900000円 （ 直接経費：900000円 ）

    離散凸解析は,連続変数に関する最適化(非線形計画)と離散変数に関する最適化(組合せ最適化)を統一的な視点から捉える枠組みとして代表者によって構築された数理計画理論であるが,本研究では,離散凸解析の理論的成果を都市工学や数理経済学という社会科学の分野に応用することを目標として,以下の成果を得た.
    (1) 不可分な財を含む経済均衡理論における効用関数として従来考察されたものの多くがM凸関数であることを指摘した.他方,効用関数にM凸性を仮定することによって一般的な均衡存在定理が得られることを示した.この結果は,M凸性の概念が,経済学でも有用かつ妥当なものであることを示している.以上の知見を,Danilov氏,Koshevoy氏との共著論文の形にまとめて,数理経済学の学術誌に投稿した.
    (2) 離散凸解析は,元来,整数格子点上で定義された整数値関数に関する理論であったが,実数空間上で定義された関数に対してもM/L凸関数の概念を定義し,M凸性とL凸性の共役性を中心に,その基本的な性質を調べた.
    (3) 凸関数を費用関数にもつネットワーク流問題に関するRockafellarの理論を,実数空間上で定義されたM/L凸関数(上記の(2))を用いて拡張することを試みた.費用関数が区分的に線形な(多面体的な)M/L凸関数の場合には厳密な理論を構築できたが,一般の非線型M/L凸関数に対しては,双対定理の解析的な部分の議論にまだ数学的に不完全な点を残している.しかし,少なくとも,これによってネットワーク流問題の枠組みに非分離関数(nonseparable function)を導入することが可能になった.なお,この結果は,実数空間上のM/L凸関数に関する双対定理として位置づけることができる.

    researchmap

  • Study on Convexity in Combinatorial Optimization

    1995年

    　 詳細を見る

    資金種別：競争的資金

    researchmap

  • 組合せ最適化における凸性の研究

    1995年

    　 詳細を見る

    資金種別：競争的資金

    researchmap

▼全件表示