社団法人 日本オペレーションズ・リサーチ学会
ENGLISH
入会申込み お問合わせ
HOME オペレーションズ・リサーチ学会とは 研究活動案内 OR事典Wiki 機関誌 論文誌 会員の方へ
活動概要
会長挨拶
支部紹介
 

HOME > 論文誌  > JORSJ論文概要 

63-1 63-2 63-3 63-4

JORSJ 63-1

1.
ONE-WAY TRADING PROBLEMS VIA LINEAR OPTIMIZATION
Hiroshi Fujiwara (Shinshu University) Naohiro Araki (Microtech Corp.) Hiroaki Yamamoto (Shinshu University)
In the one-way trading problem, we are asked to convert dollars into yen only by unidirectional conversions, while watching the exchange rate that fluctuates along time. The goal is to maximize the amount of yen we finally get, under the assumption that we are not informed of when the game ends. For this problem, an optimal algorithm was proposed by El-Yaniv et al. In this paper we formulate this problem into a linear optimization problem(linear program)and reduce derivation of an optimal algorithm to solving the linear optimization problem. This reveals that the optimality of the algorithm follows from the duality theorem. Our analysis demonstrates how infinitedimensional linear optimization helps to design algorithms.
2.
MONTE CARLO ALGORITHM FOR CALCULATING THE SHAPLEY VALUES OF MINIMUM COST SPANNING TREE GAMES
Kazutoshi Ando, Koichi Takase (Shizuoka University))

In this paper, we address a Monte Carlo algorithm for calculating the Shapley values of minimum cost spanning tree games. We provide tighter upper and lower bounds for the marginal cost vector and improve a previous studyʼs lower bound on the number of permutations required for the output of the algorithm to achieve a given accuracy with a given probability. In addition, we present computational experiments for estimating the lower bound on the number of permutations required by the Monte Carlo algorithm.

ページトップへ戻る

JORSJ 63-2

1.
An Efficient Branch-and-Cut Algorithm for Submodular Function Maximization
Naoya Uematsu, Shunji Umetani (Osaka University/RIKEN Center for Advanced Intelligence Project) Yoshinobu Kawahara (Kyushu University/ RIKEN Center for Advanced Intelligence Project)
The submodular function maximization is an attractive optimization model that appears in many real applications. Although a variety of greedy algorithms quickly find good feasible solutions for many instances while guaranteeing (1 - 1/e)- approximation ratio, we still encounter many real applications that ask optimal or better solutions within reasonable computation time. In this paper, we present an efficient branch-and-cut algorithm for the non-decreasing submodular function maximization problem based on its binary integer programming (BIP) formulation with an exponential number of constraints. Nemhauser and Wolsey developed an exact algorithm called the constraint generation algorithm that starts from a reduced BIP problem with a small subset of constraints and repeats solving a reduced BIP problem while adding a new constraint at each iteration. However, their algorithm is still computationally expensive due to many reduced BIP problems to be solved. To overcome this, we propose an improved constraint generation algorithm to add a promising set of constraints at each iteration. We incorporate it into a branch-and-cut algorithm to attain good upper bounds while solving a smaller number of reduced BIP problems. According to computational results for well-known benchmark instances, our algorithm achieves better performance than the state-of-theart exact algorithms.
2.
Improving Approximation Ratios for the Clustered Traveling Salesman Problem
Masamune Kawasaki (Tokyo Institute of Technology) Kenjiro Takazawa (Hosei University)

The clustered traveling salesman problem (CTSP) is a generalization of the traveling salesman problem (TSP) in which the set of cities is divided into clusters and the salesman must consecutively visit the cities of each cluster. It is well known that TSP is NP-hard, and hence CTSP is NP-hard as well. Guttmann-Beck et al. (2000) designed approximation algorithms for several variants of CTSP by decomposing it into subproblems including the traveling salesman path problem (TSPP). In this paper, we improve approximation ratios by applying a recent improved approximation algorithm for TSPP by Zenklusen (2019).

ページトップへ戻る

JORSJ 63-3

