入会申込み お問合せ ENGLISH

JORSJ Vol. 50 No. 4 Abstract & Keywords

 A Special Issue on the 50th Anniversay of the Operations Research Society of Japan

トップページへ戻ります
JORSJ TOP

1. SDPA Project: Solving Large-Scale Semidefinite Programs

Katsuki Fujisawa, Kazuhide Nakata, Makoto Yamashita, and Mituhiro Fukuda

abstract  The Semidefinite Program (SDP) has recently attracted much attention of researchers in various fields for the following reasons: (i) It has been intensively studied in both theoretical and numerical aspects. Especially the primal-dual interior-point method is known as a powerful tool for solving large-scale SDPs with accuracy. (ii) Many practical problems in various fields such as combinatorial optimization, control and systems theory, robust optimization and quantum chemistry can be modeled or approximated by using SDPs. (iii) Several software packages for solving SDPs and related problems (ex. \red{the Second-Order Cone Program} : SOCP) are available on the Internet.

In 1995, we started the SDPA Project aimed for solving large-scale SDPs with numerical stability and accuracy. The SDPA (SemiDefinite Programming Algorithm) is a C{\small ++ } implementation
of a Mehrotra-type primal-dual predictor-corrector interior-point method for solving the standard form SDP and its dual. We have also developed some variants of the SDPA to handle SDPs with various features. The SDPARA is a parallel version of the SDPA on multiple processors and distributed memory, which replaces two major bottleneck components of the SDPA by their parallel implementation using MPI and ScaLAPACK. The SDPARA on parallel computer has attractive features; it can load a large-scale SDP into the distributed memory and solve it in a reasonable time.
In this paper, we show through some numerical experiments that the SDPARA attains high performance. The SDPARA-C is an integration of two software SDPARA and SDPA-C which is a primal-dual interior-point method using the positive definite matrix completion technique. The SDPARA-C requires a small amount of memory when we solve sparse SDPs with a large-scale matrix variable and/or a large number of equality constraints. The paper also explains a grid portal system for solving SDPs, which we call the SDPA Online Solver.

In this paper, we review the major achievements of the SDPA Project on solving large-scale SDPs. This paper provides an introductory and comprehensive materials for researchers who are interested in practical computational aspects of
the SDPs.

keywords

Optimization, semidefinite program, primal-dual interior-point method, parallel computing, grid computing

2. Stochastic Programming Problem with Fixed Charge Recourse

Takayuki Shiina, Yu Tagaya, and Susumu Morito

abstract  In this paper, we introduce a class of stochastic programming problem with fixed charge recourse
in which a fixed cost is imposed if the value of the continuous recourse variable is strictly positive.
The algorithm of a branch-and-cut method to solve the problem is developed by using the property of the expected recourse function. Then, the problem is applied to a power generating system. The numerical experiments show that the proposed algorithm is quite efficient. The mathematical programming model defined in this paper is quite useful for a variety of design and operational problems.
keywords

Stochastic optimization, stochastic programming with fixed charge recourse, branch-and-cut, generation planning

3. Linking Systems and Matroid Pencils

Satoru Iwata

abstract  A matroid pencil is a pair of linking systems having the same ground sets in common. It provides a combinatorial abstraction of matrix pencils. This paper investigates the properties of matroid pencils analogous to the theory of Kronecker canonical form. As an application, we give a simple alternative proof for a theorem of Murota on power products of linking systems.
keywords

Combinatorial optimization, matroid theory

4. Enumerating Spanning and Connected Subsets in Graphs and Matroids

Leonid Khachiyan, Endre Boros, Konrad Borys, Khaled Elbassioni, Vladimir Gurvich, and Kazuhisa Makino Kazuhisa

abstract  We show that enumerating all minimal spanning and connected subsets of a given matroid can be solved in incremental quasi-polynomial time. In the special case of graphical matroids, we improve this complexity bound by showing that all minimal $2$-vertex connected subgraphs of a given graph can be generated in incremental polynomial time.
keywords

Algorithm, matroid, enumeration, quasi-polynomial

