Mathematical programming and industrial applications

(K. Nieminen, S. Ruuth, I. Maros.)

This research group is specialized in mathematical optimization methods, models and software. The research and development work is done in cooperation with other leading international universities and research institutes. Our main target is to transfer the latest technology to the Finnish industry in joint projects.

Mathematical programming algorithms, software and applications

We are developing methods for solving linear (LP) and mixed integer programming (MIP) problems, with emphasis on software implementations and applications in industrial systems and the public sector. We are studying and applying modern computer science techniques, such as object-orientation, parallellism, and distributed computation for designing and implementing efficient computer codes. We have been developing the latest branch and cut algorithms and also metaheuristics based search methods, such as genetic algorithms for solving extremely large combinatorial problems efficiently T[MÄN96] T[NIE02]. We have also implemented several discrete event simulation packages and applied them for production planning, scheduling and elevator systemsT[KÄM99].

MILP (Mixed Integer Linear Programming) is a research project supported by The National Technology Agency (Tekes).The ong-range goal of the project is to develop efficient optimization methods for linear process models including integer variables and to implement prototype versions of the algorithms in object oriented environment. The work happens in collaboration with Imperial College and it supports the long tradition of Åbo Akademi for solving MINLP (Mixed Integer Non-Linear Programming) problems using cutting plane algorithms.

A key to the success of Branch and Bound (B&B) algoriths for integer programming is early identification of a first ineger solution. While there are several methods to achieve this goal, in this project we developed a customized algorithm (GA) for this purpose.

The traditional method used for finding the first feasible integer solution is the depth first search algorithm. In the study a genetic algorithm (GA) has been developed. The new method turned out to be significantly more efficient than the depth first method. For the most test problems using GA a good solution was found in 30 - 50% shorter time compared to the depth first algorithm. In the literature no corresponding approach could be found T[NIE02] R[NIE03].

We have developed a new genetic algorithm for the capacitated vehicle routing problem (CVRP) in which a fixed fleet of delivery vehicles of identical capacity, a common depot and several geographically scattered customer demands are given and the problem is to find the set of routes with overall minimum route cost which service all the demands.

The objective of P-Net project was to develop scheduling and production planning methods for Finnish industry. Such tasks lead to hard combinatorial optimization problems. Since MIP methods are inadequate for large problems, we applied genetic algorithms, priority rules, simulations and heuristics. The associates were Okmetic Oy, Nokia Telecommunication Oy, Tieto Corporation, ABB Industry and Sisu-Akselit Oy. T[EK99], T[KÖS00].

Production scheduling relies often on priority based sequencing to determine which job a machine should process when the machine becomes available. These dispatching algorithms lack optimality because they make current decisions without considering future events and what is happening at other machines. This can cause long lead times and high inventories in highly utilised factories. However, large scale real world production scheduling can not generally be solved optimally in a reasonable computing time. Therefore, metaheuristics based search methods, such as genetic algorithms, have been used to give solutions. Genetic algorithm imitates natural evolution mechanism. Each iteration step gives a set of solutions, which is modified by selection, crossover and mutation.

In a generalised resource constrained scheduling problem the objective is to schedule the operations subject to ready times, due dates, precedence relations and resource constraints in order to optimise the objective function. We have implemented a scheduling procedure, which has two levels: A genetic algorithm is used for determining the priorities of the operations and the schedule is calculated based on the priorities P[KÄM99].

Our algorithm will be applied to the production scheduling problem of a Finnish silicon wafer manufacturer Okmetic Oy. We are developing a scheduling system, which will be integrated with the production control system of the company. The scheduling algorithm deals with a deterministic scheduling problem, but the production environment is dynamic with external and internal disturbances. A simulation environment, which can be used to analyse what happens when the deterministic scheduling problem changes, is considered T[KÄM99].

Our software package (LP2) has been used in production planning, transportation, project scheduling problems P[HYN90], hydro power planning T[ARO91], reparceling of farm land in Finland, power line maintenance (KUHA), bridge management (SIHA), and industrial energy optimization. We have completed the TEHO-project (energy optimization of a steel factory), where we developed an energy management and optimization system for the Rautaruukki Steel Factory at Raahe P[LAH92], R[LAH93a, LAH93c].

Figure: Process chart of Rautaruukki Raahe Steelworks

Many large and complex problems exhibit a structure that allows designing specialized algorithms for solving the problems more efficiently than with standard algorithms. We have been implementing a number of such special algorithms as extensions of standard LP/MIP techniques.

The Danzig-Wolfe decomposition algorithm transforms a large linear programming problem into multiple smaller problems, which are solved in turn. Our implementation of a modified Danzig- Wolfe algorithm is being used in the Finnish forest industry for optimizing large scale, long term energy management. We have developed and implemented a parametric decomposition algorithm for mixed integer programming, which allows modelling and solving corporate- wide models locally at production plants with only minimal centralized coordination. The system is in use in a major Finnish pulp and paper corporation. P[LAH89], R[RUT90].

