MOTOR 2022: MATHEMATICAL OPTIMIZATION THEORY AND OPERATIONS RESEARCH
PROGRAM FOR MONDAY, JULY 4TH
Days:
previous day
all days

View: session overviewtalk overview

10:00-12:00 Session 7: Plenary Session
10:00
Recent Advances in Sphere Packing Problem

ABSTRACT. We consider a general sphere packing problem which is to pack non-overlapping spheres with the maximum volume into a convex set. This problem has important applications in science and technology and belongs to a class of global optimization.

In two dimensional case, the sphere packing problem is a classical circle packing problem. It has beenshown that 200 years old Malfatti’s problem is a particular case of the circle packing problem.

We survey existing theories and algorithms on general sphere packing problems. We also discuss their applications in economics and a mining industry.

10:40
Matching market design: theory and applications

ABSTRACT. How do we match supply and demand when standard price mechanisms are not available? Examples include school choice, college admissions, organ allocation, social housing. In these cases, we use matching mechanisms that elicit the agents' preferences and then determine who gets what, so that the outcome is desirable by various standards. In this talk, I introduce the matching theory and present the results addressing the recent methodological difficulty: how to compare different matching mechanisms according to various desirable properties when the standard axiomatic approach is not applicable? I also present a practical case in point: the Russian college admissions system.

11:20
Three efficient methods of finding near-optimal solution for NP-hard discrete optimization problems

ABSTRACT. Three fairly universal and efficient methods of finding near-optimal solutions for NP-hard problems will be discussed in our talk and illustrated by examples of their application to scheduling problems (although, they are surely applicable to a much wider area of Discrete Optimization problems):

1. Methods of“compact” vector summation in a ball (of any norm) of minimum radius, and methods of non-strict summation of vectors in a given area of d-dimensional space. These methods are applicable to problems of finding uniform distributions of multicomponent objects.

2. Application of the maximum flow and the minimum cut algorithms to problems of finding uniform distributions of one-component objects with prescribed constraints on the distribution areas of objects.

3. The method of a gradual reduction of the feasible solutions domain.

12:00-12:20Coffee Break
12:20-13:35 Session 8A: Game Theory (Online Session)
12:20
Hybrid Genetic Global Search Algorithm for Solving Hexamatrix Games

ABSTRACT. This work addresses the development of a hybrid approach to solving three-person polymatrix games (hexamatrix games). On the one hand, this approach is based on the reduction of the game to a nonconvex optimization problem and the Global Search Theory proposed by A.S. Strekalovsky for solving nonconvex optimization problems with (d.c.) functions representable as a difference of two convex functions.

On the other hand, to increase the efficiency of one of the key stages of the global search - constructing an approximation of the level surface of a convex function that generates the basic nonconvexity in the problem under study - operators of genetic algorithms are used.

12:35
Linear Differential Game with a Grid Terminal Set

ABSTRACT. In a finite-dimensional normed space, we consider a linear differential game of a given duration. Vectograms of the players' controls are compacts containing the origin. The goal of the first player is to lead at a fixed moment at least one of the phase coordinates to the neighborhood of the desired state, taking into account the periodicity. The non-convex terminal set, which is determined by this condition, is called the grid terminal set in the report. The goal of the second player is the opposite. Necessary and sufficient termination conditions are found and the corresponding controls of the players are constructed. As an example, the problem of control of a rotational mechanical system is considered, in which the specified termination condition acquires the meaning of leading one of the angles of the system to the neighborhood of the desired state.

12:50
Search for Nash equilibrium in quadratic quasiconcave games

ABSTRACT. It is known that a quadratic function with exactly one positive eigenvalue is quasiconcave on two convex sets. These sets are the images of two corresponding convex cones under the affine transformation which converts the initial quadratic function into its separable form. We consider normal form games with quadratic payoffs with at most one positive eigenvalue. If the strategy space of each player is a subset of the set on which its payoff function is quasiconcave, then a Nash equilibrium exists due to Kakutani's fixed point theorem. Otherwise, equilibrium points may not exist. We propose a method for finding an equilibrium using Nikaido-Isoda approach and the methodology studied in the paper Minarchenko I., Khamisov O. "On minimization of a quadratic function with one negative eigenvalue", Optim. Lett. 15, 1447–1455 (2021). If a game does not possesses an equilibrium, the method shows this fact numerically. Results of a computational experiment are provided.

13:05
Value of cooperation in a differential game of pollution control