5. Approximating Minimum Cost Multigraphs of Specified Edge-Connectivity under Degree Bounds

Takuro Fukunaga and Hiroshi Nagamochi

abstract  In this paper, we consider the problem of constructing a minimum cost graph with a specified edge-connectivity under a degree constraint. For a set $V$ of vertices, let $r: {V \choose 2}\rightarrow \Zset_+$ be a connectivity demand, $a: V \rightarrow \Zset_+$ be a lower degree bound, $b: V \rightarrow \Zset_+$ be an upper degree bound, and $c: {V \choose 2}\rightarrow \Qset_+$ be a metric edge cost. The problem $(V,r,a,b,c)$ asks to find a minimum cost multigraph $G=(V,E)$ with no self-loops such that $\lambda(u,v) \geq r(u,v)$ holds for each vertex pair $u,v \in V$ and
$a(v) \leq d(v) \leq b(v)$ holds for each vertex $v \in V$, where $\lambda(u,v)$ (resp., $d(v)$) denotes the local-edge-connectivity between $u$ and $v$ (resp., the degree of $v$) in $G$.
We reveal several conditions on functions $r,a,b$ and $c$ for which the above problem admits a constant-factor approximation algorithm.
For example, we give a $(2+ 2/k)$-approximation algorithm to $(V,r,a,b,c)$ with $r(u,v) \geq 2$, $u,v \in V$ and a uniform $b(v)$, $v \in V$, where $k=\min_{u,v \in V}r(u,v)$. To design the algorithms in this paper, we derive new results on splitting and detachment, which are graph transformations to split vertices into several copies of them while preserving edge-connectivity.
keywords Combinatorial optimization, approximation algorithm, degree bound, detachment, edge-connectivity, network design, splitting

6. Relaxation Heuristics for the Set Covering Problem

Shunji Umetani and Mutsunori Yagiura

abstract  The set covering problem (SCP) is one of representative combinatorial optimization problems, which has many practical applications. The continuous development of mathematical programming has derived a number of impressive heuristic algorithms as well as exact branch-and-bound algorithms, which can solve huge SCP instances of bus, railway and airline crew scheduling problems. We survey heuristic algorithms for SCP focusing mainly on contributions of mathematical programming techniques to heuristics, and illustrate their performance through experimental analysis.
keywords Combinatorial optimization, set covering problem, linear programming, Lagrangian relaxation, subgradient method, heuristic algorithm

7. Bi-Criteria Food Packing by Dynamic Programming

Yoshiyuki Karuno, Hiroshi Nagamochi, and Xiaoming Wang