We have developed and implemented a heuristic MIP algorithm for solving large scale unit commitment problems for long term production planning. This implementation is also being used in the forest industry. P[LAH89]. A national long- term energy management model and optimization algorithm has been developed in cooperation with Tampere University of Technology. The optimization algorithm is based on combining LP/MIP techniques with dynamic programming P[LAU92]. We are cooperating with the Technical Research Centre of Finland in developing new algorithms and implementations for solving large unit commitment problems for long term energy production. This software is currently in operative use at several municipal power plants.

LPR is a linear and mixed programming package using rational number arithmetics. The package is intended for educational use P[LAH91c]. LPR provides the primal and dual algorithms with bounded variables, parametric analysis and a branch and bound algorithm for mixed integer programming. The pivoting is carried out in tabular form. It is possible to execute the algorithms step by step manually. The models are defined using a subset of the object-oriented modelling language of MME.

SIM2 is an object-oriented simulation tool for discrete event systems. The prominent feature of SIM2 is its support for parallellism through procedures written in a conventional programming language. The Simula-like process-oriented paradigm is supported through queues and pseudo-concurrent processes, statistic and random number utilities, interactive graphics and animation P[LAH91d]. SIM2 was originally implemented in an object-oriented version of Pascal (Borland) in the PC/DOS environment. An implementation in C++ is also available.

DISIM is an experimental simulation environment, which allows simulators to be built graphically from predefined components such as clients, servers, queues, generators, channels, and statistical displays. We use SIM2 and DISIM regularly in a course on discrete simulation, where the students implement small to medium sized simulators for different application areas such as computer architectures, production networks, and business. Some real-life simulators for industry have also been constructed using SIM2 such as the simulator for the plate rolling mill of Rautaruukki Raahe Steelworks T[PAL93], and a traffic simulator.

Previous research:

Currently we do not have active research going on in these areas.

(F-G. Adler, A. Antikainen, V. Ek, S. El-Mahgary, H. Falck, H. Haanpää, H. Hakonen, J. Hokkanen, T. Iivanainen, J. Ikäheimo, A. Korhonen, O. Kämäräinen, J. Kössi, R. Lahdelma,, J. Liede, S. Makkonen, S.T. Makkonen, J. Mäntysaari, S. Ukkonen A. Vasama)

Building Trafic Simulator

( H. Hakonen, M. Siikonen )

BTS (Building Traffic Simulator) by KONE CO is an application for simulating passenger flow inside bulding. It is suitble for computing performance of elevator and escalator systems, e.g. passenger waiting times or travel times. The simulator is used for designing elevator systems for high rise buildings. The other uses are to test elevator group control algorithms and to display 2D and 3D animations about building traffic for demonstration purposes. We have been developing elevator and passenger simulation, statistics computations and optimization models of elevator group control in cooperation with KONE T[SII97].

Adaptive Metallurgical Raw Material Optimization

( J. Ikäheimo, J. Ranta, J. Turunen )

We developed charge optimization techniques in AMRO (Adaptive Metallurgical Raw Material Optimization) project. The AMRO method is particularly suitable for melting shops using scrap grades with varying prices and compositions, where accurate chemical an\ alyses for the lots are difficult to obtain. More sophisticated techniques to manage uncertainties associated with raw material\ s make it possible to use cheaper raw materials for producing high-quality products. The AMRO system is based on a stochastic o\ ptimization model and an adaptive parameter estimation and learning mechanism. During 1997/98, a new charge calculation system was developed for the Kuusakoski scrap aluminum melting plant in Heinola, Finla\ nd, T[RAN99]. A similar system was developed for the Outokumpu Po\ larit stainless steel melting shop in Tornio during 1998/99,T[IKÄ99]. We are also studied copper making process in order to model diffusion of impurities in shaft furnace, which helps to predi\ ct the element composition of the product, T[TUR00].

Multicriteria Decision Support in Environmental Problems

(R. Lahdelma, S. El-Mahgary, H. Hakonen, J. Hokkanen, K. Miettinen, P. Salminen )

We developed multicriteria group decision support methods and software for real-life environmental problems in cooperation with the University of Jyväskylä and Paavo Ristola Consulting Engineers Ltd. We have worked with several real-life applications of environmental decision making, such as choosing waste management systems for various sites in Finland. Our team has assisted in the decision-making of processes that today account for more than 80% of Finnish waste R[HOK96]. Another completed project was to support the decision making for developing a new general cargo harbour in Helsinki. By April 1996 the authorities had concurred that the project fulfills the requirements of the law on Environmental Impact Assessments (EIA) in Finland. The City Council of Helsinki has made a preliminary decision about building the harbour in Vuosaari. R[HOK96], P[LAH96c], M[HOK].

During the Helsinki Harbour project we developed the Stochastic Multiobjective Acceptability Analysis (SMAA) as an extension of the EIA procedure. SMAA is a technique for analyzing the preferences (weights) by which each alternative becomes acceptable. We are developing this methodology further to incorporate group preference information. P[LAH96a], M[LAHb]