ABSTRACT. The paper studies a linear-quadratic pollution control game for which a set of characteristics is introduced, including normalized values, showing how much the players lose if their assumptions about the structure of the game were wrong, and also if they refused to cooperate. All these characteristics (“value of information”, “value of cooperation” and their normalized counterparts) are new in the field of game theory and can be further applied to a wide class of problems. Theoretical results are demonstrated on the basis of data for the city of Penza (Russia). The reported study was funded by RFBR and DFG, project number 21-51-12007.

13:20
On the existence of a fuzzy core in an exchange economy

ABSTRACT. The fuzzy core is widely used in theoretical economics for modeling perfect competition. However, in modern literature, the proof of its existence is presented in an indirect way and applies a cumbersome construction. It usually is based on the idea of replicated economies, via standard core existence, followed by passing to the limits, allowing the number of replicas tends to infinity. The result is also proved under additional restrictive assumptions. We present a direct proof based on two well-known theorems: Michael's theorem on the existence of a continuous selector for a point-to-set mapping and Brouwer's fixed point theorem. This new direct proof is efficient and shortest among others. Moreover, now the existence of fuzzy core is stated under other weakest assumptions: agent preferences can be incomplete, non-transitive, satiated, and so on.

12:20-13:35 Session 8B: Operational Research Applications
12:20
On the Interference Cancellation by Reduced Channel Zero Forcing Class of Precodings in Massive MIMO Systems
PRESENTER: Evgeny Bobrov

ABSTRACT. In this research, we study the interference cancellation capabilities of receivers and transmitters in multiple-input-multiple-output (MIMO) systems using theoretical calculations and numerical simulations in Quadriga. We study so-called Reduced Channel Zero-Forcing (RCZF) class of precoding as well as Minimum MSE Interference Rejection Combiner (MMSE-IRC) and QR Maximum Likelihood Detection (QR-MLD) receivers. The precodings from the RCZF class are widely used in practice and include for example Zero-Forcing (ZF),  Regularized Zero-Forcing (RZF) and Iteratively Weighted MMSE precodings. Our theoretical and experimental results confirm that MMSE-IRC and QR-MLD receivers in combination with the RCZF precoding provide complete interference suppression asymptotically.

12:40
Spectrum Allocation in Optical Networks: DSatur Coloring and Upper Bounds

ABSTRACT. Routing and Spectrum Allocation (RSA) is one of the central problems in modern optical networks. In this setting, also called Flexible Grid, we want to find paths and allocate non-overlapping frequency slots for as many demands as possible. As opposed to the Routing and Wavelength Assignment (RWA) problem, where all frequency slots are of the same width, demands in Flexible Grids may require slots of different sizes, what makes the original NP-hard problem even more challenging. In this paper, we consider Spectrum Allocation (when routing is known), develop an efficient greedy algorithm based on "degree of saturation"-coloring, and by means of Constraint Programming, we show that the greedy algorithm is almost optimal even for hard real-world instances.

13:00
The VNS algorithm for the periodic pick-up and delivery helicopter routing problem in oil and gas offshore projects

ABSTRACT. In offshore field development projects, the high operating costs is a crucial part of the total expenses. In this paper, we consider the helicopter routing problem in a given time horizon. We need to deliver workers at the offshore platforms every day and return other workers to depot. We have a fleet of identical helicopters with known capacity. All routes start and finish at the depot, the length of each route cannot exceed a given threshold. We can split the demand for each platform and visit it by some helicopters. Our goal is to find the routes to satisfy all demands with minimal total travel length. To tackle this pick-up and delivery routing problem, we design the MILP model and adopt the VNS-algorithm. Some hard constraints are relaxed and included into the objective function with penalties. Computational results for the real world test instances of the JV Vietsovpetro company are discussed.

13:15
Differential Evolution for Short Wave Antenna Array Optimization

ABSTRACT. In this paper, we develop and study experimentally a differential evolution algorithm for a non-convex constrained quadratic programming problem, which has an application in radiophysics. In this application, it is required to maximize the directed radiation in short wave range, using a phased antenna array. The differential evolution method is adapted to the specifics of the problem under consideration. In the computational experiments, the proposed algorithm is compared to the gradient ascend method and BARON package, which is based on the branch and bound approach. A parallel implementation of the proposed algorithm on the GPU is described and experimaentally tested.

13:45-14:45Lunch
15:00-17:00 Session 9: Plenary Session (Online)
15:00
Numerical infinities and infinitesimals in optimization

