ABSTRACT. We are given a set of parallel jobs that have to be executed on a set of speed-scalable processors varying their speeds dynamically. Running a job at a slower speed is more energy efficient, however it takes longer time and affects the performance. Every job is characterized by processing volume and number of required processors. Our objective is to minimize the total completion time so that the energy consumption is not greater than a given energy budget. For various particular cases we propose polynomial-time approximation algorithms, consisting of two stages. At the first stage, we give an auxiliary convex program. By solving this problem in polynomial time, we find processing times of jobs and a lower bound on the makespan. Then, at the second stage, we transform our problem to the classical problem without speed scaling, and construct a feasible schedule using the obtained durations of jobs.

The research is supported by RFBR grant 20-07-00458.

ABSTRACT. We consider the problem of constructing the shortest schedule for processing jobs located at nodes of a transportation network by machines travelling through the edges of the network. Initially, all machines are located at a special node (called “depot”), and should return to the depot at the completion of all jobs. The time when the last machine returns to the depot is taken for the objective function of our problem. The jobs are parts of a Flow Shop system, which means that each job must be processed my machines M₁,…,M_m in this fixed order (the same for all jobs); the processing of job J_j by machine M_i requires a pre-specified time p_ij. The network is represented by a complete directed graph G=(V,E) with weights of arcs not assumed to be symmetric. We consider a special case of this problem with TWO machines and with the number of nodes bounded above by a constant value g. For this case, we show that the problem can be solved in polynomial time.

ABSTRACT. Tight optima localization interval for a classical open shop scheduling problem with three machines was established by S. Sevastyanov and I. Chernykh in 1998. It was proved that for any problem instance its optimal makespan does not exceed 4/3 times the standard lower bound. The process of proof involved massive computer-aided enumeration of the subsets of instances of the problem considered and took about 200 hours of running time to complete. This make it seemingly impossible to use the same approach for more complicated problems, i.e. four-machine open shop for which the optima localization interval is still unknown. In this paper we apply that computer-aided approach to the three-machine routing open shop problem on a two-node transportation network. For this generalization of the plain open shop problem we derive some extreme instance properties and prove that optimal makespan does not exceed 4/3 times the standard lower bound, thus generalizing the result previously known for the three-machine open shop.

ABSTRACT. This work addresses the optimistic statement of a bilevel optimization problem with a general d.c. optimization problem at the upper level and a convex optimization problem at the lower level. First, we use the reduction of the bilevel problem to a nonconvex mathematical optimization problem using the well-known Karush-Kuhn-Tucker approach. Then we employ the novel Global Search Theory and Exact Penalty Theory to solve the resulting nonconvex optimization problem. Following this theory, the special method of local search in this problem is constructed. This method takes into account the structure of the problem in question.

ABSTRACT. This paper addresses the general optimization problem (P) with equality and inequality constraints and the cost function given by d.c. functions. We reduce the problem to a penalized problem ( P_σ) without constraints with the help of the Exact Penalization Theory. Further, we show that the reduced problem is also a d.c. minimization problem. This property allows us to prove the Global Optimality Conditions (GOCs), which reduce the study of the penalized problem to an investigation of a family of linearized (convex) problems tractable with the help of standard convex optimization methods and software.

In addition, we propose a new Local Search Scheme (LSS1) which produces a sequence of vectors converging to a so-called critical point. On the other hand, the vector satisfying the GOCs turns out to be also a critical point.

On the basis of the GOCs for finding a global solution to (P_σ), we develop a Global Search Scheme, including the LSS1 with an update of the penalty parameter, and a special stopping criteria allowing detection of a feasible vector in the original problem (P), and, consequently, a global solution to the original Problem (P).

ABSTRACT. The paper addresses the problem of solving the system of nonlinear equations with d.c. functions (i.e. a difference of convex functions). The original problem is reduced to an unconstrained optimization problem, where the goal function is presented as d.c. function. For solving this problem we apply the Global Search Theory for d.c. minimization problem, based on global optimality conditions. The methods of local and global searches are developed. The computational experiments were carried out on test instances with nonconvex quadratic functions of high dimension. The effectiveness of the proposed approach is demonstrated by its comparison with well-known specialized software for solving systems of nonlinear equations.

