Project 1583

Mathematical optimization models and methods with applications

Leader: dr Nenad MladenoviŠ


Subject of research

Description of the work

The basic subject of our project are 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:

The problems that belong to Multi-criteria or multi-attribute decision models we would treat in more details are:

The other optimization problem we would pay attention are:

Originality of research

New heuristic methods for combinatorial and global optimization. New optimization models for industrial applications. New theorems regarding suggested methods.

Research Goal

To develope models and methods (software) in order to improve the quality of decisions in industry, trafic and transportation, medicine, etc., i.e., to anable racional use of energy, money, time, manpower, food, etc.

To develope original methods that produce results of similar quality as those known to be the best in the literature.

To include young researchers and to make conditions for a good scientific future of our country in this important field.

State of the Art in Scientific Field

World-wide Situation

The role of mathematical modelling in solving real word problems is increasing rapidly. The special role have optimization methods and more specifically, heuristic techniques. Almost all big companies in the word have research department with mathematicians and programmers that are trying to improve some segment of production, transportation, distribution, scheduling, etc. processes, by using optimization techniques. Importance of this field of Applied mathematics and Computer science can be seen in the number of high quality journals (more than 50). For example, SIAM (Society of Applied and Industrial Mathematics) is publishing 10 journals such as SIAM J. Optimization, SIAM J. Comput., SIAM J. Sci. Comput., SIAM J. App. Math. Let's mention here a few other best known journals: Operations Research, Mathematical Programming, Management Science, European J. Operations Research, INFORMS J. Computing, Computers and OR, Networks, Pattern Recognition, JORS, JOTA, J. of Heuristics.

The special attention in our research would be paid on near optimal solution methods (heuristics) since the most real-word problems are so-called NP-hard and could not be solved in reasonable time even on fastest computers by classical approaches. In order to solve them in reasonable time, in the last 10 years several so called metaheuristic methods have been proposed. As an example for increasing research interests in these field could be several specialized web sites as well as a few conferences.

Domestic Situation

Researchers in Yugoslavia are relatively well organized in this field. They are gathered around Yugoslav symposium of Operations research that takes place once a year (in last 30 years). Beside, several leading universities and institutes in Yugoslavia are included in publishing (in last 10 years) an international journal, i.e., Yugoslav journal of Operations research, despite of very well known financial and other dificulties in our country. There are also two professional sociaties: Yugoslav society of industrial and applied mathematics (YuSIAM), that tries to fill the gap between academic research and practical needs of Yugoslav society; Serbian society of Operations research (SSOR), with interesting publishing activities. However, the financial situation unable researchers and users larger implementation of the theoretical work in practice.

Planned Project Results

The planed results of project are very close to applications, which could be direct or indirect. Mathematical modeling process is arising from some real problem. After model forming, 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 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. Previous descriptions indicate the other fields where our results could be applied:

As the results of this project could be offer following direct services to the domestic and foreign market: (a) consulting or software for solving optimization problems by segments or in whole for some companies according to the contemporaneous methods applying on similar problems. Some of direct applying could be:

Especially the developed software could be directly applied for solving many practical problems related to: database systems, geophysics, immunology, polyphase radar codes, etc.