ABSTRACT. In this talk, a recent computational methodology is described. It has been introduced with the intention to allow one to work with infinities and infinitesimals numerically in a unique computational framework. It is based on the principle ‘The part is less than the whole’ applied to all quantities (finite, infinite, and infinitesimal) and to all sets and processes (finite and infinite).The methodology uses as a computational device the Infinity Computer (a new kind of supercomputer patented in several countries) working numerically with infinite and infinitesimal numbers that can be written in a positional system with an infinite radix. On a number of examples (numerical differentiation, divergent series, ordinary differential equations, fractals, set theory, etc.) it is shown that the new approach can be useful from both theoretical and computational points of view. The main attention is dedicated to applications in optimization (local, global, and multi-objective). The accuracy of the obtained results is continuously compared with results obtained by traditional tools used to work with mathematical objects involving infinity.The Infinity Calculator working with infinities and infinitesimals numerically is shown during the lecture.

15:40
Coordination in Closed-Loop Supply Chains: A Dynamic Games Perspective

ABSTRACT. Lack of coordination between the parties involved in a supply chain typically leads to lower outcomes for manufacturers and retailers, and to lower consumer surplus. Further, the collection of past-purchased products at the end of their useful life, for remanufacturing or recycling purposes, is a crucial activity in optimizing operations management and achieving a better environmental performance.

In this talk, I will discuss some coordination mechanisms that could be implemented to improve the efficiency of a closed-loop supply chain, in a context of long-term strategic interactions between the agents and in the presence of demand uncertainties.

16:20
Store location and agglomeration in competitive and non-competitive retail

ABSTRACT. Agglomeration or clustering of stores can be observed in practice in the location of both competitive and non-competitive stores. What makes several shoe stores locate beside each other, or a shoe store locate close to a pants store? Hotelling in 1929 proposed an explanation; however, it only works under very special circumstances. Economists, transport and market researchers have found better explanations to this phenomenon: agglomeration is due to the savings obtained in multiple-stop shopping trips. Amazingly, these trips were only recently included into optimization models for optimal location, and their inclusion indeed changes the prescribed locations.

We study the effect of multiple-stop trips, both multipurpose shopping (MPS) and comparison shopping (CS), on location of retail stores. We analyze follower and (bi-level) leader-follower models for MPS and CS, in which customers use a binary, deterministic choice rule to decide to which store to go to make a purchase, and a MPS follower problem in which customers behave according to a random utility model.

17:00-17:15Coffee Break
17:15-19:15 Session 10A: Optimization and Applications (Online Session)
17:15
Primal-Dual Method for Optimization Problems with Changing Constraints

ABSTRACT. We propose a modified primal-dual method for general convex optimization problems with changing constraints. We obtain properties of Lagrangian saddle points for these problems which enable us to establish convergence of the proposed method. We describe specializations of the proposed approach to multi-agent optimization problems under changing communication topology and to feasibility problems.

17:30
Two-stage stochastic facility location problem with quantile criterion and choosing reliability level

ABSTRACT. A two-stage discrete facility location problem is considered. The demand for future products and the income from this demand is assumed to be random. In mathematical modeling of the decision-making process, the quantile criterion is used. This takes into account the requirements for the level of reliability as a criterion for the optimality of the chosen strategy. At the first stage of the decision-making procedure, a set of open facilities is selected and the distribution law of random demand is known. At the second stage, upon the realization of random demand for products, additional facilities can be opened and the profit taken with the opposite sign (quantile of losses) is minimized. The method of sample approximations is used to solve the optimization problem of choosing the open facilities for a given value of the reliability level. The resulting approximation problem is reduced to a linear programming problem. An optimization problem is also proposed for choosing the level of reliability of the quantile criterion. The choice of the level of reliability is carried out using the problem of minimizing the quantile function according to the optimization strategy and the level of reliability with an additional restriction on the value of the quantile function at the chosen level of reliability. A sample approximation is constructed. A theorem on sufficient conditions for the convergence of the designed sample approximations is proved. Under certain conditions, the resulting approximation problem can be reduced to a linear programming problem. The results of the work are illustrated by a numerical example.

17:45
Large-scale Modeling and Optimization of Production-Level Transportation System