ABSTRACT. Solution and analysis of some mathematical programming problems may be simplified when these problems are symmetric under appropriate linear transformations. In particular, knowledge of the symmetries may help reduce the problem dimension, cut the search space by linear cuts or obtain new local optima from the ones previously found. While the previous studies of symmetries in mathematical programming usually dealt with permutations of coordinates of the solutions space, the present paper considers a larger group of invertible linear transformations. We study the special case of quadratic programming problem, where the objective function and the constraints are given by quadratic forms, and the sum of all matrices of quadratic forms, involved in the constraints, is a positive definite matrix. In this setting, it is sufficient to consider only the orthogonal transformations of the solution space. In this group of orthogonal transformations, we describe the structure of the subgroup which gives the symmetries of the problem. Besides that, a method for finding such symmetries is outlined, and illustrated in two simple examples.

ABSTRACT. The Capacitated Vehicle Routing Problem (CVRP) is the well-known combinatorial optimization problem having numerous practically important applications. CVRP is strongly NP-hard (even on the Euclidean plane), hardly approximable in the general case and APX-complete for an arbitrary metric. Meanwhile, for the geometric settings of the problem, there are known a number of quasi-polynomial and even polynomial time approximation schemes. Among these results, the well-known QPTAS proposed by A.Das and C.Mathieu appears to be the most general. In this paper, we propose the first extension of this scheme to a more wide class of metric spaces. Actually, we show that the metric CVRP has a QPTAS any time when the problem is set up in the metric space of any fixed doubling dimension d>1 and the capacity does not exceed polylog(n).

ABSTRACT. It is known that there exist 4-regular, 1-tough graphs which are non-hamiltonian. The smallest such graph known has n=18 nodes and was found by Bauer et al., who conjectured that all 4-regular, 1-tough graphs with n≤ 17 are hamiltonian. They in fact proved that this is true for n≤15, but left open the possibility of non-hamiltonian graphs of 16 or 17 nodes. By using ILP for modeling a counterexample, and then showing that the model has no solutions, we give an algorithmic proof that their conjecture was indeed correct.

ABSTRACT. A method for solving the terminal control problem with discrete phase constraints is proposed. The method is based on the Lagrangian formalism and duality theory, thanks to which it is possible to realize the necessary and sufficient optimality condition for the class of convex problems with linear dynamics. The time interval is divided into a finite number of sub-segments, on each of which, using the technique developed by the authors, the basic problem is solved as a terminal control problem with a boundary-value problem at the right-hand end of the interval. In each such problem, the minimum of the convex objective functional is sought on the set determined by phase constraints (convex polyhedron). As a result, the original problem is broken into a finite number of sub-problems. The peculiarity of the statement of the problem is that all intermediate problems are solved sequentially, and the right end of the trajectory found on each subsegment (as a solution to the finite-dimensional boundary value optimal control problem) serves as the initial value for the phase trajectory in the next time interval. To solve intermediate problems, a saddle-point method of an extragradient type is implemented. The convergence of the method to the solution in all its components is proved: weak convergence in controls, strong convergence in phase and conjugate trajectories, and also in finite-dimensional terminal variables.

The reported study was supported by the Russian Science Foundation (Research Project 18-01-00312).

ABSTRACT. A terminal control problem with linear controlled dynamics on a fixed time interval is considered. A boundary value problem in the form of a linear programming problem is stated in a finitedimensional terminal space at the right endpoint of the interval. The solution of this problem implicitly determines a terminal condition for the controlled dynamics. A saddle-point approach to solving the problem is proposed, which is reduced to the computation a saddle point of the Lagrangian. The approach is based on saddle-point inequalities in terms of primal and dual variables. These inequalities are sufficient optimality conditions. A method for computing a saddle point of the Lagrangian is described. Its monotone convergence with respect to some of the variables on their direct product is proved. Additionally, weak convergence with respect to controls and strong convergence with respect to phase and adjoint trajectories and with respect to terminal variables of the boundary value problem are proved. The saddle-point approach is used to synthesize a feedback control in the case of control constraints in the form of a convex closed set. This result is new, since, in the classical case of the theory of linear regulators, a similar assertion is proved without constraints imposed on the controls. The theory of linear regulators relies on matrix Riccati equations, while the result obtained is based on the concept of a support function (mapping) for the control set.

The reported study was supported by the Russian Science Foundation (Research Project 18-01-00312).

ABSTRACT. Recently some interesting classes of non-smooth and non-Lipschitz convex optimization problems were selected and first-order methods were analyzed by Yu.Nesterov and H.Lu (see [1] and [2]). We consider optimization problems with functional constraints with similar smoothness conditions. Some analogues of switching subgradient schemes are proposed for convex programming problems with a relative Lipschitz-continuous objective or functional constrants. The corresponding general class of problems for the appropriate concept of inexact model (analogous to [3]) is studied. Non-adaptive and partial adaptive Mirror Descent methods are investigated. Optimality of the proposed methods on the appropriate class of problems is stated.

