OPAL-RING
Masakazu MURAMATSU Laboratory

Applying a Mathematical Approach to the Study of the Optimization Problem: Selecting the Optimal Method

Our laboratory develops algorithms for optimization problems in the broad sense. How can a quantitative task be executed most efficiently? We approach problems like these as optimization problems in the broad sense of the term. Optimization problems arise in numerous fields ranging from machine control to finance.<br /> One example: A task recently studied at our laboratory involved scheduling vessel allocations for a marine transport company. Applying our optimization algorithm to this problem, we formulated a schedule that reduced costs by 5% compared to a schedule drawn up by a human specialist.

Optimization Problems and Personnel Assignment Planning

Optimization problems are often found hiding in the most unlikely places.<br /> Suppose a hospital administrator wants to prepare a work shift plan for the following month. He or she must determine which nurses to assign to certain shifts and monthly total work hours for every staff member in a way that none will find grossly unfair. This is exactly the type of problem handled by the optimization algorithm. The optimal staff assignment can be determined by treating the satisfaction of each staff member as an objective function, then creating a mathematical model that maximizes total satisfaction, with some expression of feasible staff assignments. Finding the corresponding mathematical solutions by an optimization algorithm, we can find an optimal staff assignment.

Nonlinear Programming, Convex Programming, and the Latest Research

Although our laboratory pursues research interests across a broad range of optimization problems, we do focus on special areas: namely, nonlinear programming (NLP) and convex programming.<br /> We base our algorithms for solving optimization problems on a class of algorithms known as interior point methods. (In passing, one example of the interior point method became the first algorithm anywhere in the world to be judged worthy of a patent.)

Our Specialty: Conic Programming

Among NLP optimization problems, our primary strength lies in the area of conic programming problems, which have attracted considerable attention since the 21st century. We pride ourselves in being among the leaders in the study of conic programming problems and derivative forms, including semidefinite programming, second-order cone programming, and symmetric cone programming.

Profound Expertise in the Latest Optimization Algorithms

Optimization technologies are normally implemented in four steps: (1) capturing a problem as an optimization problem; (2) modeling the problem as an optimization problem; (3) solving the optimization problem; and (4) solving the original problem using the optimal solution obtained.
Of these steps, the most important is step (1). An optimization problem lying hidden in plain sight can only be solved once it has been recognized. Only after the user recognizes the problem as an optimization problem can he or she proceed to step (2). At this second stage, the key task is to assess the feasibility of solving the problem.<br /> Some optimization problems are easily solved, while others defy solution. Modeling applies only in the case of solvable problems, since proceeding to step (3) would otherwise be meaningless. While step (1) may be the most important, step (2) generally presents the greatest obstacle.
At this stage, our laboratory and our extensive familiarity with and understanding of the various issues associated with optimization problems and experience with various algorithms can help. Once a business realizes that the problem on hand is an optimization problem, our laboratory offers powerful support at steps (2) and (3), the modeling and solution-finding stages. If the optimization problem is already modeled, we identify and propose the most efficient algorithm. (We call this the optimization proposal.) Here we want to stress that tremendous progress has been made in developing optimization technologies in recent years, with solutions identified for numerous problems previously regarded as insoluble. One of the key strengths of our laboratory is that our technologies reflect this progress.

Optimization: A Partnership of Theory and Application

We have little interest in deskbound contemplation of optimization technologies. We believe the real adventure and challenges begin when we apply the technologies to solve various problems in the real world. This is why our laboratory is active in both basic research and in finding solutions to actual problems.
Polynomial optimization is a current basic research topic. Simply put, the polynomial optimization problem is an optimization problem that can be defined by polynomials. It has recently been discovered that the optimal solution can be obtained through semidefinite programming.<br /> In joint efforts with other universities, we recently completed the development of software to solve polynomial optimization problems, and we are currently exploring potential applications.
Nothing gives us greater pleasure than encountering a new optimization problem. We encourage businesses to contact us to present new and challenging problems they wish to solve.