1. SDPA
Project: Solving LargeScale 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 primaldual
interiorpoint method is known as a powerful tool for solving largescale
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 SecondOrder Cone Program} : SOCP)
are available on the Internet.
In 1995, we started the SDPA Project aimed for solving largescale
SDPs with numerical stability and accuracy. The SDPA (SemiDefinite
Programming Algorithm) is a C{\small ++ } implementation
of a Mehrotratype primaldual predictorcorrector interiorpoint
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 largescale 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 SDPARAC is an integration
of two software SDPARA and SDPAC which is a primaldual interiorpoint
method using the positive definite matrix completion technique.
The SDPARAC requires a small amount of memory when we solve sparse
SDPs with a largescale 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 largescale 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,
primaldual interiorpoint 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 branchandcut 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, branchandcut, 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 quasipolynomial 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,
quasipolynomial 
5. Approximating Minimum Cost Multigraphs
of Specified EdgeConnectivity 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 edgeconnectivity
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 selfloops 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 localedgeconnectivity
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 constantfactor 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 edgeconnectivity. 
keywords 
Combinatorial optimization, approximation
algorithm, degree bound, detachment, edgeconnectivity, 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 branchandbound 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. BiCriteria
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 $II'$ 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 bicriteria 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, 01 knapsack problem, dynamic programming 
8. Dual Form of Markov Renewal Equations and an Application
to Asymptotic Analysis of a SingleServer 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 singleserver queue, where its arrival process
is governed by a countablestate Markov chain. This application extends
the existing result for the case with a finitestate 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, singleserver queues, asymptotic analysis, Markovian
arrival streams, stationary workload distribution 
9. A Finite
Population Model and ProductForm 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 productform approximation} in this paper. Under the productform
approximation, the probability that channels are fully occupied in
a cell is given by the Erlangloss formula. We evaluate the accuracy
of the productform approximation through several simulation experiments,
and find that the Erlangloss formula remains applicable to the performance
evaluation and channel provisioning of cellular mobile systems. 
keywords 
Telecommunication, mathematical
modeling, cellular mobile systems, Erlangloss formula, insensitivity

10. Minimum
Underflow Routing for StreamType 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 streamtype communication services.
Typical examples of streamtype services include interactive voice
such as Voice over IP (VoIP) and live video delivery. Stream services
require realtime 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 streamtype communication services. Optimality is discussed
in terms of the continuous playback of packets. From network observations,
we assume that the endtoend 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 endtoend delay. This paper
presents an efficient algorithm for finding the optimal point in
this coordinate system.

keywords 
Telecommunication, routing, underflow,
stream traffic, VoIP 
11. UserOriented
and Perceived Software Availability Measurement and Assessment
with Environmental Factors
Koichi Tokuno and Shigeru Yamada

abstract

This paper proposes the methods of
the operationoriented software availability measurement and assessment.
Considering the difference of the software failureoccurrence 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 customeroriented attribute and defined as the attribute that
the software system can successfully satisfy the end users' requests.
We derive several serviceoriented 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. MultiPeriod
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, multiperiod optimization,
financial planning, investment and insurance strategy, insurance
design 
13. An Invitation
to MarketBased Option Pricing and its Applications
Koichi Miyazaki

abstract

This article provides an overview of marketbased
option pricing and its applications. First, two fundamental approaches
for marketbased 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, marketbased option pricing,
deterministic volatility, implied tree, stochastic volatility, jump,
modelfree, 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 minimumnorm 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 rightleft symmetry and robust ranking that are not
guaranteed by the EM. 
keywords 
AHP, minimumnorm 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 Paretooptimal 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, multicriteria,
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 
