Skip to main content

Über dieses Buch

This book constitutes revised and selected papers from the 18th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2019, held in Ekaterinburg, Russia, in July 2019.
The 40 full papers and 4 short papers presented in this volume were carefully reviewed and selected from a total of 170 submissions. The papers in the volume are organised according to the following topical headings: ​combinatorial optimization; game theory and mathematical economics; data mining and computational geometry; integer programming; mathematical programming; operations research; optimal control and applications.



Invited Paper


Committees: History and Applications in Machine Learning

The article outlines a brief history and applications of the committee theory. The use of committees in the problems of recognition and optimization is discussed. The application of the committee structures, ambiguous interpretation of non-formalized and contradictory data are given. The ways of rational regard on environmental factors in the context of a lack of resources are considered. The question of the numerical finding of committee structures is discussed, and these results are directly related to the theory of voting. The class of non-classical logics also contains MK-logic (Mazurov, Khachay). This section of non-classical logic includes the works by N. A. Vasiliev, L. Wittgenstein, J. Lukashevich, and Latin American mathematicians having a wrong term in their titles parainconsistent logic. One of the important results achieved by M. Yu. Khachay: For arbitrary positive integers q and k, $$k<q,$$ the minimum estimate of the subsystem power is given that is resolvable by a committee of k-elements for the inconsistent system having a committee of q-elements. Further the history of this field will be mentioned.

Vladimir D. Mazurov, Ekaterina Yu. Polyakova

Combinatorial Optimization


An Evolutionary Based Approach for the Traffic Lights Optimization Problem

We consider the traffic lights optimization problem which arises in city management due to continuously growing traffic. Given a road network and predictions (or statistical data) about the traffic flows through the arcs of this network the problem is to define the offsets and phase length for each traffic light in order to improve the overall quality of the service. The latter can be defined through a number of criteria, such as average speed, average trip duration, total waiting time etc. For this problem, we present an evolutionary based heuristic approach. We use a simulation model on the basis of the SUMO modeling system to evaluate the quality of obtained solutions. The results of numerical experiments on real data confirm the efficiency of the proposed approach.

Ivan Davydov, Daniil Tolstykh

On Given Diameter MST Problem on Random Input Data

We give an approximation deterministic algorithm for solving the Random MST with given diameter of directed graph. The problem is NP-hard. Algorithm has a quadratic time complexity. A probabilistic analysis was performed under conditions that edge weights of given graph are identically independent uniformly distributed random variables on an interval with positive ends. Sufficient conditions of asymptotic optimality are presented.

Edward Kh. Gimadi, Ekaterina Yu. Shin

Variable Neighborhood Search for the Resource Constrained Project Scheduling Problem

We consider the resource-constrained project scheduling problem (RCPSP) with respect to the makespan minimization criterion. The problem accounts for technological constraints of activities precedence together with resource constraints. Activities preemptions are not allowed. The problem with renewable resources is NP-hard in the strong sense. We propose a variable neighborhood search algorithm with two neighborhoods. Numerical experiments based on standard RCPSP test dataset j120 from the PCPLIB library demonstrated that the proposed algorithm produces better results than existing algorithms in the literature for large-sized instances. For some instances from the dataset j120 the best known heuristic solutions were improved.

Evgenii N. Goncharov

The VNS Approach for a Consistent Capacitated Vehicle Routing Problem Under the Shift Length Constraints

We consider a new real-world application of vehicle routing planning in a finite time horizon. A company has a set of capacitated vehicles in some depots and must serve a set of clients. There is a frequency for each client stating how often this client must be visited. Time intervals between two consecutive visits must be the same but the visiting schedule is flexible. To get some competitive advantage, the company tries to increase its service quality. To this end, each client should be visited by one driver only. The goal is to minimize the total length of vehicles’ paths over the planning horizon under the frequency constraints and driver shift length constraints. We present an integer linear programming model for this new consistent capacitated vehicle routing problem. To find near-optimal solutions, we design the Variable Neighborhood Search metaheuristic with eleven neighborhood structures. The driver shift length and capacity constraints are penalized and included into the objective function. Empirical results for real test instances from Orenburg region in Russia with up to 900 clients and four weeks in the planning horizon are discussed.

Igor Kulachenko, Polina Kononova

Development of Ant Colony Optimization Algorithm for Competitive p-Median Facility Location Problem with Elastic Demand