1.
A NOTE ON A NEARLY UNIFORM PARTITION INTO COMMON INDEPENDENT SETS OF TWO MATROIDS
Satoru Fujishige(RIMS, Kyoto University) Kenjiro Takazawa(Hosei University)
The present note is a strengthening of a recent paper by K. Takazawa and Y. Yokoi (A generalizedpolymatroid approach to disjoint common independent sets in two matroids, Discrete Mathematics (2019)). For given two matroids on E, under the same assumption in their paper to guarantee the existence of a partition of E into k common independent sets of the two matroids, we show that there exists a nearly uniform partition P of E into k common independent sets, where the difference of the cardinalities of any two sets in P is at most one.
2.
A NOTE ON ACCELERATED PROXIMAL GRADIENT METHOD FOR ELASTOPLASTIC ANALYSIS WITH TRESCA YIELD CRITERION
Wataru Shimizu(IHI Corporation) Yoshihiro Kanno(The University of Tokyo

Diverse accelerated first-order methods have recently received considerable attention for solving large-scale convex optimization problems. This short paper shows that an exiting accelerated proximal gradient method for solving quasi-static incremental elastoplastic problems with the von Mises yield criterion can be naturally extended to the Tresca yield criterion.


ページトップへ戻る

JORSJ 63-4

1.
ASSET ALLOCATION WITH ASSET-CLASSBASED AND FACTOR-BASED RISK PARITY APPROACHES
Hirotaka Kato Norio Hibiki(Keio University)
The asset allocation strategy is important to manage assets effectively. In recent years, the risk parity strategy has become attractive to academics and practitioners. The risk parity strategy determines the allocation for asset classes in order to equalize their contributions to overall portfolio risk. Roncalli and Weisang(2016)propose the use of “risk factors” instead of asset classes. This approach achieves the portfolio diversification based on the decomposition of portfolio risk into risk factor contribution. The factor-based risk parity approach can diversify across the true sources of risk whereas the asset-class-based approach may lead to solutions with hidden risk concentration. However, it has some shortcomings. In our paper, we propose a methodology of constructing the well-balanced portfolio by the mixture of asset-class-based and factor-based risk parity approaches. We also propose the method of determining the weight of two approaches using the diversification index. We can construct the portfolio dynamically controlled with the weight which is adjusted in response to market environment. We examine the characteristics of the model through the numerical tests with seven global financial indices and three factors. We find it gives the well-balanced portfolio between asset and factor diversifications. We also implement the backtest from 2005 to 2018, and the performances are measured on a USD basis. We find our method decreases standard deviation of return and downside risk, and it has a higher Sharpe ratio than other portfolio strategies. These results show our new method has practical advantages.
2.
LIMIT OPERATION IN PROJECTIVE SPACE F O R C O N S T R U C T I N G N E C E S S A RY OPTIMALITY CONDITION OF POLYNOMIAL OPTIMIZATION PROBLEM
Tomoyuki Iori, Toshiyuki Ohtsuka (Kyoto University

This paper proposes a necessary optimality condition derived by a limit operation in projective space for optimization problems of polynomial functions with constraints given as polynomial equations. The proposed condition is more general than the Karush-Kuhn-Tucker(KKT)conditions in the sense that no constraint qualification is required, which means the condition can be viewed as a necessary optimality condition for every minimizer. First, a sequential optimality condition for every minimizer is introduced on the basis of the quadratic penalty function method. To perform a limit operation in the sequential optimality condition, we next introduce the concept of projective space, which can be regarded as a union of Euclidian space and its points at infinity. Through the projective space, the limit operation can be reduced to computing a point of the tangent cone at the origin. Mathematical tools from algebraic geometry were used to compute the set of equations satisfied by all points in the tangent cone, and thus by all minimizers. Examples are provided to clarify the methodology and to demonstrate cases where some local minimizers do not satisfy the KKT conditions.


ページトップへ戻る
HOMEに戻る
カレンダー
日 程:2021/10/9(土)
場所:オンライ ン開催
テーマ:地理情 報システム入門
シンポジウム
2021 年春季シンポジウム
開催終了しました。
日 程:2021/3/1(月)
場所:東 京工業大学
(オ ンライン開催)
2021 年秋季シンポジウム
日程:2021/9/15 (水)
場所:九 州大学
(オ ンライン開催)
研究発表会
2021 年春季研究発表会
開催終了しました。
日程:2021/
3/2(月)~3(水)
場所:東 京工業大学
(オ ンライン開催)
2021 年秋季研究発表会
日程:2021/
9/16(水)~17(金)
場所:九 州大学
(オ ンライン開催)
= 会場開催についてのお知らせ=
「新型コロナウイルス感染予防のため、以下について、予め御了承いただけますよう、よろしくお願い 申し上げます。」

● 新型コロナウイルス感染拡大の状況によっては、イベントの開催を中止させていただく場合がございます。 ご来場前に必ず当該イベントのホームページにて開催の有無をご確認下さ い。

●参加者の皆様へのお願い
・発熱、強い倦怠感等の症状がある方は御来場を御遠慮下さい。

・感染予防のため、スタッフはマスクを着用している場合があることを御了承下さい。