藤江 哲也

The smallest positive eigenvalue of the Laplacian of a network is called the spectral gap and characterizes various dynamics on networks. We propose mathematical programming methods to maximize the spectral gap of a given network by removing a fixed number of nodes. We formulate relaxed versions of the original problem using semidefinite programming and apply them to example networks. © Springer-Verlag Berlin Heidelberg 2013.

We study a polytope which arises from a mixed integer programming formulation of the quadratic semi-assignment problem. We introduce an isomorphic projection and transform the polytope to a tractable full-dimensional polytope. As a result, some basic polyhedral properties, such as the dimension, the affine hull, and the trivial facets, are obtained. Further, we present valid inequalities called cut- and clique-inequalities and give complete characterizations for them to be facet-defining. We also discuss a simultaneous lifting of the clique-type facets. Finally, we show an application of the quadratic semiassignment problem to hub location problems with some computational experiences. (C) 2008 Elsevier B.V. All rights reserved.

ParaLEX, developed recently by the authors, is a parallel extension for the CPLEX mixed integer optimizer which is known as one of the fastest commercial solvers for the mixed integer programming problems. In our previous work, we showed that ParaLEX could efficiently perform 30 solver parallelizations. On the other hand, the simple load balancing mechanism of ParaLEX did not obviously have scalability In this paper, we propose a load balancing mechanism for a new version of ParaLEX. Preliminary computational results show that the load balancing mechanism is quite efficient in solving a lot of classes of problem instances.

The ILOG CPLEX Mixed Integer Optimizer is a state-of-the-art solver for mixed integer programming. In this paper, we introduce ParaLEX which realizes a master-worker parallelization specialized for the solver on a PC cluster using MPI. To fully utilize the power of the solver, the implementation exploits almost all functionality available in it. Computational experiments are performed for MIPLIB instances on a PC cluster composed of fifteen 3.4GHz pentiumD 950 (with 2G bytes RAM) PCs (running a maximum of 30 CPLEX Mixed Integer Optimizers). The results show that ParaLEX is highly effective in accelerating the solver for hard problem instances.

Recently, a semi-definite programming relaxation method (SDP relaxation) for the design problem of FIR filters with SP2 coefficients is proposed. In this paper, we propose a new linear programming relaxation method (LP relaxation) with triangle inequalities based on, the SDP relaxation method. Here, the polynomiality of the method is guaranteed by exploiting the interior point methods to solve the LP relaxation problem. We will compare the LP relaxation methods proposed here and the SDP relaxation methods through numerical experiments and show that, the quality of the solution for the LP relaxation method is better than, that of SDP relaxation method.

In this paper, we consider a three-machine permutation flow-shop scheduling problem where the criterion is to minimize the total completion time without idle times subject to the minimum makespan on the second machine. This problem is NP-hard while each of the objective functions alone can be optimized in polynomial time. We develop a branch-and-bound algorithm with effective branching rules and dominance properties which help to reduce the search space. By our computational experiments, the branch-and-bound algorithm is comparable to a recent mixed integer programming solver and, for some kinds of problem instances, the branch-and-bound algorithm outperforms the solver. On the other hand, the computational result would indicate that the hierarchical scheduling problems are essentially hard in both theoretical and computational points of view.

情報化社会といわれる今日,おびただしい量の情報を、コンピュータを使ってどう経営に活用するかは企業経営にとって重要な課題である.中でも通信技術の発達は,迅速な意思決定や経営判断を迫られる現代においては欠かせない重要な技術といえる.そのため,通信技術のひとつであるディジタルフィルタの研究においてもここ30年でめざましい成果があげられている.ディジタルフィルタは,ディジタル計測,ディジタル通信等において中心的な役割をなす信号処理回路であり、その設計における精度の高さのレベルや設計の高速化といった問題が非常に重要な研究課題のひとつとなっている.そこで、本稿では、最適化手法のひとつである線形計画問題(LP)を緩和した問題に三角不等式を付加した方法および2次錐計画問題による緩和をもちいたディジタルフィルタの新たな設計方法を提案し,比較実験を行ったのでその結果も報告する.In this paper, we propose a new approach for designing digital filters by one of the optimization methods, "second order cone problem relaxation (SOCP)" based on the semidefinite programming (SDP) relaxation methods. And we show the solution with our proposed design method is better than that with SDP relaxation method through several numerical experiments.