In this paper, we consider the competitive p-median facility location and design problem with elastic demand that we have earlier formulated based on the problem with elastic demand and the classical p-median problem. The situation that arises in a new company planning to enter the existing market of goods and services is considered. The firm wants to locate its businesses in p points, capturing as much of the profits from competitors as possible. The problem has a mathematical model with a non-linear objective function. Searching the optimal solution to the constructed problem is difficult. The CPU-time of commercial software is significant even for not too large dimension. For the new model, we have previously proposed variants of local search algorithms, and created a series of test instances based on real data. In this paper, an ant colony algorithm is developed, and an artificial ant algorithm is proposed. The algorithm’s parameters are adjusted taking into account the specifics of the problem. Experimental studies and comparison of the ant colony optimization algorithm with the simulated annealing are carried out.

Tatyana Levanova, Alexander Gnusarev

Bounds for Non-IRUP Instances of Cutting Stock Problem with Minimal Capacity

We consider the well-known cutting stock problem (CSP). An instance of CSP possesses IRUP (the integer round up property) if difference (the gap) between its optimal function value and optimal value of its continuous relaxation is less than 1. If the gap is 1 or greater, then an instance is non-IRUP. Constructing non-IRUP instances is very hard and a question about how large the gap can be is an open theoretical problem. Aim of our research is to find non-IRUP instances with minimal capacity. We have found a non-IRUP instance with integer sizes of items having capacity $$L=16$$ , while a previously known instance of such kind had capacity $$L = 18$$ . We prove that all instances with capacity $$L \le 10$$ have IRUP.

Artem V. Ripatti, Vadim M. Kartak

Merging Variables: One Technique of Search in Pseudo-Boolean Optimization

In the present paper we describe new heuristic technique, which can be applied to the optimization of pseudo-Boolean functions including Black-Box functions. This technique is based on a simple procedure which consists in transition from the optimization problem over Boolean hypercube to the optimization problem of auxiliary function in a specially constructed metric space. It is shown that there is a natural connection between the points of the original Boolean hypercube and points from new metric space. For a Boolean hypercube with fixed dimension it is possible to construct a number of such metric spaces. The proposed technique can be considered as a special case of Variable Neighborhood Search, which is focused on pseudo-Boolean optimization. Preliminary computational results show high efficiency of the proposed technique on some reasonably hard problems. Also it is shown that the described technique in combination with the well-known (1+1)-Evolutionary Algorithm allows to decrease the upper bound on the runtime of this algorithm for arbitrary pseudo-Boolean functions.

Alexander A. Semenov

Using Sat Solvers for Synchronization Issues in Partial Deterministic Automata

We approach the task of computing a carefully synchronizing word of minimum length for a given partial deterministic automaton, encoding the problem as an instance of SAT and invoking a SAT solver. Our experimental results demonstrate that this approach gives satisfactory results for automata with up to 100 states even if very modest computational resources are used.

Hanan Shabana, Mikhail V. Volkov

A Computational Comparison of Parallel and Distributed K-median Clustering Algorithms on Large-Scale Image Data

Most commonly used clustering algorithms are those aimed at solving the well-known k-median problem. Their main advantage is that they are simple to implement and use, and they are flexible in choosing dissimilarity measures (not necessarily metrics). K-median algorithms are also known to be more robust to noise and outliers in comparison with k-means algorithms. In spite of that, they have been of limited use for large-scale clustering problems due to their high computational and space complexity. This work aims at computational comparison of k-median clustering algorithms in a specific large-scale setting—clustering large image collections. We implement distributed versions of the most common k-median clustering algorithms and compare them with our parallel heuristic for solving large-scale k-median problem instances. We analyze clustering results with respect to external evaluation measures and run time.

Anton V. Ushakov, Igor Vasilyev

On the One–Dimensional Space Allocation Problem with Partial Order and Forbidden Zones

In this paper we consider a generalization of the One–Dimensional Space Allocation Problem (ODSAP). It is a well–known optimization problem. The classical formulation of the problem is as follows. It is required to place rectangular connected objects (linear segments) on a line with the minimal total cost of connections between them. The generalization of the problem is that there are fixed objects (forbidden zones) on the line and between the objects a partial order of their placement on the line is given. It is impossible to place the objects in the forbidden zones. The area in which the placement is allowed consists of disjoint segments (blocks). Centers of the placed objects are connected among themselves and with centers of the zones. The structure of connections between the objects is defined using a graph. A review of the formulations and methods for solving the classical ODSAP is given. We propose a polynomial–time algorithm for finding a local optimum for a fixed partition of the objects into the blocks when the graph of connections between the objects is a composition of rooted trees and parallel–serial graphs.

