Skip to main content
main-content

Über dieses Buch

This book constitutes the proceedings of the 19th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2020, held in Novosibirsk, Russia, in July 2020. The 31 full papers presented in this volume were carefully reviewed and selected from 102 submissions. The papers are grouped in these topical sections: discrete optimization; mathematical programming; game theory; scheduling problem; heuristics and metaheuristics; and operational research applications.

Inhaltsverzeichnis

Frontmatter

Session 1: Invited Talks

Frontmatter

Global and Local Search Methods for D.C. Constrained Problems

This paper addresses the general optimization problem ($$\mathcal P$$) with equality and inequality constraints and the cost function given by d.c. functions. We reduce the problem to a penalized problem ($$\mathcal P_{\sigma }$$) 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 ($$\mathcal P_{\sigma }$$), 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 ($$\mathcal P$$), and, consequently, a global solution to the original Problem ($$\mathcal P$$).

Alexander S. Strekalovsky

Dual Newton’s Methods for Linear Second-Order Cone Programming

The linear second-order cone programming problem is considered. For its solution, two dual Newton’s methods are proposed. These methods are constructed with the help of optimality conditions. The nonlinear system of equations, obtained from the optimality conditions and depended only from dual variables, is solved by the Newton method. Under the assumption that there exist strictly complementary solutions of both primal and dual problems the local convergence of the methods with super-linear rate is proved.

Vitaly Zhadan

Discrete Optimization

Frontmatter

On Symmetry Groups of Some Quadratic Programming Problems

Solution and analysis of mathematical programming problems may be simplified when these problems are symmetric under appropriate linear transformations. In particular, a 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 the 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 a special case of the quadratic programming problem, where the objective function and 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 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.

Anton V. Eremeev, Alexander S. Yurkov

An Extension of the Das and Mathieu QPTAS to the Case of Polylog Capacity Constrained CVRP in Metric Spaces of a Fixed Doubling Dimension

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), hard to approximate 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 $$\mathrm {polylog}\,{(}n)$$.

Michael Khachay, Yuri Ogorodnikov, Daniel Khachay

Using Integer Programming to Search for Counterexamples: A Case Study

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\le 17$$ are hamiltonian. They in fact proved that this is true for $$n\le 15$$, but left open the possibility of non-hamiltonian graphs of 16 or 17 nodes. By using ILP for modeling a counterexample, and then finding out that the model has no solutions, we give an algorithmic proof that their conjecture was indeed correct.

Giuseppe Lancia, Eleonora Pippia, Franca Rinaldi

On Asymptotically Optimal Solvability of Max m-k-Cycles Cover Problem in a Normed Space

We consider the intractable problem of finding m edge-disjoint vertex covers in d-dimensional normed space with maximum total weight, such that each of them has exactly k cycles. We construct a polynomial-time approximation algorithm for solving this problem and derive conditions of its asymptotical optimality.

Edward Kh. Gimadi, Ivan A. Rykov

Mathematical Programming

Frontmatter

D.C. Constrained Optimization Approach for Solving Metal Recovery Processing Problem

This paper was motivated by an industrial optimization problem arisen at the Erdenet Mining Corporation (Mongolia). The problem involved real industrial data turned out to be a quadratically constrained quadratic programming problem, which we solve by applying the global search theory for general DC programming. According to the theory, first, we obtain an explicit DC representation of the nonconvex functions involved in the problem. Second, we perform a local search that takes into account the structure of the problem in question. Further, we construct procedures for escaping critical points provided by the local search method. In particular, we propose a new way of constructing an approximation of the level set based on conjugated vectors. The computational simulation demonstrates that the proposed method is a quite flexible tool which can fast provide operations staff with good solutions to achieve the best performance according to specific requirements.

Rentsen Enkhbat, Tatiana V. Gruzdeva, Jamsranjav Enkhbayr

On Solving the Quadratic Sum-of-Ratios Problems

This paper addresses the numerical solution of fractional programs with quadratic functions in the ratios. Instead of considering a sum-of-ratios problem directly, we developed an efficient global search algorithm, which is based on two approaches to the problem. The first one adopts a reduction of the fractional minimization problem to the solution of an equation with an optimal value of a parametric d.c. minimization problem. The second approach reduces the original problem to the optimization problem with nonconvex (d.c.) constraints. Hence, the fractional programs can be solved by applying the Global Search Theory of d.c. optimization.The global search algorithm developed for sum-of-ratios problems was tested on the examples with quadratic functions in the numerators and denominators of the ratios. The numerical experiments demonstrated that the algorithm performs well when solving rather complicated quadratic sum-of-ratios problems with up to 100 variables or 1000 terms in the sum.

