Tutorials
Prof. Saïd Hanafi
University of Valenciennes, FranceAn overview of heuristics based on Mathematical programming for the 0–1 mixed integer programming problem
The 0 – 1 mixed integer programming problem is used for modeling many combinatorial problems, ranging from logical design to scheduling and routing as well as encompassing graph theory models for resource allocation and financial planning. This talk provides a survey of heuristics based on mathematical programming for solving 0 – 1 mixed integer programs (MIP). More precisely, we focus on the stand - alone heuristics for 0 – 1 MIP as well as those heuristics that use linear programming techniques or solve a series of linear programming models or reduced problems, deduced from the initial one, in order to produce a high quality solution of a considered problem. We review: heuristics that use pivot moves within the search for an optimal solution of the MIP in order to move from one extreme point to another; heuristics that use pseudo - cuts in order to cut-off portions of a solution space already examined in the previous solution process; the so-called pump heuristics which purpose is to create a first feasible solution of the considered MIP; and so-called proximity heuristics that seek a MIP feasible solution of a better quality in the proximity of the current incumbent solution. In addition, we provide a classification and summary of main components of MIP heuristics. In general, our emphasis is on how mathematical programming techniques can be used for approximate problem solving, rather than on comparing performances of heuristics.
Damir N. Gainanov
Ural Federal University/ Moscow Aviation InstituteGraph Theory and Combinatorial Optimization in the Applied Problems of the Freight Railway Transportations Management
The report will consider a number of optimization problems devoted to the freight railway transportations managment. The stage of the planning of the freight railway transportations involves the construction of the conflict-free sets of threads, as well as the same problem taking into account the current transportations plan. Within the framework of the proposed approach, these applied problems are reduced to the consideration of the classical combinatorial optimization problem on the largest independent set. The next stage of the organization of the freight railway transportations consists in the assignment of locomotives, which are given by conditions of their ability, for execution of the transportations plan, which is given by the conflict-free set of threads. To reduce the dimension of this problem, it is proposed the approach in the framework of which the investigation reduces to solving the problem on the decomposition of the directed graph on the set of strongly connected components. In this case, each strongly connected component generates the same problem, and whithin these components the problem on the assignment of locomotives is reduced to solving the problem on the cover of vertices of the graph by minimal number of directed paths.