Gennady G. Zabudsky, Natalia S. Veremchuk

Game Theory and Mathematical Economics


The Interaction of Consumers and Load Serving Entity to Manage Electricity Consumption

This paper addresses the coordination of interaction between various types of consumers and a load serving entity to manage electricity consumption by using several models: the Nash equilibrium pricing, and the adverse selection model based on the contract theory. We propose a method to form rate options for load curve optimization for different types of consumers and a load serving entity for different market configurations. The utility functions describe the real situation sufficiently well and allow the implementation of a system of incentives for load curve optimization (load shifting from a peak time of the day). The rates providing a separating equilibrium are determined. We compare the effectiveness of different retail market models. We use the pricing scheme that implies the change in electricity prices depending on the electricity consumption by all users during every hour so that all users are financially motivated.

Natalia Aizenberg, Nikolai Voropai

Social Optimality in International Trade Under Monopolistic Competition

We study the homogeneous model of international trade under the monopolistic competition of producers. The utility function assumes additive separable. The transport costs are of “iceberg types”. It is known that, in the situation of market equilibrium, under linear production costs, the social welfare, as a function of transport costs, decreases near free trade while (counter-intuitively!) increases near total autarky. Instead, we study the situation of social optimality. We show that total welfare decreases. We restrict our study by the case of two countries, “big” and “small”. Moreover, we study two important “limited” situations: near free trade and near total autarky. We show that near free trade, the welfare in the small country decreases; as to the big country, we find examples when (1) the welfare decreases and (2) the welfare (counter-intuitively!) increases. Besides, in the autarky case, we describe the situations of decreasing/increasing of welfare in each country.

Igor Bykadorov

Hamilton-Jacobi-Bellman Equations for Non-cooperative Differential Games with Continuous Updating

This paper is devoted to a new class of differential games with continuous updating. It is assumed that at each time instant, players have or use information about the game defined on a closed time interval. However, as the time evolves, information about the game updates, namely, there is a continuous shift of time interval, which determines the information available to players. Information about the game is the information about motion equations and payoff functions of players. For this class of games, the direct application of classical approaches to the determination of optimality principles such as Nash equilibrium is not possible. The subject of the current paper is the construction of solution concept similar to Nash equilibrium for this class of differential games and corresponding optimality conditions, in particular, modernized Hamilton-Jacobi-Bellman equations.

Ovanes Petrosian, Anna Tur

Data Mining and Computational Geometry


On the Thinnest Covering of Fixed Size Containers with Non-euclidean Metric by Incongruent Circles

The paper is devoted to the circle covering problem with unequal circles. The number of circles is given. Also, we know a function, which determines a relation between the radii of two neighboring circles. The circle covering problem is usually studied in the case when the distance between points is Euclidean. We assume that the distance is determined by means of some special metric, which, generally speaking, is not Euclidean. The special numerical algorithm is suggested and implemented. It based on optical-geometric approach, which is developed by the authors in recent years and previously used only for circles of the equal radius. The results of a computational experiment are presented and discussed.

Alexander Kazakov, Anna Lempert, Quang Mung Le

The Problem K-Means and Given J-Centers: Polynomial Solvability in One Dimension

We consider a problem of partitioning a finite set of points in Euclidean space into clusters so as to minimize the sum over all clusters of the intracluster sums of the squared distances between clusters elements and their centers. The centers of one part of the clusters are given as an input, while the centers of the other part of the clusters are defined as centroids (geometrical centers). It is known that in the general case this problem is strongly NP-hard. We prove constructively that the one-dimensional case of this problem is solvable in polynomial time. This result is based, first, on the proved properties of the problem optimal solution and, second, on the justified dynamic programming scheme.

Alexander Kel’manov, Vladimir Khandeev

A Generalized Point-to-Point Approach for Orthogonal Transformations