Tatiana V. Gruzdeva, Alexander S. Strekalovsky

Adaptive Descent Splitting Method for Decomposable Optimization Problems

We suggest a modified descent splitting method for optimization problems having a special decomposable structure. The proposed modification maintains the basic convergence properties but enables one to reduce computational efforts per iteration and to provide computations in a distributed manner. On the one hand, it consists in component-wise choice of descent directions together with a special threshold control. On the other hand, it involves a simple adaptive step-size choice, which takes into account the problem behavior along the iteration sequence. Preliminary computational tests confirm the efficiency of the proposed modification.

Igor Konnov, Olga Pinyagina

Convergence Analysis of Penalty Decomposition Algorithm for Cardinality Constrained Convex Optimization in Hilbert Spaces

The paper examines an algorithm for finding approximate sparse solutions of convex cardinality constrained optimization problem in Hilbert spaces. The proposed algorithm uses the penalty decomposition (PD) approach and solves sub-problems on each iteration approximately. We examine the convergence of the algorithm to a stationary point satisfying necessary optimality conditions. Unlike other similar works, this paper discusses the properties of PD algorithms in infinite-dimensional (Hilbert) space. The results showed that the convergence property obtained in previous works for cardinality constrained optimization in Euclidean space also holds for infinite-dimensional (Hilbert) space. Moreover, in this paper we established a similar result for convex optimization problems with cardinality constraint with respect to a dictionary (not necessarily the basis).

Michael Pleshakov, Sergei Sidorov, Kirill Spiridonov

Game Theory

Frontmatter

Dixit-Stiglitz-Krugman Model with Nonlinear Costs

We study the market equilibrium in international trade monopolistic competition model a‘la Dixit-Stiglitz-Krugman with homogeneous firms. The utility of consumers are additive separable. Transport costs are of “iceberg type.” The only production factor is labor. The concrete functional form of sub-utility function is assumed unknown. Thus, it is not possible to get the equilibrium in closed form. We examine the local symmetric comparative statics of consumption, prices, firms masses and firms sizes with respect to transport costs. For linear production costs, the results about equilibria near free trade and autarky are known. We show that many of these results are true for the case of non-linear production costs.

Ivan Belyaev, Igor Bykadorov

Investments in R&D in Monopolistic Competitive Trade Model

We study a monopolistic competition model in the open economy case. The utility of consumers are additive separable. The producers can choose technology (R&D) endogenously. We examine the local comparative statics of market equilibrium with respect to trade costs (of iceberg type). Our main finding is the following: increasing trade costs has opposite impacts on mass of firms and productivity. Moreover, we study the cases of small trade costs and symmetric (on numbers of consumers) countries.

Igor Bykadorov

On the Cooperative Behavior in Multistage Multicriteria Game with Chance Moves

We consider a class of multistage multicriteria games in extensive form with chance moves where the players cooperate to maximize their expected joint vector payoff. Assuming that the players have agreed to accept the minimal sum of relative deviations rule in order to choose a unique Pareto optimal payoffs vector, we prove the time consistency of the optimal cooperative strategy profile and corresponding optimal bundle of the cooperative trajectories. Then, if the players adopt a vector analogue of the Shapley value as the solution concept, they need to design an appropriate imputation distribution procedure to ensure the sustainability of the achieved cooperative agreement. We provide a generalization of the incremental payment schedule that is applicable for the games with chance moves and satisfies such advantageous properties as the efficiency, strict balance condition and the time consistency property in the whole game. We illustrate our approach with an example of the extensive-form game tree with chance moves.

Denis Kuzyutin, Ekaterina Gromova, Nadezhda Smirnova

On a One-Dimensional Differential Game with a Non-convex Terminal Payoff

A one-dimensional differential game is considered, in which the payoff is determined by the modulus of the deviation of the phase variable at a fixed time from the set value, taking into account the periodicity. The first player seeks to minimize the payoff. The goal of the second player is the opposite. For this problem, the price of the game is calculated and optimal player controls are constructed. As an example, we consider the problem of controlling a rotational mechanical system in which the goal of the first player acquires the meaning of minimizing the modulus of deviation of the angle from the desired state.

