ὅδε οἶκος, ὦ ἑταῖρε, μνημεῖον ἐστιν ζωῶν τῶν σοφῶν ἀνδρῶν, καὶ τῶν ἔργων αὐτῶν

Project 174010

Mathematical Models and Optimization Methods with Applications

Leader: Nenad Mladenović, Research Professor

Abstract

Subject, description and importance of research

The main goal of our research is consideration of real-word large scale systems that needs to be improved using mathematics and optimization methods. Such large scale systems appear in industry, telecommunication, transportation, medicine, electronics, education, chemistry, in public and private sector, etc. In the process of getting good solution, there are some steps, common for all kind of problems mentioned. Those steps are

      (i) modeling, or extracting from the reality important components and make symbolic or mathematical model of the problem;

 

      (ii) Find numerical solution method(s);

 

      (iii) Make computer implementation of the methods;

 

      (iv) iterate steps (i)-(iii) until decision maker is happy with the final solution.

 

Most of real word problems belong to the areas of combinatorial and global optimization. More precisely, they may include integer, Boolean 0-1, and/or continues variables. In addition, such problems might be linear or non-linear. Thus, the model may belong to mixed integer linear or nonlinear programming. However, most of them are NP-hard and this means that there is no exact solution method that could solve the problem in reasonable time. Since there are usually a huge number of unknown variables and constraints, in the forefront will be the development of heuristics based on some metaheuristics principle. They do not ensure finding an optimal solution, but approximate one, in reasonable computing time. Our attention will be mostly focused on Variable neighborhood search (VNS) and Genetic algorithms (GA) metaheuristic. In addition to designing heuristics based on VNS and GA for many classical combinatorial and global optimization problems, we will develop their methodological and theoretical properties. We also plan to work on exact solution methods simultaneously for the following two basic reasons:

      (i) we can find out how large problems can be solved exactly;

 

      (ii) how good are our heuristics for solving instances where optimal solutions are known.

 

Thus, it is natural that one of our research topic will be matheuristics (or model-based heuristics). They combine heuristics and exact methods in order to improve performances of both. More precisely, the content of the research could be as follows:

      01. The development of VNS and GA for solving discrete location problems.

 

      02. The design of VNS for solving various versions of the Travelling Salesman Problem (TSP):

 

        (a) Capacitated TSP with Pickup and Delivery,

 

        (b) TSP with FIFO rule,

 

        (c) TSP with Time Windows etc.

 

      03. VNS, Bee colony optimization and Tabu search based heuristics for Routing and wavelength assignment problem in optical and telecommunication networks. This problem will be considered with respect to various restrictions related to network: sets of wavelengths on links of the network are all the same or sets of wavelengths on links of the network are all different, the transmission wavelength can be changed while passing through a vertex of the network or the wavelength change is not allowed or the wavelength change is allowed, but only to predefined set of values, etc.

 

      04. Heuristic methods for solving global nonlinear optimization problems.

 

      05. VNS and GA for solving Generalized minimum vertex cover problem of a Graph.

 

      06. GA and VNS heuristics for solving Maximum insertion problem. The possibility of creating new model for this problem will considered as well.

 

      07. Metaheuristics for Activity scheduling problems (class schedule, exam schedule, school club schedule) with various kinds of constraints (time, space or other resources).

 

      08. GA for CNC machine-job assignment problem with controllable processing times.

 

      09. Problems related to semantic web.

 

      10. Modeling and solving Quality of service web problem.

 

      11. VNS for Clustering and data mining.

 

Our project group that will deal with optimization models in Mechanics will consider the following problems. The dynamic behavior of heterogeneous or multi-phase materials remains an active research topic in more than two decades. In spite of that, the stochastic nature of brittle dynamic material response remains difficult to model analytically not only due to complex interplay of the structural disorder and the dynamically induced nonlinear stress field but also the inherent limitations of the perpetually advancing experimental techniques at the high strain rates. The use of simplified discrete methods (such as lattices or particle dynamics) still has its merits to the extent they can capture "essential physics of phenomenon" that is only weakly dependent on the complexities of realistic systems.
The brittle continuum is approximated by a 2D microstructure offer an efficient approach to modeling of its stochasticity. The discrete system consists of "continuum particles" that interact through nonlinear bonds. The system is a Delaunay network dual to the Voronoi froth of the ceramic grain boundaries. The model is geometrically disordered by introduction of the normal distribution of stress-free inter-particular distances λ0within the range ⌈αλ≤λ0≤(2−α)λ⌉. The geometrical-order parameter α(0<α≤1), is the model property that is identifiable by visualization of micrographs. The average inter-particular distance, λ, defines the model resolution length. All finer-scale material flaws have to be taken into account by the failure strain and/or stiffness distributions of inter-particular bonds ⌊βκ≤κ≤(2−β)κ⌋, where β(0≤β≤1) is the structural-order parameter. The mean stiffness of inter-particular bonds comprising the discrete network is related to the modulus of elasticity of the pristine material, κ=8√3Ε0/15. The dynamic response of such disordered system to the dynamic loading is obtained by solving a system of differential equations of motion of the classical mechanics (by adaptation of molecular dynamics techniques). The system of 105 particles is solved routinely on the average PC, which makes statistical analysis efficient.