The known Iterative Closest Point (ICP) algorithm utilizes point-to-point or point-to-plane approaches. The point-to-plane ICP algorithm uses points coordinates and normal vectors for aligning of 3D point clouds, whereas point-to-point approach uses point coordinates only. This paper proposes a new algorithm for orthogonal registration of point clouds based on a generalized point-to-point ICP algorithm for orthogonal transformations. The algorithm uses the known Horn’s algorithm and combines point coordinates and normal vectors.

Artyom Makovetskii, Sergei Voronin, Vitaly Kober, Aleksei Voronin

Integer Programming


An Integer Programming Approach to the Irregular Polyomino Tiling Problem

In this paper, new integer programming models of the problem of irregular polyomino tiling are introduced. We consider tiling of finite, square, NxN-sized structure with L-shaped trominoes without any restriction on their number. Each polyomino can be rotated 90 $$^{\circ }$$ , so there are four orientations of the L-tromino. Developed models are effective for small-size instances. For medium- and large-size instances we suggest dividing the initial structure into several equally sized parts and combine the solutions of optimized tilings. We tried to apply new models to the existing information-theoretic entropy-based approach. We conducted computational experiments using IBM ILOG CPLEX package. The problem of irregular polyomino tiling can be applied to the design of phased array antennas where polyomino-shaped subarrays are used to reduce the cost of the array antenna and to reduce the undesired sidelobes radiation. Computational results along with antenna simulation results are presented in the paper.

Vadim M. Kartak, Aigul Fabarisova

Iterative Methods for Constructing Approximations to Optimal Coverings of Nonconvex Polygons

The paper proposes algorithms for the iterative construction of optimal coverings of nonconvex flat figures using sets of circles. These algorithms are based on the procedures of dividing the figure into zones of influence of points that serve as the centers of the initial coverings and finding the Chebyshev centers of these zones. To generate the initial array of points, we use stochastic procedures based on the synthesis of optimal hexagonal grids and random vectors.

Pavel Lebedev, Vladimir Ushakov

Polyhedral Attack on the Graph Approximation Problem

In the clique partition problem (CPP), we need to find a spanning family of pairwise vertex-disjoint cliques of minimum total weight in a complete edge-weighted graph. In this paper, we consider the special case of the CPP, the so-called graph approximation problem (GAP), where the weights of edges are 1 or −1. It is one of the most computationally difficult cases of the CPP. We present our polyhedral approach to this problem based on the facet inequalities and the branch and cut framework. Computational experiments on the randomly generated instances indicate simple and hard classes of the GAP and maximal dimension for exact and an approximate solution with a given accuracy.

R. Yu. Simanchev, I. V. Urazova, Yu. A. Kochetov

Analysis of Integer Programming Model of Academic Load Distribution

The bicriteria problem of academic load distribution (ALD) and its integer linear programming (ILP) model are considered. Earlier it was shown that the search for a feasible solution to this problem is NP-hard and the cardinality of the complete set of alternatives is polynomial. For the ALD problem, the problem of finding a Pareto-optimal solution can be formulated as a weighted bin packing problem with color constraints and lower bounds on the load of the bins. In this problem, the number of bins is given and items have volume and color. For each bin, there is an upper bound on the number of different colors and this bound depends on the bin volume. For each item, coefficients of the efficiency of placing in any bin are set. In this paper, we study the ILP model for finding a Pareto-optimal solution. Parametric families of ALD instances are constructed and the L-coverings of these instances are studied. These instances have a small duality gap, in particular, it can be equal to one. We investigate the complexity of solving these families by the Land and Doig algorithm for some known branching rules. It is shown, that the iterations number grows exponentially with the number of bins.

Lidia Zaozerskaya

Mathematical Programming


Regularization and Matrix Correction of Improper Linear Programming Problems

The results of the study of improper linear programming problems are presented, in which the duality theory is essentially used and the approaches of I.I. Eremin (correction of incompatible constraints) and A.N. Tikhonov (creation of compatible systems of constraints equivalent in accuracy to given incompatible constraints). The problem of a stable solution to an approximate (and, possibly, improper) pair of mutually dual linear programming problems with a coefficient matrix of size $$m\times n$$ is reduced to a Mathematical Programming problem of dimension $$m + n + 2$$ . The necessary and sufficient conditions for the existence of a solution and constructive formulas for its calculation are obtained. Computational experiments were carried out on a model Linear Programming problem with an approximate matrix and vectors of the right-hand side and the objective function, demonstrating the convergence of the obtained solutions to the normal solutions to direct and dual problems with a decrease in the level of data error.