In this paper, we generalize the theory of a convex set relaxation for the maximum weight stable set problem due to Grotschel, Lovasz and Schrijver to the generalized stable set problem. We define a convex set which serves as a relaxation problem, and show that optimizing a linear function over the set can be done in polynomial time. This implies that the generalized stable set problem for perfect bidirected graphs is polynomial time solvable. Moreover, we prove that the convex set is a polytope if and only if the corresponding bidirected graph is perfect. The definition of the convex set is based on a semidefinite programming relaxation of Lovasz and Schrijver for the maximum weight stable set problem, and the equivalent representation using infinitely many convex quadratic inequalities proposed by Fujie and Kojima is particularly important for our proof.

本稿では,総所要時間最小のスケジュールの中で総滞留時間を最小化するものを求める二機械フローショップ問題を考える.この問題は,複数の目的関数に優先順位が与えられる,階層的多目的スケジューリング問題の一つとして知られている.一般にこの問題はNP困難であり,分枝限定法がT'kindt et al.により提案され,ジョブ数23の問題まで効率的に解くことができたと報告している.本稿では,子問題表現の一般化と新しい優越関係に基づく分枝限定法の改善を行う.この改善により,ジョブ数29の問題まで効率的に解くことができるようになった.さらに,提案した分枝限定法は,T'kindt et al.の分枝限定法および混合整数計画問題を解く商用ソフトウェアと比較した結果,最も高速であり,かつ最も大規模な問題を扱うことができた.

The Maximum Leaf Spanning Tree Problem (MLSTP) is to find a spanning tree in a given undirected graph, whose number of leaves (vertices of degree 1) is maximum. In this article, we consider an integer programming approach to the MLSTP. We provide two formulations of the MLSTP and study the facial structure of polytopes arising from the formulations. Moreover, several relaxation problems are compared. (C) 2004 Wiley Periodicals, Inc.

The dominance test is a bounding operation in branch-and-bound algorithms, where each subproblem is examined whether it can be terminated or not by comparing, implicitly or explicitly, with another subproblem. For a single machine scheduling problem with release dates to minimize total flow time, Chu [5] proposed a branch-and-bound algorithm with a dominance test based on already known and new dominance properties and reported that the dominance test works successfully to solve problem instances exactly with up to 100 jobs. On the other hand, a naive combination of these dominance properties may delete all of the optimal solutions. The purpose of this paper is to point out such a pitfall and then propose a way to avoid it. Furthermore, new dominance properties based on the property developed by Chu [5] are proposed. Computational experiments are performed to see how often the branch-and-bound algorithm with a naive dominance test fails and to show an effectiveness of our branch-and-bound algorithm.

Given a connected graph, the Maximum Leaf Spanning Tree Problem (MLSTP) is to find a spanning tree whose number of leaves (degree-one vertices) is maximum. We propose a branch-and-bound algorithm for MLSTP, in which an upper bound is obtained by solving a minimum spanning tree problem. We report computational results for randomly generated graphs and grid graphs with up to 100 vertices.

In this paper, we introduce a new method of parallelizing a MIP (Mixed Integer Programming) solver. This method is different from a standard implementation that constructs a parallel branch-and-cut algorithm from scratch (except using an LP solver). The MIP solver we use is ILOG-CPLEX MIP Optimizer (Version 8.0), which is one of the most efficient implementations of branch-and-cut algorithms. The parallelization of the solver is performed by using the software tool PUBB2 developed by the authors. We report a part of our computational experience using up to 24 processors. In addition, we point out some problems that should be resolved for a more efficient parallelization.

Grotschel, Lovasz and Schrijver introduced a convex set containing the stable set polytope of a graph. They proved that the set is a polytope if and only if the corresponding graph is perfect. In this paper, we give an alternative proof of the fact based on a new representation of the convex set described by infinitely many convex quadratic inequalities.

最大リーフ全域木問題とは，連結無向グラフGの全域木の中で，リーフ（次数1の頂点）数が最大のものを求める問題である．この問題はNP?困難であり，いくつかの近似解法，すなわち下界値計算が提案されている．これに対し，本稿では，上界値計算に関連した議論を行う．まず，この問題の0?1整数計画問題としての定式化を2通り与える．次に，各定式化について，定式化に用いた不等式が，実行可能解集合の凸包として定義される多面体の極大面を定める必要十分条件を与える．最後に，緩和問題について触れる．Given an undirected graph G, the Maximum-Leaf Spanning Tree Problem is to find a spanning tree in G, whose number of leaves (degree-1 vertices) is maximum. The problem is NP-hard, and several approximation algorithms, that is, lower bounding computations, are proposed. This paper concerns with upper bounding computations. First, we provide two kinds of O-1 integer programming formulations of the problem. Next, we give necessary and sufficient conditions that the constraints in each formulation define facets of a polytope which is defined as a convex hull of the set of feasible solutions. Finally, relaxation problems are considered.