[1] Nesterov Yu. Relative Smoothness: New Paradigm in ConvexOptimization, September 4, 2019 (EUSIPCO 2019, A Coruna, Spain).

[2] Lu H. "Relative-Continuity" for Non-Lipschitz Non-Smooth Convex Optimization using Stochastic (or Deterministic) Mirror Descent arXiv:1710.04718 [math.OC].

[3] Tyurin A.I., Gasnikov A.V. Fast gradient descent method for convex optimization problems with an oracle that generates a (\delta, L)-model of a function in a requested point // Computational Mathematics and Mathematical Physics. 2019. V.59, N 7. P. 1137–1150.

ABSTRACT. It has been observed in [Rodionova et al., GECCO'19] that the 2-rate (1+λ) Evolutionary Algorithm previously suggested in [Doerr et al., GECCO'17] suffers from the weakness that its performance crucially depends on the threshold at which the mutation rate is capped to prevent from converging to zero. This effect is an issue already when focusing on the simple-structured OneMax problem, the problem of minimizing the Hamming distance to an unknown bit string. Here, a small lower bound is preferable when the offspring population size λ is small, whereas a larger lower bound is better for large λ.

In this work, we introduce a secondary parameter control scheme, which adjusts the lower bound during the run. We demonstrate, by extensive experimental means, that our algorithm performs decently on all OneMax problems, independently of the offspring population size. It therefore appropriately removes the dependency on the lower bound. The key ingredient of our algorithm is a voting approach, which compares the number of recommendations to increase the mutation rate threshold with those recommending a reduction.

We also evaluate our algorithm for several other benchmark problems, and show that it works fine at least for the sufficiently small values of λ.

ABSTRACT. Nowadays vehicles are highly customizable products. Indeed, they can be equipped with a great number of options directly chosen by the customers. This situation provides several harness design problems to automotive companies, where by harness we mean the set of conducting wires (cables), positioned within the vehicle frame (chassis), which transmit information and electrical power to the options to make them operative. In this context we focus on an optimization problem arising in the construction and assembly phase of the harness within a vehicle. The options selected by customers have to be connected through a harness shaped in a tree structure within the vehicle chassis. In particular, the wiring has to connect subsets composed of two or more options. The total length of the connecting cables could be very large if a dedicated cable would be used for each couple of options in each subset. This length can be significantly reduced by realizing the connection through the usage of cable weldings. This work introduces for the first time the problem of the optimal placement of the weldings on the wiring harness tree of a vehicle, aimed at minimizing the total length and/or the cost of the cables, weighted by their gauge. The problem can be schematized as a p-median problem (PMP) on a tree in a continuous and discrete domain, with additional technological constraints related to the welding positions and mutual distance. This work proposes an integer linear programming model and a matheuristic aimed at finding exact and/or heuristic solutions for this constrained PMP. The efficiency and the effectiveness of the proposed methodologies have been proved through the solution of test instances built from real data provided by an automotive company.

ABSTRACT. We study the influence of the particular choice of operators on the running time of the recently proposed (1+( λ,λ)) genetic algorithm. In particular, we consider three choices for the mutation operator, six choices of the crossover operator, three strategies for sampling population sizes based on non-integer parameter values, and four choices of what to do when the best mutant is better than the parent.

We test all these 216 configurations on four optimization problems and in three adjustment flavours: the fixed λ, the unlimited self-adjustment of λ and the logarithmically capped one. For each of these configurations, we consider both the default values of the hyperparameters and the ones produced by the irace parameter tuning tool.

The result of our experimental analysis showed that there exists a configuration that is robust on linear functions and is roughly two times faster compared to the initially proposed one and 12% faster on the OneMax problem compared to one of the similar previous studies. An even more robust configuration exists, which has a slightly worse performance on OneMax but is better on satisfiability problems. Such configurations can be the default choices for the practical evaluation of the (1+( λ,λ)) GA.

ABSTRACT. We consider relative or subjective optimization problems where the goal function and feasible set are dependent of the current state of the system under consideration. We propose equilibrium formulations of the corresponding problems that lead to general (quasi-)equilibrium problems. We propose to apply a regularized version of the penalty method for the general quasi-equilibrium problem, which enables us to establish existence results under weak coercivity conditions and replace the quasi-equilibrium problem with a sequence of the usual equilibrium problems. We describe several examples of applications and show that the subjective approach can be extended to non-cooperative game problems.