Vladimir Erokhin, Sergey Sotnikov, Andrey Kadochnikov, Alexey Vaganov

Discrete Time Lyapunov-Type Convergence Conditions for Recurrent Sequences in Optimization and Subgradient Method for Weakly Convex Functions

We present here the set of conditions for recursive optimization-like processes which guarantee their convergence to a given solution set. These conditions simplify convergence studies for such processes by essentially reducing them to the analysis of the processes behavior at arbitrary small vicinity of points outside the solution set. They also implicitly implement a rather complicated part of the logic of convergence proofs when there is no strict monotonicity of Lyapunov function along the process trajectory.

Evgeni Nurminski, Natalia Shamray

Methods for Matrix Games with Mixed Strategies and Quantile Payoff Function

Walsh–Vries approach to matrix games with mixed strategies is considered. According to this approach, the payment function is defined not as the mathematical expectation of a random gain in a long series of parties, but as its quantile (VaR-estimate) for a given level of risk. The properties of such games are studied, and the methods for their solution are suggested.

Leonid D. Popov

Simulation of Flow Regimes of Non-isothermal Liquid Films

For moderate Reynolds numbers, a nonlinear partial differential equation of the free surface state of a non-isothermal liquid film is presented. The algorithm was developed and the program was written in Matlab R2017b using the Symbolic Math Toolbox module. The wave characteristics of the liquid film under heat and mass transfer are calculated. The flow regimes of a vertical liquid film with a maximum perturbation growth rate are distinguished, and the effect of temperature gradients and surface viscosity on them is investigated.

Liudmila Prokudina, Dmitrii Bukharev

Counterexamples in the Theory of -Sets

The paper considers $$\alpha $$ -sets that are the generalization of convex sets. This concept was introduced by V.N. Ushakov in the 2000s to classify the reachable sets of controlled systems according to the degree of their nonconvexity. Since then a lot of properties of such sets have been discovered and proven. However, not all the “natural” properties are fulfilled. We have proved two “unnatural” properties for such sets in the paper. Firstly, we provide an example of a non-self-intersecting curve, a connected segment of which is “less convex” than the entire curve in terms of $$\alpha $$ -sets. Secondly, we show that there is an $$\alpha $$ -curve which is not representable as a graph of the function for all $$\alpha >0$$ .

Vladimir Ushakov, Aleksandr Ershov, Maksim Pershakov

Operations Research


Using Machine Learning Algorithm for Diagnosis of Stomach Disorders

Medicine is one of the rich sources of data, generating and storing massive data, begin from description of clinical symptoms and end by different types of biochemical data and images from devices. Manual search and detecting biomedical patterns is complicated task from massive data. Data mining can improve the process of detecting patterns. Stomach disorders are the most common disorders that affect over 60% of the human population. In this work, the classification performance of four non-linear supervised learning algorithms i.e. Logit, K-Nearest Neighbour, XGBoost and LightGBM for five types of stomach disorders are compared and discussed. The objectives of this research are to find trends of using or improvements of machine learning algorithms for detecting symptoms of stomach disorders, to research problems of using machine learning algorithms for detecting stomach disorders. Bayesian optimization is considered to find optimal hyperparameters in the algorithms, which is faster than the grid search method. Results of the research show algorithms that base on gradient boosting technique (XGBoost and LightGBM) gets better accuracy more 95% on the test dataset. For diagnostic and confirmation of diseases need to improve accuracy, in the article, we propose to use optimization methods for accuracy improvement with using machine learning algorithms.

Yedilkhan Amirgaliyev, Shahriar Shamiluulu, Timur Merembayev, Didar Yedilkhan

The Convergecast Scheduling Problem on a Regular Triangular Grid

The problem of conflict-free data aggregation in an arbitrary graph is NP-hard. On a square unit grid, in each node of which a sensor is located, the problem is polynomially solvable. For the case when the graph is a regular triangular grid, the upper bound on the length of the schedule of conflict-free data aggregation was previously known. In this paper, the refined estimates are given for the length of the schedule of conflict-free data aggregation on a triangular grid, as well as polynomially solvable cases are found and algorithms for constructing optimal and approximate schedules are proposed.

Adil Erzin, Roman Plotnikov