abstract  In this paper, we deal with a certain type of automated food packing system with $n$ hoppers.
The system repeats throwing some amount of foods into empty hoppers to make all hoppers full of foods, and collecting the foods from several hoppers to pack them into a single package.
We treat foods thrown into each hopper as an item $i$ with an integer weight $w_{i}$.
Given a set $I$ of $n$ items in the hoppers, the packing system chooses a subset $I'$~$(\subseteq I)$ of items, and puts them into a package so that the total weight of items is at least a specified target weight $B$. The packing system then throws new items into the empty hoppers, and the set $I$ is updated to be the union of the remaining items in $I-I'$ and the new items. Repeating such packing operations, it produces a large number of packages one by one. In the packing system, an item may stay for a long time in some hopper until it is chosen for packing. To avoid such a situation, we introduce a priority $\gamma_{i}$ for each item $i$, and formulate the problem of choosing a subset $I'$ as a bi-criteria discrete optimization problem in which one objective is to minimize
$\sum_{i \in I'} w_{i}$ such that $\sum_{i \in I'} w_{i} \geq B$ must be satisfied, and the other is to
maximize $\sum_{i \in I'} \gamma_{i}$. %

In this paper, we propose an $O(n^{2}w_{max})$ time algorithm based on dynamic programming
to obtain a nondominated solution, where $w_{max}$ is an upper bound on the weight of an item.
We also report the results on computational experiments conducted to examine the performance of the proposed approach.

keywords

Discrete optimization, automated food packing, 0-1 knapsack problem, dynamic programming

8. Dual Form of Markov Renewal Equations and an Application to Asymptotic Analysis of a Single-Server Queue

Naoto Miyoshi

abstract  We propose dual form of Markov renewal equations. While the dual form is theoretically equivalent to the classical standard form of Markov renewal equation, it is shown to be a useful tool for analysis of recent stochastic models. To demonstrate the power of the dual form of Markov renewal equations,
we apply one to tail asymptotic analysis of the stationary workload distribution for a single-server queue, where its arrival process is governed by a countable-state Markov chain. This application extends the existing result for the case with a finite-state Markov chain. We find that our approach with the dual form of Markov renewal equation gives a more straightforward proof than those in the previous works and makes the extension simple.
keywords

Applied probability, Markov renewal equations, single-server queues, asymptotic analysis, Markovian arrival streams, stationary workload distribution

9. A Finite Population Model and Product-Form Approximation for Cellular Mobile Systems with Traveling Users

Shigeo Shioda, Kenji Ohtsuka, and Fumiaki Machihara

abstract  We propose a new finite population model for cellular mobile systems with traveling users. In this model, mobile users arrive according to a Poisson process from outside the system, independently travel in the system, and leave the system in due time. A mobile user is either in call (active) or out of call (inactive). We find that if two minor modifications are made to the model, the joint distribution of the number of calls in progress in each cell has the product form. Making the two modifications is referred to as {\it product-form approximation} in this paper. Under the product-form approximation, the probability that channels are fully occupied in a cell is given by the Erlang-loss formula. We evaluate the accuracy of the product-form approximation through several simulation experiments, and find that the Erlang-loss formula remains applicable to the performance evaluation and channel provisioning of cellular mobile systems.
keywords

Telecommunication, mathematical modeling, cellular mobile systems, Erlang-loss formula, insensitivity

10. Minimum Underflow Routing for Stream-Type Communication Services

Masaki Aida, Chisa Takano, and Shunichi Osawa

abstract 

The Internet of today supports various types of communication services including not only conventional data communication services but also stream-type communication services. Typical examples of stream-type services include interactive voice such as Voice over IP (VoIP) and live video delivery. Stream services require real-time packet transmission, and the continuous playback of packets at the receiver side. As a result, they are not only sensitive to the absolute value of the delay, but also sensitive to delay variations. This paper addresses the problem of optimal routing for stream-type communication services. Optimality is discussed in terms of the continuous playback of packets. From network observations, we assume that the end-to-end delay statistics conform to a normal distribution. We model a network as a weighted graph with its link weights representing link delays. In the course of the analysis, we show that this type of routing optimization problem can be formulated as a process of searching for a specific point in a coordinate system defined by the mean and variance of the end-to-end delay. This paper presents an efficient algorithm for finding the optimal point in this coordinate system.

keywords Telecommunication, routing, underflow, stream traffic, VoIP

11. User-Oriented and -Perceived Software Availability Measurement and Assessment with Environmental Factors

Koichi Tokuno and Shigeru Yamada

abstract  This paper proposes the methods of the operation-oriented software availability measurement and assessment. Considering the difference of the software failure-occurrence phenomena and the restoration characteristics between the testing and the operation phases, we first introduce the environmental factors into the existing Markovian software availability model. Next we discuss the stochastic modeling for measuring software service availability; this is one of the customer-oriented attribute and defined as the attribute that the software system can successfully satisfy the end users' requests. We derive several service-oriented software availability assessment measures which are given as the functions of time and the number of debuggings. Finally, we present several numerical examples of these measures for software service availability analysis.
keywords

Reliability, software service availability, operational phase, Markov process, environmental factor, software reliability growth

12. Multi-Period Optimization Model for a Household, and Optimal Insurance Design

Norio Hibiki

abstract  We discuss an optimization model to obtain an optimal investment and insurance strategy for a household. In this paper, we extend the studies in Hibiki and Komoribayashi~\cite{[HK_2006]}. We introduce the following points, and examine the model with numerical examples. % \begin{namelist}{ Xx} \item[ \maru{1}] We consider cash flow due to a serious disease and involve medical insurance.
\item[ \maru{2}] An optimization model is formulated with term life insurance which variable nsurance money is received. \item[ \maru{3}] We propose a model to decide optimal life and medical insurance money received at each time. \item[ \maru{4}] Sampling error is examined with 100 kinds of 5,000 sample paths. \vls{0.5} \end{namelist}
keywords

Finance, multi-period optimization, financial planning, investment and insurance strategy, insurance design

13. An Invitation to Market-Based Option Pricing and its Applications

Koichi Miyazaki

abstract  This article provides an overview of market-based option pricing and its applications. First, two fundamental approaches for market-based option pricing from the literature are introduced. Then, three important new processes, the deterministic volatility model, the stochastic volatility model, and a model including jump, are discussed. Finally, several empirical analyses on the NIKKEI225 option market are provided as examples.
keywords Finance, market-based option pricing, deterministic volatility, implied tree, stochastic volatility, jump, model-free, characteristic function, fast Fourier transform, NIKKEI225 option

14. Matrix Balancing Problem and Binary AHP

Koichi Genma, Yutaka Kato, and Kazuyuki Sekitani

abstract  A matrix balancing problem and an eigenvalue problem are transformed into two minimum-norm point problems whose difference is only a norm. The matrix balancing problem is solved by scaling algorithms that are as simple as the power method of the eigenvalue problem. This study gives a proof of global convergence for scaling algorithms and applies the algorithm to Analytic Hierarchy process (AHP), which derives priority weights from pairwise comparison values by the eigenvalue method (EM) traditionally. Scaling algorithms provide the minimum $\chi$ square estimate from
pairwise comparison values. The estimate has properties of priority weights such as right-left symmetry and robust ranking that are not guaranteed by the EM.
keywords

AHP, minimum-norm point, matrix scaling, binary AHP, rank reversal

15. Quadratic Ordered Median Location Problems

Yoshiaki Ohsawa, Naoya Ozaki, Frank Plastria, and Kazuki Tamura

abstract  The criteria used in location analysis have to be chosen according to the character of the facility.
The single facility location models addressed in this paper accommodate simultaneous multiple criteria in a continuous space in the framework of ordered median problems, which generate and unify many standard location problems. We demonstrate that tools of computational geometry such as Voronoi diagrams and arrangements of curves and lines, enable us to identify the entire set of Pareto-optimal locations, when the squared Euclidean distances between the facility and affected inhabitants are used. For two objectives this works for any type of ordered median objectives and any polygonally bounded feasible region. When more than two criteria are present the objectives and the feasible region have to be convex. For the analysis of this last case we extend several recent structural results for unconstrained convex vector optimization to a convex and compact constraint. Our findings are illustrated by several examples.
keywords

Facility planning, location, multi-criteria, quadratic Euclidean distance, Pareto solutions, ordered median problem, Voronoi diagrams, arrangements of curves

16. Bounds for Staff Size in Home Help Staff Scheduling

Atsuko Ikegami and Aki Uno

abstract  Home help organizations provide services at respective users' homes at a time that is convenient for the user. Helpers with time window constraints for their working hours must be assigned to these services to ensure that the services are provided. Producing adequate schedules usually takes
the schedulers a considerable amount of time due to many types of constraints and requirements.
It is difficult even to estimate the number of helpers needed.

In this paper, we introduce a mathematical programming formulation of the home help staff scheduling problem, and propose two types of lower bounds for the number of helpers needed on a specific day.
We then also calculate the number of helpers using a simple heuristic algorithm in order to determine the upper bound. Combining the bounds with the information obtained when determining the bounds was shown to be useful for arranging the appropriate helpers for each day before making a detailed schedule, even though each of the algorithms that obtains the bounds is very simple.

keywords

Health care, staff scheduling, mathematical modeling, transportation, network flow

 

JORSJ TOP