ABSTRACT. The Restricted Capacitated Facility Location Problem is the optimization problem, where it is needed to open facilties from given set of possible locations to serve demands of given clients with both constraints on edge capacities and facility capacities, knowning the transportation cost for each edge and opening cost for each facility to minimize total costs. We want to investigate some interesting particular cases of this problem and present faster algorithms for solving such particular problems. Also we implement proposed algorithms and conclude the work with computational results.

ABSTRACT. The article is devoted to the development of the branch and bound algorithm for competitive facility location and design problem with elastic demand, which was formulated in the article by Aboolian R., Berman O. and Krass D. (2007). In the problem, there is a set of demand points and its subset of potential locations for facilities with different design scenarios. Some of them are captured by the pre-existing competing company. A new Company plans to enter the market and to locate new facilities. Customers select companies based on their attractiveness and distance from their location. So such kind of demand isn't fixed and is called elastic. The aim of the new Company is to capture the interest of the greatest number of customers thus serving the largest share of the demand. The corresponding mathematical model contains a nonlinear objective function. The number of algorithms known for solving the competitive facility and design problem is little. Commercial software does not solve the problem exactly. An adapted weighted greedy heuristic algorithm is proposed by Aboolian R., Berman O. and Krass D. Earlier we developed Variable Neighborhood Search algorithms, Threshold Algorithms and Ant Colony Optimization Algorithm for this problem. In this paper, a branching scheme for the branch and bound method is proposed. The branch and bound algorithm is constructed. Computational experiments were carried out. The results of numerical experiments are discussed.

ABSTRACT. Differential game has emerged as a useful tool for the study in depth various problems in marketing, recognizing that most marketing decision. The new class of differential games with continuous updating is assumed that at each time instant, players have or use information about the game structure defined on a closed time interval with a fixed duration. A major concern in such a setting is how to define the behavior of each player as time goes by. Since there is a continuous shift of time horizon, information about the game updates. The player maximizes his or her objective function only on a closed time interval. This paper shows how to formulate a continuous updating game, introduces main solution concepts for both initial differential games and continuous updating games, and discusses some classical results. In particular, Pontryagin’s maximum principle is formalized and presented for the open-loop Nash equilibrium for this class of games.

ABSTRACT. The paper deals with a game-theoretic model of best choice with incomplete information. In this model experts (players) observe a sequence of incoming contestants each described by two random quality components. The first component is announced to players and the other one is hidden. Each player has to choose in his team two contestants. Each experts chooses a consestant based on known information about it. The winner is the player whose team includes a contestant with the maximum sum of both quality components. The optimal strategies of the players and their payoffs in the game are derived.

ABSTRACT. We deal with n-person multistage multicriteria games in extensive form (see, e.g., [2, 4, 5, 6]) with chance moves and examine the basic properties of Pareto equilibria as well as the possibility of sustainable cooperation. Firstly, we prove that such games possess a (subgame perfect) Pareto equilibria in pure strategies and provide an algorithm how to construct a unique SPPE based on the so called MSRD rule proposed in [6].

In order to achieve and implement a long-term cooperative agreement in a multicriteria dynamic game we have to solve in series the following problems. First, when players seek to achieve the maximal total vector payoff of the grand coalition, they face the problem of choosing a unique Pareto efficient payoffs vector. In the dynamic setting it is necessary that a specific method the players agreed to accept in order to choose a particular Pareto optimal solution not only takes into account the relative importance of the criteria, but also satisfies time consistency [1, 2, 4, 5, 6], i.e., a fragment of the optimal cooperative bundle of the trajectories in the subgame should remain optimal in this subgame.

In this paper, we use the rule of minimal sum of relative deviations (MSRD) from the ideal payoffs vector (see [6] for detailes) to find a unique optimal cooperative bundle of the trajectories, which is proved to satisfy time consistency at initial position of the game (see, e.g., [7]).

After choosing the cooperative bundle of the trajectories it is necessary to construct a vector-valued characteristic function. To this end, we use the ζ-characteristic function introduced in [3] and a novel η-characteristic function as well as the MSRD rule in order to choose a particular Pareto efficient solution for the auxiliary vector optimization problems. We assume that the cooperative multicriteria game satisfies the component-wise transferable utility property, i.e., we allow the payoff to be transferred between the players within the same criterion. Note that the main measurable criteria used in multicriteria resource management problems (for instance, water supply amount, cost of water purification, the quota for the use of a common resource, the quota for emissions, profit from the use of a common resource, etc.) usually satisfy the required transferable utility property. To determine the optimal payoff allocation we use a vector analogue of the Shapley value.