On an Applied Problem of Vector Optimization

The paper is devoted to the construction and investigation of mathematical models of economic processes in a local product market. The problem of optimization of prices at outlets of an autonomous network of wholesale under additional restrictions is in focus. The mathematical model of this problem belongs to the class of linear problems of vector optimization. The main properties of the multicriteria problem are studied. An optimal plan is defined. The necessary and sufficient conditions for optimality are established. The theorem of the existence and uniqueness of the optimal plan is formulated. A finite iterative procedure for the problem solution is developed on the base of the obtained theoretical results. The suggested numerical algorithm is based on specific variations of model parameters. The results are illustrated by examples of numerical solutions of some intuitive economic problems with using model data.

Igor Kandoba, Alexander Uspenskii

Net Present Value Maximization in Inventory Management System

The paper researches the model of profit maximization for a commercial company, taking into account the intensity of the sale of goods, the cost of purchase, the cost of delivery, the cost of storage and the cost of sale of goods. The alternative investments of available capital are also taken into account. It is shown that the profit function, depending on the period of delivery of goods, has a single maximum point. A model of the problem of the profit maximization in multi-product systems with limited working capital has been built and an algorithm for solving it has been developed.

Svetlana A. Malakh, Vladimir V. Servakh

Constructive Heuristics for Min-Power Bounded-Hops Symmetric Connectivity Problem

We consider a problem of constructing an energy-efficient bounded diameter communication spanning tree when the vertices are located on a plane, and the energy required to transmit a message between a pair of vertices is proportional to the squared distance between them. For this NP-hard problem, we have developed several approximate heuristic algorithms. The results of a posteriori analysis of solutions constructed by the proposed algorithms are presented.

Roman Plotnikov, Adil Erzin

Identification of the Optimal Set of Informative Features for the Problem of Separating of Mixed Production Batch of Semiconductor Devices for the Space Industry

In this paper, we investigate the problem of separation of a mixed production batch of semiconductor devices of space application into homogeneous production batches. The results of the mandatory testing for each item contain a large number of parameters. Many optimization models and algorithms were developed for solving this clustering problem in the most efficient way. However, due to a rather high data dimensionality, such algorithms take significant computational resources. We analyzed methods of reducing the dimensionality of the data set with the use of factor analysis based on Pearson matrix in order to improve the accuracy of the separation. We investigated efficiency of the proposed method for separating a mixed lot of semiconductor devices which consists of two, three, four and seven homogeneous batches, with various methods of selection and rotation of factors. It was shown on real data that with any orthogonal rotation, with an increasing number of homogeneous batches in the sample, the clustering accuracy decreases. Moreover, it was impossible to identify a universal clustering model with a limited number of factors for dividing a mixed lot composed from an arbitrary number of homogeneous batches. Thus, the use of the multidimensional data was shown to be inevitable.

G. Sh. Shkaberina, V. I. Orlov, E. M. Tovbis, L. A. Kazakovtsev

A Cost Minimizing at Laser Cutting of Sheet Parts on CNC Machines

The problem of cost minimizing at laser cutting of sheet parts on CNC machines is considered in this paper. As an objective function the cost function of cutting process is used. The model of exact cost function calculation is presented depending on the number of frames (commands) in the NC program. The each command is written using G-code. In order to most correctly construct optimal cutting path the accurate value of objective function basic parameters should be calculated. To this end, the accurate calculation methodologies of basic parameters values are presented. The methodologies relate to calculation of cost parameters and cutting speed. Based on proposed methodology the subsystem of cutting cost calculation was developed by using .Net Framework technology. In order to solve optimization problem the special cutting techniques are used. There are some multi-contour and multi-segment cutting techniques. In this paper special cutting techniques for common geometrical types of contours widely used in blank production are presented. In order to verify the proposed methodologies on practice the computational experiments which show a statistically significant improvement of the objective function value compared with using standard cutting techniques are presented.

Anastasia Tavaeva, Alexander Petunin, Stanislav Ukolov, Vladimir Krotov

A Local Branching MIP Heuristic for a Real-World Curriculum-Based Course Timetabling Problem