Igor’ V. Izmest’ev, Viktor I. Ukhobotov

Open-Loop Based Strategies for Autonomous Linear Quadratic Game Models with Continuous Updating

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 the feedback form. Using these strategies the notions of Shapley value and Nash equilibrium as optimality principles for cooperative and non-cooperative cases respectively are defined and the optimal strategies for the linear-quadratic case are presented.

Ildus Kuchkarov, Ovanes Petrosian

On Iterative Methods for Searching Equilibrium in Pure Exchange Economy with Multiplicative Utilities of Its Agents

We consider the classical Arrow–Debreu model for a pure exchange economy with multiplicative utilities of its agents. To calculate its equilibrium prices, we present a new iterative algorithm that simulates the simplest intuitive forms of the economic behavior of market agents. It converges under very weak assumptions. The algorithm relies on increasing prices for scarce products only. Moderate inflation, accompanying the computational process, plays a positive role in establishing an equilibrium between commodity supply and demand. Schemes have a meaningful economic interpretation. The convergence theorems are proved, and the results of numerical experiments are presented, including other types of economies.

Leonid D. Popov

The Continuous Hotelling Pure Location Game with Elastic Demand Revisited

The Hotelling pure location game has been revisited. It is assumed that there are two identical players, strategy sets are one-dimensional, and demand as a function of distance is constant or strictly decreasing. Besides qualitative properties of conditional payoff functions, attention is given to the structure of the equilibrium set, best-response correspondences and the existence of potentials.

Pierre von Mouche

Scheduling Problem

Frontmatter

An Improved Approximation Algorithm for the Coupled-Task Scheduling Problem with Equal Exact Delays

We study the coupled-task single machine scheduling problem with equal exact delays and makespan as the objective function. It is known that the problem cannot be approximated with a factor better than 1.25 unless P $$=$$ NP. In this paper, we present a 2.5-approximation algorithm for this problem, which improves the best previously known approximation bound of 3. The algorithm runs in time $$O(n\log n)$$ where n is the number of jobs.

Alexander Ageev, Mikhail Ivanov

On the Optima Localization for the Three-Machine Routing Open Shop