ABSTRACT. Large-scale economic modeling is becoming a reality for big businesses, and it pushes their analytic and planning departments in very complicated areas of big data analytics and control. At the same time, it asks research communities in academia and else to develop adequate tools to operate models with millions of variables and gigabytes of data where traditional off-the-shelf solutions fail. This paper intends to describe our experience with one relatively common high-dimensional logistic problem and some of the mathematical and computational ideas we pursue to cope with it. In a nutshell, it describes a multi-product multi-index multi-period transportation problem of the linear optimization variety. Even if each of these sub-indices has a modest cardinality, their multiplicative effect quickly raises the dimensionality of the resulting problem into hundreds of millions. The additional complexity of this problem arises from complex interactions between sub-indices, originating from the plethora of technological conditions that can not be formalized in a regular way. These relationships change from one problem instance to another, often depending upon ad hoc operator decisions, state of transportation infrastructure, and others factors. The mathematics involved consists of sophisticated modeling efforts to describe these situations in a high-level language, advanced linear algebra for analyzing the models and developing potentially suitable algorithms, and effective programming implementation of the project. These parts will be described in reasonable detail, space and time permitting.

18:00
Parameter analysis of variable neighborhood search applied to multiprocessor scheduling with communication delays

ABSTRACT. When dealing with hard, real-life optimization problems, metaheuristics methods are considered a very powerful tool. If designed properly, they can provide high-quality solutions in reasonable running times. We are specially interested in Variable neighborhood search (VNS), a very popular metaheuristic for more than 20 years with many successful applications. Its basic form has a small number of parameters, however, each particular implementation can involve a problem-dependent set of parameters. This makes parameter analysis and performance assessment a challenging task. Contribution of this work is twofold: we develop a new variant of the VNS algorithm for the considered optimization problem and simplify the methodology for experimental analysis of metaheuristic algorithms. We conclude three stages of the parameter analysis: parameter definition, deciding the most influential parameters and analysis of their relationship. The analysis contributes to the design of VNS as a search problem in the space of its parameters. We apply the sophisticated approach that equally relies on visual as well as on the statistical and machine learning methods that have become standard practice for parameter tuning and experimental evaluation of metaheuristic algorithms. The obtained results are presented and discussed in this study.

18:15
Dispersion problem under capacity and cost constraints: multiple neighborhood tabu search

ABSTRACT. Diversity and dispersion problems consists of selecting a subset of elements from a given set so that their diversity is maximized. The one of most recently proposed variant is the MaxMin dispersion problem with capacity and cost constraints. This variant usually called the generalized dispersion problem. In this paper we propose variant of tabu search based on multiple neighborhoods to solve large-size instances. Extensive numerical computational experiments are performed to compare our tabu search metaheuristic with the state-of-art heuristic. Results on public benchmark instances show the superiority of our proposal with respect to the previous algorithms.

18:30
A mathheuristic approach for the supplementary school timetabling problem

ABSTRACT. We consider a new timetabling problem that arises in a real-life application. A school, which provides an additional educational service, improving English language knowledge, aims to enroll an educational process. At first, the school collects the applications from potential students. Each of them indicates the set of time windows he(she) is able to attend the lessons in and take a part in a trial lesson to define their level of knowledge. When a reasonable number of applications is received the school runs the schedule construction process. Students are united into small groups if they have similar ages, the same level of knowledge, and shareable time windows. The size of a group is limited. Students who do not fit the current schedule, are kept on the waiting list until some more applications arrive. The process then is repeated, additional groups and lessons are added to the previous schedule. The objective of the school is two-fold: maximize the number of students attending while keeping a high number of students in a group on average. In this research, we provide a mathematical model for the described problem in terms of integer linear programming. We propose a hybrid algorithm combining a MIP solver for a simplified version of the problem and a constructive heuristic to solve the entire problem. Computational results carried on real and artificially generated instances show that the proposed approach is able to find solutions close to optimal.

18:45
Exploring the Identification of Autoregression Model by General Least Deviation Method

ABSTRACT. We consider a new approach to the analysis of time series based on the use of quasi-linear recurrence relations. Unlike neural networks, this approach makes it possible to explicitly obtain high-quality quasi-linear difference equations (adequately describing the considered process). Currently, we developed and tested methods for identifying the parameters of a single equation. In our paper we discuss and test our identification algorithm for parameters of quasilinear recurrence equation. We use it to solve the problem of regression analysis with mutually dependent observable variables, which allows to implement the generalized last deviations method (GLDM). Using this model we held the computational experiment to identify the parameters of quasi-linear difference equations describing the process of spreading Covid-19 infection. We test our model on three different types of processes: (1) monotonous (forecasting of cumulative cases); (2) aperiodic (forecasting of local extremums for one wave of infection spreading); (3) oscillatory (forecasting the daily cases). The model using the identified parameters allows to obtain the long-time forecast.