著者

Masato Koda Hiroyuki Okano

出版者

The Operations Research Society of Japan

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.43, no.4, pp.469-485, 2000 (Released:2017-06-27)

参考文献数

17

被引用文献数

4 4

---

A new stochastic learning algorithm using Gaussian white noise sequence, referred to as Subconscious Noise Reaction (SNR), is proposed for a class of discrete-time neural networks with time-dependent connection weights. Unlike the back-propagation-through-time (BTT) algorithm, SNR does not require the synchronous transmission of information backward along connection weights, while it uses only ubiquitous noise and local signals, which are correlated against a single performance functional, to achieve simple sequential (chronologically ordered) updating of connection weights. The algorithm is derived and analyzed on the basis of a functional derivative formulation of the gradient descent method in conjunction with stochastic sensitivity analysis techniques using the variational approach.

著者

Naoya Uematsu Shunji Umetani Yoshinobu Kawahara

出版者

The Operations Research Society of Japan

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.63, no.2, pp.41-59, 2020-04-30 (Released:2020-05-01)

参考文献数

28

---

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-the-art exact algorithms.

著者

Tomoyuki Iori Toshiyuki Ohtsuka

出版者

The Operations Research Society of Japan

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.63, no.4, pp.114-133, 2020-10-31 (Released:2020-10-31)

参考文献数

20

---

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.

著者

Keisuke Sato Yoshitsugu Yamamoto

出版者

The Operations Research Society of Japan

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.52, no.2, pp.112-130, 2009 (Released:2017-06-27)

参考文献数

12

---

This paper presents a study on the recently proposed linear inequality representation of Arrovian Social Welfare Functions (ASWFs). We correct and show several sufficient conditions on preference domains for the linear inequalities of the representation to form integral polytopes. We also show that a given probabilistic ASWF induces a real vector satisfying the inequalities.

著者

YUKIO HATOYAMA

出版者

The Operations Research Society of Japan

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.20, no.3, pp.164-181, 1977 (Released:2017-06-27)

被引用文献数

2 3

---

Discrete time Markov maintenance models are coupled with the theory of control of queues. Each system has an operating machine, spare machines and a repair facility. A decision maker has the option of opening or closing the repair shop when there are machines waiting for repair service, as well as the option of repairing or leaving an operating machine. A two-dimensional control limit policy is defined, and sufficient conditions for the optimality of a two-dimensional control limit policy are obtained for each model.

著者

鳩山 由紀夫

出版者

The Operations Research Society of Japan

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.22, no.2, pp.106-122, 1979 (Released:2017-06-27)

被引用文献数

1 1

---

本論文はDerman(1963)によって導入されたマルコフ型劣化を伴なう機械の保全問題の拡張である。拡張は系が閉じたループをなしていること、取替でなく修理問題であること、及び複数の修理施設をもつことに見られる。即ち、系は、有限個の劣化の状態をもち劣化の進行がマルコフ鎖で記述される単一の稼動機械と、同一機能をもつ有限個の予備機械、及び修理の種類毎に異なる複数の修理施設とからなる。各時点において、稼動機械を修理すべきか否かを決定することが問題となるが、その決定の際に、稼動機械の劣化の程度、修理がなされるときに要求される修理の種類、更に各修理施設で修理中の機械の数が情報として与えられる。修理がなされるときには、機械は修理の種類に対応した修理施設に直わに送られ、修理が開始され、同時に予備機械の一つが新たに稼動を開始する。修理時間は修理施設に依存する幾何分布に従うものとし、修理後は新晶同様の状態に戻ると仮定する。予備機械の用意が間に合わないときには、一つの機械の修理が終了する迄稼動は休止せざるを得ず、この間ペナルティが課せられる。その他のコストとしては、作動費用、材料費及び労賃を考慮している。以上のモデルを設定し、割引率を考慮した総期待費用、乃至は平均期待費用を最小とする最適保全政策が如何なる形となるかを考察する。ここで、修理の種類を固定したとき、稼動機械の劣化がある限界を越えたときのみ修理を施し、又稼動機械の劣化の状態を固定したとき、修理の種類がある限界を越えないときのみ修理を施すという二次元のコントロールリミットポリシーを提案し、緩やかな条件の下で最適政策がこの形となることを示す。次にコスト等を一般化し、更に保全員が各修理施設に一人づつの場合にも同様の議論がなされることを確認し、最後に解法に触れている。

著者

Komei Fukuda Tamas Terlaky

出版者

The Operations Research Society of Japan

雑誌

日本オペレーションズ・リサーチ学会論文誌 (ISSN:04534514)

巻号頁・発行日

vol.35, no.1, pp.45-61, 1992 (Released:2017-06-27)

被引用文献数

5 12

---

A combinatorial abstraction of the linear complementarity theory in the setting of oriented matroids was first considered by M.J. Todd. In this paper, we take a fresh look at this abstraction, and attempt to give a simple treatment of the combinatorial theory of linear complementarity. We obtain new theorems, proofs and algorithms in oriented matroids whose specializations to the linear case are also new. For this, the notion of sufficiency of square matrices, introduced by Cottle, Pang and Venkateswaran, is extended to oriented matroids. Then, we prove a sort of duality theorem for oriented matroids, which roughly states: exactly one of the primal and the dual system has a complementary solution if the associated oriented matroid satisfies "weak" sufficiency. We give two different proofs for this theorem, an elementary inductive proof and an algorithmic proof using the criss-cross method which solves one of the primal or dual problem by using surprisingly simple pivot rules (without any perturbation of the original problem).

著者

林田 智弘 西崎 一郎 菅生 雄矢

出版者

The Operations Research Society of Japan

雑誌

日本オペレーションズ・リサーチ学会和文論文誌 (ISSN:13498940)

巻号頁・発行日

vol.57, pp.27-43, 2014

---

部分ゲーム完全均衡は展開型ゲームに対する均衡概念であり,多くの展開型ゲームにおけるプレイヤーの行動のベンチマークとして用いられている.しかし,展開型ゲームの一種であるムカデゲームに対する被験者実験では,部分ゲーム完全均衡から逸脱する行動が多く観測されたことが報告されている.均衡理論では利得最大化の意味での合理的なプレイヤーが仮定されているが,ゲームが繰り返される場合,被験者は1回のゲームの利得の最大化ではなく,むしろ累積利得を考慮した長期的な視野に基づいた行動選択をしていると考えられる.本論文では,ムカデゲームに対して適応型エージェントを用いたシミュレーションにより,累積利得を考慮した長期的視野および被験者間での非対称性,利得に対するリスク態度などにより被験者の行動が説明できることを示す.