Tetsuya Fujie

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.

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.

In this paper, we discuss a two-machine flowshop problem with the objective of minimizing the total flow time subject to minimum makespan. The problem is known as one of the hierarchical multicriteria scheduling problems which are a variant of the multicriteria scheduling problems. The problem is known to be NP-hard in general. T'kindt et al. provided a branch-and-bound algorithm to find an optimal schedule for the problem and reported that their algorithm solved problem instances effectively with up to 23 jobs. The purpose of this paper is to improve the branch-and-bound algorithm based on a generalization of a subproblem representation and new dominance relations. In most branch-and-bound algorithms for scheduling problems, a subproblem representation which fixes some jobs at the head of the schedule is used. In this paper, we use a more flexible subproblem representation in which jobs both at the head and at the end of the schedule are fixed. We show that existing dominance relations can be generalized and then propose some new relations. Dominance tests based on the dominance relations are incorporated into the branch-and-bound algorithm. The computational result shows that our algorithm works successfully to solve problem instances with up to 29 jobs. Furthermore, our algorithm outperforms an algorithm proposed by T'kindt et al. and a recent mixed integer programming solver.

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.

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 0-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.