Project 144007

Mathematical Models and Optimization Methods with Applications

Leader: Nenad Mladenović

Abstract

This research is concerning mathematical modeling of the practical problems from the following fields of applied mathematics: Scheduling, Discrete and continuos location; Hub location; Optimization on networks and graphs; Data mining; Clustering; Bioinformatics; Geoinformation Sciences, etc. These models are specific and there is not a general model that is appropriate for all potential or existing applications. The studied models are often extremely difficult to solve, at least optimally. Therefore, the second important area of our research is directed to developing metaheuristic solution methods for solving NP-hard combinatorial and global optimization problems, their computer implementation and their testing on real word or benchmark data from the literature. Research would include the following modern meta-heuristic methods: Variable neighborhood search; Genetic and Evolutionary algorithms; Neural networks; Tabu search; etc. Significant part of this research will be hybridization of the mentioned meta-heuristics, combining with exact methods, parallelization and executing on a multi-processor systems. By using these approaches we will attempt to solve large-scale problem instances for which no solution is known up to now.

Subject, description and importance of research

The basic subject of our project is developing methods for solving NP-hard Combinatorial and Global Optimization problems that could be used in industry, in public sector, etc. The first topic would be a heuristic approach since exact methods are not able to solve the most of real word problems. For some combinatorial problems we would also develop exact methods in order to check the solution quality of our new heuristics. Moreover, we would try to solve exactly larger instances than previously treated in the literature. In more detail, the context of our research would include the following:

• Variable Neighborhood Search (VNS) and Genetic algorithms (GAs) for solving discrete location problems. Particular attention will be directed to hub location problems (uncapacitated/capacitated, multiple/single allocation, center/median cases). The Discrete ordered median problem will also be studied, since it represents a generalization of several well-known discrete location problems.
• Solving network design problems and the index selection problem using evolutionary computation approach and using Variable Neighborhood Search.
• Applying Variable Neighborhood Search for solving Graph Optimization problems: Augmenting Biconnectivity Problem, Steiner Tree Problem, etc.
• Variable neighborhood decomposition search for the edge/vertex unweighted/weighted k-cardinality tree problem.
• Developing metaheuristic algorithms for Task scheduling. • Reformulation descent method applied to circle packing problems.
• Design of balanced MBA student teams
• Applying Variable Neihborhood Search for Global Optimization.
• Constructing and implementing new genetic operators adopted to the problem under study in order to preserve the feasibility of the individuals. These genetic operators will be designed for solving wider class of similar problems.
• Using different encoding schemes in the GA for solving the same problem and investigating the effect of representation to GA performance and convergence • Developing new methods based on a hybrid of Genetic algorithm and some other heuristics or exact methods.
• Implementing caching technique in the pure GA and its extension to the hybrid GA in order to improve computational performance
• Parallel implementation of the GA and testing on a multi-processor computer.
• Applying GA in solving of differential equations.
• VNS for solving the Maximum clique problem/Maximum independent set.
• Heuristic and exact approaches for solving the J-Means, K-means, minimum sum-of-squares clustering problems.
• Pooling problem in oil industry.

The problems that belong to Multi-criteria or multi-attribute decision models we would treat in more details are:
1) New approaches in Data envelopment analysis;
2) Fuzzy multicriteria approach in ranking strategies in production/distribution system;
3) Optimal control in traffic and transportation;
4) Optimization in public sector (garbage collection, arc routing, post delivery, supply chain management);
5) Optimization of telecommunication and computer networks.

The other optimization problem we would pay attention are:
1) Location theory;
2) Oil pipeline design problem;
3) Bioinformatics, disordered proteins and function;
4) Data reduction for spatial-temporal knowledge discovery.

After the mathematical model of some real problem has been formed, the class including that model is recognized and the existing methods are analyzed or some new are proposed. The next phase is implementation these methods on computers, and then testing by using instances from literature or real problem data. As different problems might have the same mathematical models, it follows that problems are classified according to their mathematical characteristics (linear, nonlinear, convex, global, continual, discrete, combinatorial, etc). On the other side, the models could be classified by the field of applying (location, optimization of public sectors, saving in electrical power, hydroeconomy, traffic, transportation, military sciences, and so on). Finally the result of our research should be software directed to some combinatorial or global optimization. The results of this project could be offerring direct services to the domestic and foreign market and applying the developed softwares for solving many practical problems.

Research Goal

The research goal of our project includes:

• Developing models and methods (software) in order to improve the quality of decisions in industry, trafic and transportation, medicine, etc., i.e., to enable rational use of energy, money, time, manpower, food, etc. The same software can be adapted to different purposes and we can say that possible applying of our results is almost in all fields of human activities;
• Developing original methods that produce results of similar or better quality as those known to be the best in the literature;
• Obtaining new theorems regarding suggested methods;
• Including young researchers in the project to make conditions for a good scientific future of our country in this important field;
• Publishing obtained original results in high-quality international and domestic journals, proceedings and monographs. In this way we will confirm high international position of the group of researchers working in the field of mathematical optimization models and methods.