Lastly, to guarantee the sustainability of the achieved long-term cooperative agreement one needs to design a consistent imputation distribution procedure (IDP) or a payment schedule (see, e.g., [1, 2, 4, 5, 6, 7] that should satisfy a set of useful properties. The detailed review of dynamical properties the IDP may satisfy for multistage multicriteria games is presented in [5, 6]. In this paper we mainly focus on the efficiency constraint and the strict balance condition as well as time consistency (at initial position of the game) and provide a generalization of the incremental IDP to implement a long-term cooperative agreement in a multistage multicriteria game with chance moves.

The research was funded by RFBR under the research project 18-00-00727 (18-00-00725).

References

[1] L. Petrosyan, Stable solutions of differential games with many participants, Vestnik of Leningrad University 19 (1977), pp. 46-52. (in Russian).

[2] L. Petrosyan, D. Kuzyutin, Games in extensive form: optimality and stability, Saint Petersburg University Press, 2000. (in Russian).

[3] E. Gromova, L. Petrosyan, On an approach to constructing a characteristic function in cooperative differential games, Automation and Remote Control, Vol. 78 (9) (2017) 1680-1692.

[4] D. Kuzyutin, E. Gromova, Ya. Pankratova, Sustainable cooperation in multicriteria multistage games, Operations Research Letters, Vol. 46, issue 6, (2018), pp. 557-562.

[5] D. Kuzyutin, M. Nikitina, Time consistent cooperative solutions for multistage games with vector payoffs, Operations Research Letters, Vol. 45, issue 3, (2017), pp. 269-274.

[6] D. Kuzyutin, N. Smirnova, E. Gromova, Long-term implementation of the cooperative solution in multistage multicriteria game, Operations Research Perspectives, 6, (2019), 100107.

[7] P. Reddy, E. Shevkoplyas, G. Zaccour, Time-consistent Shapley value for games played over event trees, Automatica, 49 (6),(2013), 1521-1527.

ABSTRACT. The class of differential games with continuous updating is quite new, there it is assumed that at each time instant, players use information about the game structure (motion equations and payoff functions of players) defined on a closed time interval with a fixed duration. As time goes on, information about the game structure updates. A linear quadratic case for this class of games is particularly important for practical problems arising in the engineering of human-machine interaction. In this paper it is particularly interesting that the open-loop strategies are used to construct the optimal ones, but subsequently we obtain strategies in feedback form. Using this strategies the notions of Shapley value and Nash equilibrium as an optimality principles for cooperative and non-cooperative case respectively are defined and the optimal strategies for the linear quadratic case are presented.

ABSTRACT. For decades, for many well-known combinatorial optimization problems, the approximability results in the class of algorithms with theoretical performance guarantees have had the quite similar nature. For instance, the classic Traveling Salesman Problem (TSP) is strongly NP-hard both in general and even in very specific settings, e.g. in the Euclidean plane. The problem is hardly approximable in general setting, it is APX-complete for an arbitrary metric, whilst, the problem admits polynomial time approximation schemes (PTAS) in the Euclidean space of an arbitrary fixed dimension. Recent results in the field of the analysis of finite metric spaces shed a light to the design of approximation schemes for a wide family of metric settings of these problems. In this tutorial, we give a short overview of such an approach leading to the PTAS for the metric TSP in metric space of any fixed doubling dimension.

ABSTRACT. Given an optimization problem and a feasible solution to it, the corresponding inverse optimization problem is to find a minimal adjustment of the cost vector under some norm such that the given solution becomes optimum. Inverse optimization problems have been applied in diverse areas, ranging from geophysical sciences, traffic networks, communication networks, facility location problems, finance, electricity markets, and medical decision-making. It has been studied in various optimization frameworks including linear programming, combinatorial optimization, conic, integer and mixed-integer programming, variational inequalities, and countably infinite linear problems and robust optimization. In this talk, we mainly concentrate on inverse combinatorial optimization problems (ICOP). We will introduce some classes of ICOP as well as general methods to solve them. Some open problems are proposed. We also discuss some generalized inverse optimization problems. We introduce inverse optimization problems on spanning trees and mainly concentrate on the inverse max+sum spanning tree problems in which the original problem aims to minimize the sum of a maximum weight and a sum cost of a spanning tree.