A tight optima localization interval for the 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 $$\frac{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 h of the running time to complete. This makes it seemingly impossible to use the same approach for more complicated problems, i.e. the 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 the optimal makespan does not exceed $$\frac{4}{3}$$ times the standard lower bound, thus generalizing the result previously known for the three-machine open shop.

Ilya Chernykh, Olga Krivonogova

Makespan Minimization for Parallel Jobs with Energy Constraint

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 the processing volume and the number of the required processors. Our objective is to minimize the maximum 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.

Alexander Kononov, Yulia Kovalenko

A Polynomial-Time Algorithm for the Routing Flow Shop Problem with Two Machines: An Asymmetric Network with a Fixed Number of Nodes

We consider the routing flow shop problem with two machines on an asymmetric network. For this problem we discuss properties of an optimal schedule and present a polynomial time algorithm assuming the number of nodes of the network to be bounded by a constant. To the best of our knowledge, this is the first positive result on the complexity of the routing flow shop problem with an arbitrary structure of the transportation network, even in the case of a symmetric network. This result stands in contrast with the complexity of the two-machine routing open shop problem, which was shown to be NP-hard even on the two-node network.

Ilya Chernykh, Alexander Kononov, Sergey Sevastyanov

Heuristics and Metaheuristics

Frontmatter

Optimal Location of Welds on the Vehicle Wiring Harness: P-Median Based Exact and Heuristic Approaches

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.

Maurizio Boccia, Adriano Masone, Antonio Sforza, Claudio Sterle

On Non-elitist Evolutionary Algorithms Optimizing Fitness Functions with a Plateau

We consider the expected runtime of non-elitist evolutionary algorithms (EAs), when they are applied to a family of fitness functions $$\text {Plateau} _r$$ with a plateau of second-best fitness in a Hamming ball of radius r around a unique global optimum. On one hand, using the level-based theorems, we obtain polynomial upper bounds on the expected runtime for some modes of non-elitist EA based on unbiased mutation and the bitwise mutation in particular. On the other hand, we show that the EA with fitness proportionate selection is inefficient if the bitwise mutation is used with the standard settings of mutation probability.

Anton V. Eremeev

A Matheuristic for the Drilling Rig Routing Problem

In this paper, we discuss the real-world Split Delivery Vehicle Routing Problem with Time Windows (SDVRPTW) for drilling rig routing in Siberia and the Far East. There is a set of objects (exploration sites) requiring well-drilling work. Each object includes a known number of planned wells and needs to be served within a given time interval. Several drilling rigs can operate at the same object simultaneously, but their number must not exceed the number of wells planned for this object. A rig that has started the work on a well completes it to the end. The objective is to determine such a set of rig routes (including the number of assigned wells for each object) to perform all well-drilling requests, respecting the time windows, that minimizes the total traveling distance. The main difference with traditional SDVRP is that it is the service time that is split, not the demand.We propose a mixed-integer linear programming (MILP) model for this problem. To find high-quality solutions, we design the Variable Neighborhood Search based matheuristic. Exact methods are incorporated into a local search to optimize the distribution of well work among the rigs. Time-window constraints are relaxed, allowing infeasible solutions during the search, and evaluation techniques are applied to treat them. Results of computational experiments for the algorithm and a state-of-the-art MILP solver are discussed.

Igor Kulachenko, Polina Kononova

Locating Facilities Under Deliberate Disruptive Attacks

Facility disruptions or failures may occur due to natural disasters or a deliberate man-made attack. Such an attack is known as interdiction. Recently, facility location problems, addressing intentional strikes against operating facilities and strategies to reduce their impact, have received particular attention. In this paper, we present a new location-interdiction median problem aimed at designing a distribution network which is robust to the worst-case, long-term facility losses. We suppose that there are two players: defender (system designer) and attacker. The defender decides where to locate facilities to minimize the overall cost of supplying the demands of customers. The attacker determines which r facilities to interdict to maximize the cost of serving the customers from the remaining operational facilities. Note that we suppose that the facilities are attacked simultaneously and interdicted facilities become unavailable. We propose bilevel and single-level integer formulations of this problem. For a particular case when the attacker hits a single facility, we develop a fast local search procedure based on implicit enumeration of interdiction strategies. We test our approaches in a series of computational experiments on well-known test problems.

Anton V. Ushakov, Igor Vasilyev

Improving Effectiveness of Neighborhood-Based Algorithms for Optimization of Costly Pseudo-Boolean Black-Box Functions

Optimization of costly black-box functions is hard. Not only we know next to nothing about their nature, we need to calculate their values in as small number of points as possible. The problem is even more pronounced for pseudo-Boolean black-box functions since it is harder to approximate them. For such functions the local search methods where a neighborhood of a point must be traversed are in a particular disadvantage compared to evolutionary strategies. In the paper we propose two heuristics that make use of the search history to prioritize the more promising points from a neighborhood to be processed first. In the experiments involving minimization of an extremely costly pseudo-Boolean black-box function we show that the proposed heuristics significantly improve the performance of a hill climbing algorithm, making it outperform (1+1)-EA with an additional benefit of being more stable.

Oleg Zaikin, Stepan Kochemazov

Operational Research Applications

Frontmatter

Securities and Cash Settlement Framework

The securities settlement process consists in delivering securities from one financial actor to another in exchange for payment in currency. Each business day has a night-time settlement (NTS) period when transactions (exchange of cash and/or security for payment) are settled in batches. Banque de France is inter alia in charge of Mathematical Optimization Module (MOM) for the NTS period which is a component of a large European platform. To reduce the number of failed transactions some additional financial features can be triggered, such as partial settlement of eligible transactions and provision of credit (auto-collateralisation mechanism). MOM must settle as many transactions as possible respecting all business constraints and taking advantage of these financial features. Furthermore, MOM execution time is limited, the data size is large (several hundred thousands of transactions over a billion euro) and the number of transactions and their amounts require high numerical precision. In this work we introduce the necessary financial notions, explain the NTS process and formulate it as a discrete optimisation model. We expose heuristic, mixed integer and linear programming algorithmic approaches used to solve this large-scale problem. We present results obtained on production data and discuss some perspectives.

Ekaterina Alekseeva, Sana Ghariani, Nicolas Wolters

A Stable Alternative to Sinkhorn’s Algorithm for Regularized Optimal Transport

In this paper, we are motivated by two important applications: entropy-regularized optimal transport problem and road or IP traffic demand matrix estimation by entropy model. Both of them include solving a special type of optimization problem with linear equality constraints and objective given as a sum of an entropy regularizer and a linear function. It is known that the state-of-the-art solvers for this problem, which are based on Sinkhorn’s method (also known as RSA or balancing method), can fail to work, when the entropy-regularization parameter is small. We consider the above optimization problem as a particular instance of a general strongly convex optimization problem with linear constraints. We propose a new algorithm to solve this general class of problems. Our approach is based on the transition to the dual problem. First, we introduce a new accelerated gradient method with adaptive choice of gradient’s Lipschitz constant. Then, we apply this method to the dual problem and show, how to reconstruct an approximate solution to the primal problem with provable convergence rate. We prove the rate $$O(1/k^2)$$, k being the iteration counter, both for the absolute value of the primal objective residual and constraints infeasibility. Our method has similar to Sinkhorn’s method complexity of each iteration, but is faster and more stable numerically, when the regularization parameter is small. We illustrate the advantage of our method by numerical experiments for the two mentioned applications. We show that there exists a threshold, such that, when the regularization parameter is smaller than this threshold, our method outperforms the Sinkhorn’s method in terms of computation time.

Pavel Dvurechensky, Alexander Gasnikov, Sergey Omelchenko, Alexander Tiurin

Most Favorable Russell Measures of Efficiency: Properties and Measurement

Conventional radial efficiency measurement models in data envelopment analysis are unable to produce appropriate efficiency scores for production units lying outside the cone generated by the convex hull of the extreme efficient production units. In addition, in the case of production technologies with variable returns to scale, the efficiency scores measured from the input and output sides are usually different. To solve these problems, the Russell measure of efficiency, which takes both the inputs and outputs into account, has been proposed. However, the conventional Russell efficiency is measured under the least favorable conditions, rather than the general custom of measuring under the most favorable ones. This paper develops a model to measure Russell efficiency under the most favorable conditions in two forms, the average and the product. They can be transformed into a second-order cone program and a mixed integer linear program, respectively, so that the solution can be obtained efficiently. A case of Taiwanese commercial banks demonstrates that they are more reliable and representative than the radial measures. Since the most favorable measures are higher than the least favorable measures, and the targets for making improvements are the easiest to reach, they are more acceptable to the production units to be evaluated.

Chiang Kao

Optimization of Gain in Symmetrized Itakura-Saito Discrimination for Pronunciation Learning

This paper considers an assessment and evaluation of the pronunciation quality in computer-aided language learning systems. We propose the novel distortion measure for speech processing by using the gain optimization of the symmetrized Itakura-Saito divergence. This dissimilarity is implemented in a complete algorithm for pronunciation learning and improvement. At its first stage, a user has to achieve a stable pronunciation of all sounds by matching them with sounds of an ideal speaker. At the second stage, the recognition of sounds and their short sequences is carried out to guarantee the distinguishability of learned sounds. The training set may contain not only ideal sounds but the best utterances of a user obtained at the previous step. Finally, the word recognition accuracy is estimated by using deep neural networks fine-tuned on the best words from a user. Experimental study shows that the proposed procedure makes it possible to achieve high efficiency for learning of sounds and their sequences even in the presence of noise in an observed utterance.

Andrey V. Savchenko, Vladimir V. Savchenko, Lyudmila V. Savchenko

Integer Programming Approach to the Data Traffic Paths Recovering Problem

In this paper, we propose a novel approach to recovering path relationships in communication networks. The path relationship is one of the key input data which is necessary for network operation and maintenance. We have a continuous network transformation, upgrades, expansions, service allocations, thus the network physical topology and paths relationship are permanently changing with high frequency. Our approach is aimed at recovering the path relationships through flow information of each arc in the network. Getting the flow information is not a big technical problem and its control is included in the basic toolbox for network monitoring. We consider two scenarios which lead us to integer linear programs. The both of them minimize the flow deviation, where in the first one we look for a directed spanning tree (r-arborescence) and, in the second one—more general origin/destination paths (OD-paths). We propose mixed integer linear programming formulations for both problems. Their feature is that they contain the non-polynomial number of constraints which are considered implicitly by the cutting planes approach. The preliminary computation results showed that the large-scale instances of the first scenario can easily be solved. At the same time, the optimal solutions of second scenario problems can be found only on small- and medium-size instances, which inspires for the further research.

Igor Vasilyev, Dong Zhang, Jie Ren

Backmatter

Weitere Informationen

Premium Partner

    Bildnachweise