Current Position
- Research Scientist, Center for Logistics Research, Nagivation & Logistics Engineering Department, National Maritime Research Institute, Tokyo, Japan
Education
- [March 2009] Doctor of Science , Mathematical and Computing Sciences, Tokyo Institute of Technology, Tokyo, Japan.
- [October 2002 - September 2006] Doctor student, Dept. of Mathematical and Computing Sciences, Tokyo Insitute of Technology, Tokyo, Japan.
- [March 2000] Master of Engineering, Mathematical Engineering, University of Tokyo, Tokyo, Japan.
- [March 1998] Bachelor of Engineering, Mathematical Engineering, University of Tokyo, Tokyo, Japan.
Employment
- [April 2009 -] Research Scientist, National Maritime Research Institute.
- [April 2007 - March 2009] Post-doctoral Research Associate, National Maritime Research Institute.
- [September 2006 - March 2007] Part-time Research Associate, Center for Logistics Research, National Maritime Research Institute.
- [April 2000 - September 2002] Customer-support Engineer, IBM Japan, Ltd.
Refereed Publications
- K. Kobayashi and M. Kubo, "Optimization of Oil Tanker Schedules by Decomposition, Column Generation, and Time-Space Network Techniques", to appear in Japan Journal of Industrial and
Applied Mathematics., 2010
- Ship scheduling problem is an important operational level planning problem in maritime logistics. In this paper, we show how we designed and developed a mathematical model for real-world tanker scheduling problem in Japan. Tanker operators own their fleet of tankers and make their schedules for the next several weeks for meeting customers' demands. However, due to the high uncertainty of the ship operations and unexpected changes of demands, the schedules has to be revised frequently. Our methodology allows the operators to determine schedules that minimize the operational cost in a few minutes. These solutions provides cost improvements for tanker operators, as measured by reduction of 5-16 percents in total traveling distance.
- K. Kobayashi, S. Kim and M. Kojima, "Sparse Second Order Cone Programming Formulations for Convex Optimization Problems", Journal of the Operations Research Society of Japan., Vol.
51 (3), 241-264, 2008
- Second order cone program (SOCP) formulations of convex optimization problems are studied. We show that various SOCP formulations can be obtained depending on how auxiliary variables are introduced. An efficient SOCP formulation that increases the computational efficiency is presented by investigating the relationship between the sparsity of an SOCP formulation and the sparsity of the Schur complement matrix. Numerical results of selected test problems using SeDuMi and LANCELOT are included to demonstrate the performance of the SOCP formulation.
- K. Kobayashi, S. Kim and M. Kojima, "Correlative Sparsity in Primal-Dual Interior-Point Methods for LP, SDP and SOCP", September 2006, Applied Mathematics and Optimization, Vol. 58,
69-88, 2008
- Exploiting sparsity has been a key issue in solving large-scale optimization problems. The most time-consuming part of primal-dual interior-point methods for linear programs, second-order cone programs, and semidefinite programs is solving the Schur complement equation at each iteration, usually by the Cholesky factorization. The computational efficiency is greatly affected by the sparsity of the coefficient matrix of the equation which is determined by the sparsity of an optimization problem (linear program, semidefinite program or second-order cone program). We show if an optimization problem is correlatively sparse, then the coefficient matrix of the Schur complement equation inherits the sparsity, and a sparse Cholesky factorization applied to the matrix results in no fill-in.
- K.Kobayashi, K. Nakata and M. Kojima, "A Conversion of an SDP Having Free Variables into the Standard Form SDP", June 2005, Revised April 2006, Computational Optimization and
Applications, Vol. 36, 289-307, 2007
- This paper deals with a semidefinite program (SDP) having free variables, which often appears in practice. To apply the primal---dual interior-point method, we usually need to convert our SDP into the standard form having no free variables. One simple way of conversion is to represent each free variable as a difference of two nonnegative variables. But this conversion not only expands the size of the SDP to be solved but also yields some numerical difficulties which are caused by the non-existence of a primal---dual pair of interior-feasible solutions in the resulting standard form SDP and its dual. This paper proposes a new conversion method that eliminates all free variables. The resulting standard form SDP is smaller in its size, and it can be more stably solved in general because the SDP and its dual have interior-feasible solutions whenever the original primal---dual pair of SDPs have interior-feasible solutions. Effectiveness of the new conversion method applied to SDPs having free variables is reported in comparison to some other existing methods.
- K. Kobayashi, H. Morohosi, T. Oyama, "Applying Path-Counting Methods for Measuring the Robustness of the Network-Structured System", Aug. 2005, International Transactions in Operational
Research, Vol. 16 (3), 371-389, 2009
- We consider the path-counting problem that asks how many paths exist between any two different nodes in a network after deleting an arbitrary number of edges or nodes from the original network. Using path-counting methods, we propose a quantitative method for measuring the robustness of the network-structured system. First we define the connectivity function and attempt to obtain the expected connectivity function for the network. Applying the Monte Carlo method, we estimate expected edge deletion and node deletion connectivity functions when an arbitrary number of edges or nodes are deleted from the original network. We attempt to approximate the expected edge deletion connectivity function using an appropriate nonlinear function with two parameters. We also show the numerical results of applying the path-counting method with their analysis in order to quantitatively evaluate the connectivity for some special types of networks.
(conference proceedings)
- K. Kobayashi and M. Kubo, "A Linear Approximation of the Value Function of an Approximate Dynamic Programming Approach for the Ship Routing Problem", to appear in Post-conference proceedings
of LION4, Lecture Notes in Computer Science, Springer, 2010.
- An approximate dynamic programming approach for the ship routing problem is studied. The decision problem at each period is ob- tained by adding the value function in the set partitioning problem pro- posed. The decision problem is a modification of the set partitioning problem so that it can be solved by the route generation approach. Numerical results for evaluating this approach is also given.
- T. Seta, K. Kobayashi and M. Kubo, "Ship Scheduling in the Steel Industry - a Rolling Horizon and Approximate Dynamic Programming Approach -", Proceedings of the International Symposium on
Scheduling 2009.
- A rolling-horizon and approximate dynamic programming approach for ship scheduling in the steel industry is studied. The planning problem to determine the ship schedules is formulated as a set covering problem. In this set covering formulation, we assume that the data are static. However, in ship operations, there is much uncertainty. In order to deal with uncertainty, we use a rolling-horizon and approximate dynamic programming approach.
- K.Kobayashi, T. Kano, M. Kubo, "A Two-Phase Algorithm for Tramp Ship Routing Problems by a Column Generation Approach", Learning and Intelligent OptimizatioN (LION3), Jan 14-18, 2009, Trento,
Italy. Online Proceedings
Poster
- A column generation approach for tramper ship routing problems is studied. We show that an efficient algorithm can be obtained by decomposing the problem into two simple problems. The master problem of the column generation is a set partitioning problem and the subproblem is the time-dependent shortest path problems with time windows. Numerical results of problems using general-purpose integerprogramming solver and the dynamic programming algorithm are included to demonstrate the performance of the proposed method.
- K.Kobayashi, "Computational Results on Some Shortest Path Problems with Side Constraints", SICE Annual Conference 2008, Aug. 2008, Tokyo, Japan.
- We consider a shortest path problem with side constraints; time windows constraints and precedence constraints. This problem arises as a subproblem in the column generation method for solving a container-ship scheduling problem. We implemented the generalized permanent label correcting algorithm by Desrochers and Soumis. We ran the numerical experiments to evaluate the actual efficiency of this algorithm.
(submitted)
- M. Yamashita, K.Fujisawa, K.Nakata, M.Nakata, M.Fukuda, K. Kobayashi and K. Goto, "A high-performance software package for semidefinite programs: SDPA 7", 2010, Optimization-Online
Articles and others
- M. Kubo and K. Kobayashi, "A Unified Framework of the Hierarchical Building Block and Column Generation Methods and Its Application to Transporation and Ship Scheduling" ( in Japanese), Journal of the Society of Instrument and Control Engineers, Vol.47 (6), 519-524. .
- K. Nakata, K.Fujisawa, M.Fukuda, M.Yamashita, M.Nakata, K.Kobayashi, "Optimization Software SDPA" (in Japanese), Bulletin of the Japan Society for Industrial and Applied Mathematics, Vol. 18(1), 2-14, 2008.
Doctor Thesis
- "Sparsity Exploitation in Primal-Dual Interior-Point Methods for Conic Linear Optimizaion Problems", Tokyo Institute of Technology, 2009. PDF
Research Reports
- K. Fujisawa, M. Fukuda, K. Kobaashi, M. Kojima, K. Nakata, M. Nakata and M. Yamashita, "SDPA (SemiDefinite Programming Algorithm) User's Manual - Version 7.0.5", B-448, Dep. of Mathematical and Computing Sciences, Tokyo Institute of Technology, Technical Report, February 2008. -> PDF
- M. Kubo and K. Kobayashi, "On Physical Distribution and Mathematical Programming" (in Japanese), Papers of National Maritime Research Institute, Vol.7(4), 83-86.
- K. Kobayashi, "Ship Routing and Scheduling Algorithm" (in Japanese), Papers of National Maritime Research Institute, Vol.7(4), 73-76.
Presentation
- K. Kobayashi, M.Kubo, T. Kano, "A Two-Phase Approach for a Tramper Ship Scheduling Problem", SIAM Conference on Optimization (OP08), May 2008, Boston, U.S.A, Slides PDF
- K. Kobayashi, M.Kubo, T. Kano, "Ship Routing Problem for a Fleet of Chemical Tankers in Japan", Conference of the Japan Society of Naval Architects and Ocean Engineers, November 2007, Slides. PDF in Japanese
- K. Kobayashi, "Correlative Sparsity in Primal-Dual Interior-Point Methods and Efficient SOCP Formulations", Second International Conference on Optimization (ICCOPT II - MOPTA07), August 2007, Ontario, Canada.
Kazuhiro KOBAYASHI
Center for Logistics Research,
Nagivation & Logistics Engineering Department,
National Maritime Research Institute
6-38-1 Shikawa, Mitaka-shi, Tokyo, Japan, 181-0004
National Maritime Research Institute Front Page
