This supplementary volume contains the proceedings of the 9th conference on Discrete Optimization and Operations Research and scienti c school on Modern Optimization and Equilibrium, held in Vladivostok, Russia, during September 19 - 23, 2016. It was organized by the Far Eastern Federal University, Sobolev Institute of Mathematics, Krasovsky Institute of Mathematics and Mechanics, Novosibirsk State University, and the Higher School of Economics in Nizhny Novgorod. Previous conferences took place at the Sobolev Institute of Mathematics, Novosibirsk, in 1996, 1998, 2000, 2002, and 2004. The 6th conference was held in the Russian Far East in a picturesque on the shore of the Japanese Sea near Vladivostok in 2007. The 7th one, in 2010, was held in the Mountain Altay. The 8th event took place in Novosibirsk again. This event is a part of series of regular international conferences on optimization and operations research that covers a wide range of topics in mathematical programming and its applications, integer programming and polyhedral combinatorics, bi-level programming and multi-criteria optimization, optimization problems in machine learning and data mining, discrete optimization in scheduling, routing, bin packing, locations, and optimization problems on graphs, computational complexity, and polynomial time approximation. The main purpose of the conference and scienti c school is to provide a forum where scientists and young researchers can exchange ideas, identify promising directions for research and application domains, and foster new collaborations. In response to the call for papers, we received 181 submissions. Papers included in this volume were carefully selected by the Program Committee on the basis of reports from two or more reviewers from 17 countries such as Belarus, Belgium, France, Germany, India, Israel, Italy, Kazakhstan, Netherlands, Russian Federation, Spain, Sweden, Taiwan, Turkey, Ukraine, United Kingdom, United States. Only 82 submissions were selected for inclusion in this volume. The conference also featured ten invited talks by the following eminent speakers:
ii { Athanasios Migdalas from the Lulea University of Technology, Sweden; Title of the talk: Location modeling in the presence of rm and customer competition. { Vadim Shmyrev from the Sobolev Institute of Mathematics, Russia; Title of the talk: Iterative approach for piecewise linear exchange model ; { Alexandr Kononov from the Sobolev Institute of Mathematics, Russia; Title of the talk: Short survey on minimization graph correlation clustering ; and eight tutorials: { Adil Erzin from the Sobolev Institute of Mathematics, Russia; Title of the talk: Computational geometry and combinatorial optimization problems in the context of wireless sensor networks optimization ; { Alexandr Kononov from the Sobolev Institute of Mathematics, Russia; Title of the talk: How to design approximation schemes for intractable optimization problems ; { Yury Kochetov from the Sobolev Institute of Mathematics, Russia; Title of the talk: Discrete Location Problems; { Nenad Mladenovic from the University of Valenciennes, France; Title of the talk:
Developing variable neighborhood and formulation space search procedures; { Michael Khachay from the Krasovsky Institute of Mathematics and Mechanics, Russia; Title of the talk: Effective algorithms for some actual generalizations of geometrical traveling salesman problems; { Oleg Khamisov from the Melentiev Institute of Energy Systems, Russia; Title of the talk: Modeling of the energy markets with network restrictions; { Michael Batsyn from the National Research University Higher School of Economics,
Russia; Title of the talk: Optimization problems in the transportation logistics; { Alexandr Strekalovsky from the Matrosov Institute for System Dynamics and Control Theory, Russia; Title of the talk: Theory and methods of nonlinear optimization.
We thank all Program Committee members and external reviewers for their cooperation. We also thank the Organizing Committee members and our sponsors: the Russian Foundation for Basic Research, the Far Eastern Federal University, Novosibirsk State University, the Laboratory of Algorithms and Technologies for Networks Analysis, the Higher School of Economics in Nizhny Novgorod for supporting our project. September 2016 Alexandr Kononov,
Igor Bykadorov, Oleg Khamisov,
Ivan Davydov,
Polina Kononova
Far Eastern Federal University Sobolev Institute of Mathematics Novosibirsk State University Higher School of Economics, Nizhny Novgorod Krasovsky Institute of Mathematics and Mechanics
Evgeni Nurminski Vladimir Beresnev Panos Pardalos
Ekaterina Alekseeva Edilkhan Amirgaliev Oleg Burdakov Igor Bykadorov Emilio Carrizosa Yair Censor Ivan Davydov Vladimir Deineko Stefan Dempe Anton Eremeev Adil Erzin Yury Evtushenko Edward Gimadi Alexandr Grigoriev Florian Jaehn Josef Kallrath Valery Kalyagin Alexander Kelmanov Michael Khachay Oleg Khamisov Andrey Kibzun Yury Kochetov Alexander Kolokolov Alexander Kononov Mikhail Kovalev Nikolay Kuzyurin Far Eastern Federal University, Russia Sobolev Institute of Mathematics, Russia University of Florida, USA Sobolev Institute of Mathematics, Russia Suleyman Demirel University, Kazakhstan Linkoping University, Sweden Sobolev Institute of Mathematics, Russia Universidad de Sevilla, Spain University of Haifa, Israel Sobolev Institute of Mathematics, Russia The University of Warwick, UK TU Bergakademie Freiberg, Germany Sobolev Institute of Mathematics, Russia Sobolev Institute of Mathematics, Russia Dorodnicyn Computing Centre, Russia Sobolev Institute of Mathematics, Russia Maastricht University, The Netherlands Universitat Augsburg, Germany TU Darmstadt, Germany Higher School of Economics, Russia Sobolev Institute of Mathematics, Russia Krasovsky Institute of Mathematics and Mechanics, Russia Melentiev Energy Systems Institute, Russia Moscow Aviation Institute, Russia Sobolev Institute of Mathematics, Russia Sobolev Institute of Mathematics, Russia Sobolev Institute of Mathematics, Russia Belarusian State University, Belarus Institute for System Programming, Russia iv Bertrand Lin Bertrand Mareschal Athanasios Migdalas Nenad Mladenovic Urfat Nuriyev Alexandr Plyasunov Artem Pyatkin Soumyendu Raha Konstantin Rudakov Yaroslav Sergeev Sergey Sevastianov Vadim Shmyrev Petro Stetsuk Alexander Strekalovsky Maxim Sviridenko El-Ghazali Talbi Yury Zhuravlev
National Chiao Tung University, Taiwan Universite Libre de Bruxelles, Belgium Lulea University of Technology, Sweden University of Valenciennes, France Ege University, Turkey Sobolev Institute of Mathematics, Russia Sobolev Institute of Mathematics, Russia Indian Institute of Science, India Dorodnicyn Computing Centre, Russia Universita della Calabria, Italy Sobolev Institute of Mathematics, Russia Sobolev Institute of Mathematics, Russia Institute of Cybernetics, Ukraina Matrosov Institute for System Control Theory, Russia Yahoo, USA University of Lille, CNRS, INRIA, France Dorodnicyn Computing Centre, Russia
Dynamics and Natalia Shamry Yury Kochetov Mikhail Khachay Timur Medvedev Evgeniya Vorontsova Nina Kochetova Polina Kononova Andrey Velichko
Far Eastern Federal University, Russia Sobolev Institute of Mathematics, Russia Krasovsky Institute of Mathematics and Mechanics, Russia Higher School of Economics, Russia Far Eastern Federal University, Russia Sobolev Institute of Mathematics, Russia Sobolev Institute of Mathematics, Russia Far Eastern Federal University, Russia Discrete Optimization Models for Solving Complex Products Design Problems : : 49 Alexander Kolokolov, Alexandra Artemova, Alexander Adelshin and Irina Kan On the m-clustering Problem on the Line : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 57
Anna Kurochkina and Alexander Kurochkin AOE-Trails Constructing for a Plane Connected 4-Regular Graph : : : : : : : : : : : : : 62
Tatyana Makarovskikh and Anatoly Panyukov Binary Cut-and- Branch Method for Solving Linear Programming Problems with Boolean Variables : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 72
Yurii A Mezentsev Pq-Konig Extended Forests and Cycles : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 86
Dmitry Mokeev Reduction of the Graph Isomorphism Problem to Equality Checking of n-variables Polynomials and the Algorithms that Use the Reduction : : : : : : : : : : : 96
Alexander Prolubnikov Separation Problem for k-parashuties : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 109 Inna Urazova and Ruslan Simanchev About Local Optimum of the Weber Problem on Line with Forbidden Gaps : : : : 115
Gennady Zabudsky and Natalia Veremchuk
Optimization and Discretization in 2D Problems of Electromagnetic Invisible Cloaking : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 125
Gennady Alekseev, Aleksey Lobanov and Yuliya Spivak Predictive Model's Development Based on the Wavelet Analysis Technique : : : : : 138
Natalia Bakhtadze, Valery E. Pyatetsky and Ekaterina Sakrutina Optimization in Nonlinear Models of Mass Transfer : : : : : : : : : : : : : : : : : : : : : : : : : 152
Roman Brizitskii and Zhanna Saritskaya Optimal Control Algorithm for Complex Heat Transfer Model : : : : : : : : : : : : : : : : 165
Alexander Chebotarev, Gleb Grenkin and Andrey Kovtanyuk Optimization Iterative Procedure for Radiative-Conductive Heat Transfer Model 178
Alexander Chebotarev, Andrey Kovtanyuk and Veronika Pestretsova A Projection-Type Algorithm for Linear Programming Using Line and Zonotope Intersection : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 185
Max Demenkov Matrix correction minimal with respect to the Euclidean norm of a pair of dual linear programming problems : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 196 Vladimir Erohin, Alexander Krasnikov, Vladimir Volkov and Mikhail Khvostov Optimal Control for Radiative Heat Transfer Model with Monotonic Cost Functionals : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 210
Gleb Grenkin and Alexander Chebotarev Explicit univariate global optimization with piecewise linear support functions : : 218
Oleg Khamisov Modi ed Simplex Imbeddings Method in Convex Non-differentiable Optimization 226
Anton Kolosnitcyn Stochastic Optimal Growth Model with S-Shaped Utility Function : : : : : : : : : : : : 234
Sergei Mironov, Alexey Faizliev, Sergei Sidorov and Alexandre Gudkov Solution of the Contact Elasticity Problem Based on an Iterative Proximal Regularization Method for the Modi ed Lagrangian Functional : : : : : : : : : : : : : : : 242
Robert Namm and George Tsoy Parallel Newton Methods for Numerical Analysis of Infeasible Linear Programming Problems with Block-Angular Structure of Constraints : : : : : : : : : : 253 Leonid D. Popov On the Accuracy of Statistical Estimations of SAT Partitionings Effectiveness in Application to Discrete Functions Inversion Problems : : : : : : : : : : : : : : : : : : : : : 261
Alexander Semenov and Oleg Zaikin Dual Greedy Algorithm for Conic Optimization Problem : : : : : : : : : : : : : : : : : : : : : 276
Sergei Sidorov, Sergei Mironov and Michael Pleshakov Convergence of Solutions of an Optimal Control Problem for SP1 and Rosseland Approximations : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 284
Andrei Sushchenko, Tatiana Park, Rene Pinnau and Oliver Tse Discrete Optimization of Unsteady Fluid Flows : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 293
Dmitry Tereshko Modi ed Duality Method for Obstacle Problem : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 303
Elina Vikhtenko A Variant of the Multi-Step Bundle Method : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 315
Rashid Yarullin A Minimization Algorithm with Approximation of an Epigraph of the Objective Function and a Constraint Set : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 321
Igor Zabotin, Oksana Shulgina and Rashid Yarullin
Approximating Two-Machine Flow Shop Problem with Delays when Processing Times Depend Only on Machines : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 325
Alexander Ageev and Alexei Baburin Single Machine Inserted Idle Time Scheduling with Release Times and Due Dates 336
Natalia Grigoreva Scheduling of Two Parallel Machines with Linear Decreasing Time Slot Costs to Minimize Total Weighted Completion Time : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 344
Alexander Kononov and Irina Lushchakova Optima Localization in Scheduling Multi-Processor Jobs : : : : : : : : : : : : : : : : : : : : : 350
Alexander Gordeev, Alexander Kononov and Polina Kononova
Using Graph Model to Analyze the Topological Vulnerability of Transport Infrastructure : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 358
Maxim Anop Adaptive Landmark Selection when Routing in Time-Depended Network : : : : : : : 367 Valentina Bykova and Alexander Soldatenko Modeling of Urban Traffic Flows Using the Concept of Multilayer Graph by Methods of Game Theory : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 373
Anastasiya Ivanova and Alexey Kovalenko Software System for Interactive Simulation of Interregional Trade : : : : : : : : : : : : : 383
Andrey Velichko, Valeriya Gribova and Leonid Fedorishchev Interregional Transportation Modeling for the Far East of Russia Macro-region : 394
Andrey Velichko The General Multimodal Network Equilibrium Problem with Elastic Balanced Demand : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 404
Natalia Shamray
Robust Image Watermarking Technique Based on Genetic Algorithm Optimization and Even Odd Modulation : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 415 Alexander Bahrushin, Galina Bahrushina, Ruslan Bazhenov, Kiseon Kim and Rudolf Tsoy Runtime Analysis of Genetic Algorithms with Very High Selection Pressure : : : : 428
Anton Eremeev Combinations of the Greedy Heuristic Method for Clustering Problems and Local Search Algorithms : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 440
Lev Kazakovtsev and Alexander Antamoshkin Genetic Local Search for the Servers Load Balancing Problem : : : : : : : : : : : : : : : : 453
Yuri Kochetov, Artem Panin and Alexander Plyasunov The Band Collocation Problem: a Library of Problems and a Metaheuristic Approach : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 464
Hakan Kutucu, Arif Gursoy, Mehmet Kurt and Urfat Nuriyev On a Local Search for Hexamatrix Games : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 477
Andrei Orlov and Alexander Strekalovsky
Cluster Ensemble with Averaged Co-Association Matrix Maximizing the Expected Margin : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 489
Vladimir Berikov An Exact Pseudopolynomial Algorithm for a Problem of Finding a Family of Disjoint Subsets : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 501 Alexandr Galashov and Alexander Kelmanov A Local Search for a Graph Correlation Clustering : : : : : : : : : : : : : : : : : : : : : : : : : : 510
Victor Il'Ev and Anna Navrotskaya
Markov Processes in Modeling Life Cycle of Economic Clusters : : : : : : : : : : : : : : : 545
Galina Boush, Vitaly Shamis, Oksana Kulikova and Svetlana Neiman Generalized Mirror Descents with Non-Convex Potential Functions in Atomic Congestion Games : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 558
Po-An Chen An Investigation of a Bilevel Energy Market Model : : : : : : : : : : : : : : : : : : : : : : : : : : 563
Nadezhda Dresvyanskaya The Curvilinear Search Algorithm for Solving Three-Person Game : : : : : : : : : : : : 574
Rentsen Enkhbat, Natsagdorj Tungalag, Aleksander Gornov and Anton Anikin Primal-Dual Method for Searching Equilibrium in Hierarchical Congestion Population Games : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 584 Pavel Dvurechensky, Alexander Gasnikov, Evgenia Gasnikova, Sergey Matsievsky, Anton Rodomanov and Inna Usik On the Equivalence of Optimality Principles in the Two-Criteria Problem of the Investment Portfolio Choice : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 596
Victor Gorelik and Tatiana Zolotova Dual Model of Power Market with Generation and Line Capacity Expansion : : : : 606
Svetlana Gakh One Method for Constructing Pareto-Optimal Nash Equilibriums : : : : : : : : : : : : : 618
Konstantin Kudryavtsev, Vladislav Zhukovskiy and Irina Stabulit Public-Private Partnership Models for the Russian Mineral Resource Complex : : 624
Sergey Lavlinskii Algorithm Realization of a Stochastic Network Resource Mega-Project Management Model : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 638 Nina Plyaskina On Strong Accessibility of the Core of TU Cooperative Game : : : : : : : : : : : : : : : : 643
Valery Vasilev On One Multicriteria Optimal Control Problem of Economic Growth : : : : : : : : : : 656
Alexey Zakharov
Numerical Simulation of Chemical Enhanced Oil Recovery Processes : : : : : : : : : : 664
Bakhbergen Bekbauov, Abdumauvlen Berdyshev and Zharasbek Baishemirov An Empirical Study of Concern for Privacy on Providing Health Information in the EMR Context : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 677
Kuei Fen Chen, Hsin-Ginn Hwang, Ming-Ling Sher and Hui-Ting Lin An Application of Speed Gradient Method to Neural Network Control for Underwater Robot : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 689
Alexander Dyda, Dmitry Oskin and Pavel Dyda Cost-Effective Strip Covering with Identical Directed Sensors : : : : : : : : : : : : : : : : : 701
Adil Erzin On Formulation and Software Implementation of Some Financial Management and Barter Transactions Problems : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 713
Edward Gimadi, Evgenii Goncharov and Valentin Leonov Application of Active Set Method for Soft Sensor Model Identi cation of Crude Oil Distillation Process : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 723
Anton Goncharov and Andrei Torgashov Malmquist Productivity Index for Network Production Systems : : : : : : : : : : : : : : : 733
Chiang Kao Methods Assessment the Probability Density of Discrete Signals in Telecommunications : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 745
Yuriy Kropotov and Aleksey Belov Modeling the Goodness-of-Fit Test Based on the Interval Estimation of the Probability Distribution Function : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 755
Evgeny Kuleshov, Konstantin Petrov and Tatiana Kirillova Optimizing the Properties of Tool Materials by Means of the Mathematical Modeling of their Fracture Processes : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 764
Elena Mokritskaya Selection of the Optimal Parameters of the Process for Thermal Laser Treatment of Metals for Creating the Molten Pool with a Required Depth : : : : : : 768 Marina V. Polonik and Olga V. Dudko