

 1.
 ONEWAY TRADING PROBLEMS VIA
LINEAR OPTIMIZATION
Hiroshi Fujiwara （Shinshu University）
Naohiro Araki （Microtech Corp.）
Hiroaki Yamamoto （Shinshu University）
 In the oneway 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 ElYaniv 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.


 1.
 An Efficient BranchandCut 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 branchandcut algorithm
for the nondecreasing 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 branchandcut algorithm to attain good upper
bounds while solving a smaller number of reduced
BIP problems. According to computational results
for wellknown benchmark instances, our algorithm
achieves better performance than the stateoftheart 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 NPhard,
and hence CTSP is NPhard as well. GuttmannBeck
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).


 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 firstorder methods have
recently received considerable attention for solving
largescale convex optimization problems. This
short paper shows that an exiting accelerated
proximal gradient method for solving quasistatic
incremental elastoplastic problems with the von
Mises yield criterion can be naturally extended to
the Tresca yield criterion.


 1.
 ASSET ALLOCATION WITH ASSETCLASSBASED AND FACTORBASED 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 factorbased risk parity approach
can diversify across the true sources of risk whereas
the assetclassbased approach may lead to solutions
with hidden risk concentration. However, it has
some shortcomings. In our paper, we propose a
methodology of constructing the wellbalanced
portfolio by the mixture of assetclassbased and
factorbased 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 wellbalanced 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 KarushKuhnTucker（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.





 日
程：2021/10/9(土）
 場所：オンライ
ン開催
 テーマ：地理情
報システム入門

＝ 会場開催についてのお知らせ＝
「新型コロナウイルス感染予防のため、以下について、予め御了承いただけますよう、よろしくお願い 申し上げます。」
● 新型コロナウイルス感染拡大の状況によっては、イベントの開催を中止させていただく場合がございます。
ご来場前に必ず当該イベントのホームページにて開催の有無をご確認下さ い。
●参加者の皆様へのお願い
・発熱、強い倦怠感等の症状がある方は御来場を御遠慮下さい。
・感染予防のため、スタッフはマスクを着用している場合があることを御了承下さい。