Automated timetabling is a challenging area in the timetabling and scheduling theory and practice, intensively addressed in research papers in the last two decades. There are three main classes of problems, which are usually studied: school timetabling, course timetabling and examination timetabling. In this report, we address a case study of the Curriculum-Based Course Timetabling (CB-CTT) problem, arising at Engineering Department of Sannio University. In general, the problem consists of finding a feasible weekly assignment of course lectures to rooms and time periods while respecting a wide range of constraints, which have to be either strictly satisfied (hard constraints) or satisfied as much as possible (soft constraints). The case study here addressed here has many special requirements due to local organizational rules. We were able to model the complex requirements by an Integer Programming formulation. The solution approach consists of using an MIP solver, integrated with two local branching heuristics tailored for the problem. The effectiveness of the proposed approach is illustrated by the computational results on two real instances.

Pasquale Avella, Maurizio Boccia, Sandro Viglione, Igor Vasilyev

Optimal Control and Applications


Iterative Method with Exact Fulfillment of Constraints in Optimal Control Problems

A new approach is proposed for constructing a relaxation sequence of admissible controls in the class of optimal control problems with constraints. The approach is based on the construction of a system of non-local conditions for improving the admissible control in the form of a fixed point problem of the control operator. To build the conditions for improving the admissible control, we apply the transition to an auxiliary optimization problem based on the well-known principle of extension. Sufficient conditions for the optimality of admissible control and the existence of a minimizing sequence of admissible controls in the considered class of problems with constraints are substantiated. A comparative analysis of the computational efficiency of the proposed iterative method of fixed points with the exact implementation of constraints in model and test optimal control problems is carried out.

Alexander Sergeevich Buldaev, Ivan Dmitrievich Burlakov

Optimization “In Windows” for Routing Problems with Constraints

We investigate the problem of sequentially visiting a number of megalopoleis while satisfying precedence constraints where the travel cost functions depend on the set of pending tasks. It is supposed that the dimension of the investigated problem is sufficiently large, therefore, an exact solution is practically impossible; in these circumstances, heuristics are used very widely. We investigate some possibilities for local improvement of results achievable in a class of heuristics. For such improvement of a result, optimizing insertions and finite systems of optimizing insertions are used. We view these systems as multi-insertions. The given approach is combined with the employment of a parallel algorithm implemented for a multiprocessor computing system. The optimizing insertions are designed by means of a broadly understood dynamic programming.

Alexander G. Chentsov, Alexey M. Grigoryev, Alexey A. Chentsov

The Stochastic Coverings Algorithm for Solving Applied Optimal Control Problems

The paper considers a heuristic method for a global extremum search in an optimal control problem based on the idea of covering a reachable set by n-dimensional balls, including the built-in mechanisms for Lipschitz constant estimating of the objective functional. A step-by-step description of the coverage algorithm and the proposed method for generating start and auxiliary controls are presented. The proposed technique was used for solving applied optimal control problems: the problem of investment programs in Buryatia Republic and the problem of restoring the Black Lands in Kalmykia.

Alexander Gornov, Tatiana Zarodnyuk, Anton Anikin, Pavel Sorokovikov

Deterministic Approximation of Stochastic Programming Problems with Probabilistic Constraints

The work is devoted to the development of a method for solving the stochastic programming problem with a deterministic objective function and individual probabilistic constraints. Each probabilistic constraint is a constraint on the probability of inequality for a certain loss function that is linear on random parameters. In this case, the loss function may be non-linear in strategies. It is proposed to replace each probabilistic constraint by an equivalent inequality for the quantile function. This inequality is approximated using the notion of the probability measure kernel. The kernel is defined as the intersection of all closed confidence half-spaces. It is known that if the kernel satisfies the regularity property and the loss function is linear in random parameters then the quantile function can be found as the maximum of the loss function in realizations of random parameters on the probability measure kernel. To evaluate quantiles an external polyhedral approximation [1] of the probability measure kernel is used. When replacing a kernel by its approximation the maximum mentioned above is an upper estimate of the exact value of the quantile function. As a result, each quantile constraint is replaced by several deterministic inequalities.

Yuri S. Kan, Sofia N. Vasil’eva

On Estimates of the Solutions of Inverse Problems of Optimal Control