Figure: Weight space analysis in SMAA: The set of weights that make alternative i the preferred one is an n-1-dimensional polytope Wi. The central weights wci represents the weights of a typical DM preferring that alternative.

Dynamic Scenario Optimization (DYSCO)

( A. Korhonen, A. Vasama, J. Liede )

DYSCO is a technique for combining scenarios with dynamic multiperiod mathematical optimization modeling. The idea is to include multiple alternative scenarios into a multiperiod optimization model simultaneously. Dynamic constraints connect subsequent periods together in a way to force the current decisions to lead into a feasible solution in each alternative future. This means that the model seeks for a joint strategy for all different scenarios included to the model, satisfying all legislative, institutional, managerial etc. constraints. Usability of the scenario method in the strategic planning of a business unit was studied T[VAS99].

In a project with the Bank of Finland we developed a dynamic, scenario based optimization optimization model and software environment for strategic financial planning for banks. A novel combination of scenarios with mathematical optimization modelling makes it possible to consider simultaneously the different possible futures and to find such current decision that the bank will survive or make the best of each of the included scenarios. We have used the object-oriented mathematical modelling paradigm for implementing the dynamic scenario model T[IIV96].

Data envelopment analysis (DEA)

( S. El-Mahgary, R. Lahdelma )

Data envelopment analysis (DEA) is a new linear programming method for calculating the relative efficiency of mostly non-profit organizations that possess some common functional traits but may rate very differently on their efficiencies due to internal differences such as management style. P[ELM95a] We have been conducting several DEA case studies. With Rautaruukki Steel Corporation we hve performed a competitor analysis of the leading steel factories of the world. We are currently making a comparative analysis of the educational and scientific contribution between the laboratories of Helsinki University of Technology. We are also conducting a nation-wide analysis of Finnish universities.

Figure: Efficiency rating of the Finnish Universities

Figure demonstrates the relative efficiencies of the 20 Finnish universities based on 1992's data from the national KOTA-database. The input factors of this model are the total expenditure and the median study time for undergraduate students. The output factors are the number of basic degrees awarded, the number of post-graduate degrees, and the completion ratio, an estimate of the percentage of undergraduate students who complete their studies. This model is only one of several possible models and, for example, neither environmental factors nor any research activities have been incorporated.

We have been developing the AskDEA software package, with emphasis on the interaction between the decision maker and integrated visualization tools P[ELM95b]. The DEA-technique requires a large number of medium-sized linear programming problems to be solved. In particular, when DEA-analysis is performed interactively, the problems have to be solved rapidly while the decision maker is waiting. We have developed a computationally efficient algorithm for solving large DEA models.

Network programming

( P. Takkunen, J. Eskelinen )

We have also constructed an interactive, Windows-based network programming system (NP2) for solving large scale transshipment problems efficiently, developed and implemented a specialized algorithm for solving chemical equilibriums T[ESK95], and developed a model and algorithm for integrating options with currency portfolio optimization T[TAK91]. In a research project we have studied several algorithms for a real time missile co-operation problem which leads to a non-linear network problem. One of these techniques has turned out to be fast enough for real time applications. The algorithm has been implemented in an object oriented enviroment. We have also built prototypes of optimization models for the coking plant of Rautaruukki, the Koskenkorva Liquor factory of ALKO, and the Pilkington glass factory at Lahti (Lahden Lasitehdas).

Energy Modelling and Optimization

( H. Hakonen, R. Lahdelma )

We have developed EHTO - a graphical, object-oriented optimization system in cooperation with the University of Jyväskylä and Process Vision Ltd. The system includes cogeneration planning, hydro power optimization, tariff optimization and unit commitment. The algorithms are embedded in an interactive graphical user interface, which allows defining and configuring a complete energy system including production units, purchase and sales agreements, and energy balances. A mathematical modelling and optimization system based on decomposition techniques is embedded to the system, allowing immediate interactive planning, simulation and optimization. The system is in use in several energy companies. P[LAH96b], T[HAK96]

Figure: Sample EHTO application

Object Oriented Modelling Environment

The Mathematical Modelling Environment (MME) is an experimental environment for supporting mathematical modelling and algorithm development. MME provides a formal modelling and algorithm specification language, automatic support for manipulating expressions symbolically and numerically, and built-in optimization software T[LAH91], P[RUT91]. MME has been applied in an industrial energy management project in cooperation with Rautaruukki Oy P[LAH91b], R[LAH93a].

The object-oriented paradigm has been successfully used in many programming, specification, analysis, and knowledge representation tasks. We have introduced a new modelling paradigm, object-oriented mathematical modelling, where mathematical programming models and submodels are embedded inside objects and classes, which can easily be assembled into larger systems. Object-oriented mathematical modelling is particularly suitable for implementing large and complex structured models to be used and maintained for a long time. This new modelling paradigm is related to constraint logic programming (CLP). T[LAH94].