This paper is devoted to the problem of reconstruction of the normal control generating a realized trajectory of a dynamic control system by using known inaccurate measurements of this trajectory. A class of dynamic control systems with dynamics linear in controls and non-linear in state coordinates is considered. A new method, suggested in earlier publications, for solving such problems is discussed. This approach relies on necessary optimality conditions in an auxiliary variational problem on extremum of an integral discrepancy functional. The distinguishing feature of the method is using a functional which is convex in control variables and concave in state variables discrepancy. This form of the functional allows to obtain oscillating solutions. In this paper the estimates of the error of the discussed method are exposed and validated.

Evgenii A. Krupennikov

Optimization Problem in an Integral Model of the Developing System Without Prehistory

This paper addresses an integral model of the developing system consisting of elements of n age groups. The model is described by means of the Volterra equation of the first kind with variable limits of integration. The case is considered when the moment of the system origin coincides with the beginning of the modeling, therefore there is no prehistory and for $$t = 0$$ all age groups of the elements are empty. Based on this model, we set the problem of optimizing the system age structure and the moment when the elements are decommissioned. In order to study a new integral model of developing systems as applied to the problem of forecasting the electric power system development, several model examples are considered. The results of numerical calculations are presented. They confirm the adequacy of the proposed model.

Evgeniia Markova, Inna Sidler

A Modified Duality Scheme for Solving a 3D Elastic Problem with a Crack

We consider an equilibrium problem for a 3D elastic body with a crack. Inequality-type boundary conditions are considered at the crack faces to prevent mutual penetration between them. This leads to the formulation of a problem with an unknown contact area, which admits a variational formulation in the form of a problem of minimization of energy functional in a set of feasible displacements. To solve the problem, we consider the Uzawa algorithm based on the modified Lagrange functional and compare it with the classical analog. Numerical results illustrating the efficiency of the proposed algorithm are presented.

Robert Namm, Georgiy Tsoy

Control of the Oscillations Through Nonlinear Interactions

The use of nonlinear effects in the control of stationary oscillations in nonlinear dynamic systems is considered. To find periodic solutions of corresponding ordinary differential equation systems, an interactive algorithm is used, based on minimizing the solution’s deviation from the periodic form. The possibility of the system behavior controlling due to the mutual nonlinear influence of various types of oscillations is considered. For nonlinear dynamical systems with one and more degrees of freedom, examples of various types of oscillations control are given.

Lev F. Petrov

Risk Management in Gaussian Stochastic Systems as an Optimization Problem

In article the risk management algorithm in Gaussian stochastic system is describes. The model risk management represents an optimization problem. The risk management algorithm is realized on the basis of the barrier functions method. The features of this nonlinear programming problem are not the convexity of the accessible solution region and the presence of stochastic restrictions on the required risk. The software implementation of the algorithm in the form of a separate module is performed. Using the Monte Carlo statistical test method, the algorithm was investigated. The algorithm showed stable control. Its efficiency is proved. Results of a research are presented in article. Recommendations on practical application of the algorithm are given.

Al’fiya A. Surina, Alexander N. Tyrsin

The Accuracy of Approximate Solutions for a Boundary Value Inverse Problem with Final Overdetermination

The paper aims to investigate the accuracy of the methods for approximate solving a boundary value inverse problem with final overdetermination for a parabolic equation. We use the technique of the continuation to the complex domain and the expansion of the unknown function into a Dirichlet series (exponential series) to formulate the inverse problem as a linear operator equation of the first kind in the appropriate linear normed spaces. This allows us to estimate the continuity module for the inverse problem through classical spectral technique and investigate the order-optimal approximate methods for the boundary value inverse problem under study.

Elena Tabarintseva

On the Issue of Comparison of Fuzzy Numbers

In the class of decision-making problems with fuzzy information concerning criterion values, the problem of comparing fuzzy numbers is relevant. There are various approaches to solving it. They are determined by the specific character of the problem under consideration. This paper proposes one approach to comparing fuzzy numbers. The proposed approach is as follows. At first, a rule is constructed for comparing a real number with a level set of a fuzzy number. Then, with the help of a procedure for constructing the exact lower approximation for the collection of sets, a fuzzy set is constructed. This fuzzy set determine the rule for comparing a real number with a fuzzy number. Using this rule and the approach based on separating two fuzzy numbers with a real number, the procedure is chosen for comparing two fuzzy numbers. As an example, fuzzy numbers with trapezoidal membership functions are considered, and the geometric interpretation of the results being given.

Viktor Ukhobotov, Irina Stabulit, Konstantin Kudryavtsev


Weitere Informationen

Premium Partner