Mathematical Optimization Theory and Operations Research: 20th International Conference, MOTOR 2021, Irkutsk, Russia, July 5–10, 2021, Proceedings (Lecture Notes in Computer Science, 12755)

This book constitutes the proceedings of the 20th International Conference on Mathematical Optimization Theory and Operations Research, MOTOR 2021, held in Irkutsk, Russia, in July 2021. The 29 full papers and 1 short paper presented in this volume were carefully reviewed and selected from 102 submissions. Additionally, 2 full invited papers are presented in the volume. The papers are grouped in the following topical sections: ​combinatorial optimization; mathematical programming; bilevel optimization; scheduling problems; game theory and optimal control; operational research and mathematical economics; data analysis. Preface Organization Abstracts of Invited Talks On the Design of Matheuristics that make Use of Learning Optimal Classification and Regression Trees Integer Programming Formulations Based on Exponentially Large Networks: Algorithms and Applications Beyond Heuristic Gradient Descent in Machine Learning Integer Programming and Convolution, with Applications Optimization and Inverse Problems Minimum Sum of Squares Clustering for Big Data – Heuristic Approach Exploiting Structure in Nonsmooth Optimization State-of-the-Art on Rates of Convergence and Cost of Iterations of Augmented Lagrangian Methods Abstracts of Tutorials Reinforcement Learning from the Stochastic Optimization Point of View Equilibrium Traffic Flow Assignment in a Multi-subnet Urban Road Network A Local Search Scheme for the Inequality-Constrained Optimal Control Problem Contents Invited Talks Equilibrium Traffic Flow Assignment in a Multi-subnet Urban Road Network 1 Introduction 2 Multi-subnet Urban Road Network 3 Equilibrium Assignment in a Multi-subnet Road Network 4 Multi-subnet Road Network with Disjoint Routes 5 Toll Road Design in a Simple Topology Road Network 6 Conclusion References A Local Search Scheme for the Inequality-Constrained Optimal Control Problem 1 Introduction 2 Statement of the Problem and Exact Penalization 3 DC Decomposition of Problem (P) 4 Linearized Problem 5 Local Search Scheme 6 Convergence of the LSS1 7 Conclusion References Combinatorial Optimization Serving Rides of Equal Importance for Time-Limited Dial-a-Ride 1 Introduction 2 Preliminaries 2.1 Impossibility Results 2.2 The Segmented Best Path (SBP) Algorithm 3 k-Sequence Algorithm and Upper Bound 3.1 k-Sequence Upper Bound for Large 4 k-Sequence Lower Bound 5 Final Remarks References Rig Routing with Possible Returns and Stochastic Drilling Times 1 Introduction 2 Deterministic Problem Formulation 2.1 Illustrative Example 2.2 MIP Model Based on Event Points 3 Stochastic Model 3.1 Illustrative Example 4 MIP Model Based on VRP Approach 4.1 Stochastic Version 5 Greedy Algorithm for Stochastic Optimization 6 Implementation and the Computer Experiments 6.1 Testing Deterministic Models 6.2 Testing Stochastic Models 6.3 Evaluation of the Greedy Algorithm 7 Conclusions References On Asymptotically Optimal Approach for the Problem of Finding Several Edge-Disjoint Spanning Trees of Given Diameter in an Undirected Graph with Random Edge Weights 1 Introduction 2 Finding Several Edge-Disjoined MSTs with a Given Diameter 3 A Probabilistic Analysis of Algorithm A 4 Conclusion References An FPTAS for the -Modular Multidimensional Knapsack Problem 1 Introduction 1.1 Basic Definitions and Notations 1.2 Description of Results and Related Work 2 Proof of the Theorem 1 2.1 Greedy Algorithm 2.2 Dynamic Programming by Costs 2.3 Putting Things Together 3 Proof of Theorem 2 3.1 First Complexity Bound 3.2 Second Complexity Bound 3.3 Third Complexity Bound References A Column Generation Based Heuristic for a Temporal Bin Packing Problem 1 Introduction 2 Model Description 3 Lower Bounds 4 Upper Bounds 5 Computational Experiments 6 Conclusions References On Some Variants of the Merging Variables Based (1+1)-Evolutionary Algorithm with Application to MaxSAT Problem 1 Introduction 2 Preliminaries 3 (1+1)-MVEA and Its Theoretical Properties 4 On One Special Class of MaxSAT Problem 5 Computational Experiments 6 Conclusion References Mathematical Programming An Approach for Simultaneous Finding of Multiple Efficient Decisions in Multi-objective Optimization Problems 1 Introduction 2 Problem Statement 3 Reducing the Problem of Multi-objective Optimization to the Problems of One-Dimensional Global Optimization 3.1 Scalarization of Multiple Objective Functions 3.2 Dimensionality Reduction 3.3 Solving the One-Dimensional Reduced Optimization Problem 4 An Approach for Simultaneous Finding of Multiple Efficient Decisions in Multi-objective Optimization Problems 4.1 The Need to Solve Multiple Global Optimization Problems 4.2 Step-by-Step Solution of a Set of Global Optimization Problems 4.3 Simultaneous Solution of a Set of Global Optimization Problems 5 Results of Numerical Experiments References One-Point Gradient-Free Methods for Smooth and Non-smooth Saddle-Point Problems 1 Introduction 1.1 Related Works 1.2 Our Contribution 2 Preliminaries 2.1 Notation 2.2 Settings and Assumptions 3 Theoretical Results 3.1 Non-smooth Case 3.2 Smooth Case 3.3 Higher-Order Smooth Case 4 Experiments References Convex Optimization with Inexact Gradients in Hilbert Space and Applications to Elliptic Inverse Problems 1 Introduction 2 Primal Approaches 2.1 Gradient Descent 3 Dual Approaches 4 Stopping Rule for STM 5 Numerical Results References On the Computational Efficiency of Catalyst Accelerated Coordinate Descent 1 Introduction 2 Accelerated Meta-algorithm and Coordinate Descent 2.1 Theoretical Guarantees 2.2 Numerical Experiments 2.3 Application to Optimization of Markov Decision Processes 3 Conclusion References Duality Gap Estimates for a Class of Greedy Optimization Algorithms in Banach Spaces 1 Introduction 2 Greedy Optimization Algorithms in Banach Spaces 3 Duality Gap Estimates for Greedy Approximation in Banach Spaces 3.1 Duality Gap 4 Empirical Results 5 Conclusion References A Penalty Approach to Linear Programs with Many Two-Sided Constraints 1 Introduction 2 Linear Programs with Two-Sided Constraints and Their Equivalence to a Non-smooth Optimization Problem 3 The r()-Algorithm with Adaptive Steps 4 Computational Experiments 5 Conclusion References Bilevel Optimization Sample Approximations of Bilevel Stochastic Programming Problems with Probabilistic and Quantile Criteria 1 Introduction 2 Statement 3 Existence of Optimal Solution 4 Sample Approximations 5 Convergence of the Sample Approximations 6 Conclusion References On Solving Bilevel Optimization Problems with a Nonconvex Lower Level: The Case of a Bimatrix Game 1 Introduction 2 Non-normalized Bimatrix Game and Its Properties 3 Bilevel Problem Formulation and Transformation 4 D.C. Representation 5 Exact Penalty and Global Optimality Conditions 6 Local Search Scheme 7 Concluding Remarks References Scheduling Problems Two-Machine Routing Open Shop: How Long Is the Optimal Makespan? 1 Introduction 2 Instance Transformations 3 The Main Result 4 Conclusions References Minimizing Total Completion Time in Multiprocessor Job Systems with Energy Constraint 1 Introduction 2 Previous Research 3 Rigid Jobs 3.1 NP-Hardness 3.2 Approximation Algorithm 4 Moldable Jobs 5 Single Mode Multiprocessor Jobs 5.1 NP-Hardness 5.2 Two-Processor Instances References Maximising the Total Weight of On-Time Jobs on Parallel Machines Subject to a Conflict Graph 1 Introduction 2 Related Work 3 Scheduling UET Jobs 3.1 Polynomial-Time Algorithm for m=2 3.2 Approximation Algorithms for m > 2 4 Scheduling Jobs with Arbitrary Processing Times 4.1 Integer Linear Programming Formulations 4.2 Heuristic Algorithms 5 Computational Experiments 6 Conclusions References Game Theory and Optimal Control Optimal Boundary Control of String Vibrations with Given Shape of Deflection at a Certain Moment of Time 1 Introduction 2 Statement of the Problem and Its Reduction to a Problem with Zero Boundary Conditions 3 Reduction of the Solution of a Problem with Zero Boundary Conditions to the Problem of Moments 4 The Problem Solution 5 Constructing the Solution for Case n = 1 6 Numerical Experiment 7 Conclusion References A Discrete Game Problem with a Non-convex Terminal Set and a Possible Breakdown in Dynamics 1 Introduction 2 Problem Statement 3 Necessary and Sufficient Conditions of Termination 4 Problem with an Unknown Moment of Change in the Dynamics of the First Player 5 Example 6 Conclusion References Altruistic-Like Equilibrium in a Differential Game of Renewable Resource Extraction 1 Introduction 2 The Model 2.1 Equilibrium Concepts 3 Altruistic-Like Equilibria in a Differential Game of Renewable Resource Extraction 4 Numerical Simulations 5 Conclusion References Multicriteria Dynamic Games with Random Horizon 1 Introduction 2 Dynamic Multicriteria Game with Random Horizon 2.1 Multicriteria Nash Equilibrium 2.2 Multicriteria Cooperative Equilibrium 2.3 Time-Consistent Payoff Distribution Procedure 3 Dynamic Bi-criteria Resource Management Problem with Random Horizon 3.1 Multicriteria Nash Equilibrium 3.2 Cooperative Equilibrium 4 Conclusions References Feedback Maximum Principle for a Class of Linear Continuity Equations Inspired by Optimal Impulsive Control 1 Introduction 1.1 Notations 1.2 Regularity Hypotheses 2 Pontryagin's Maximum Principle 3 Feedback Maximum Principle 3.1 ``Exact'' Increment Formula of the Cost Functional: An Informal Discussion 3.2 Ensemble-Feedback Controls and Sampling Solutions 3.3 Integral Constraint on Control 3.4 Formulation of the Feedback Maximum Principle 3.5 Example: Discarding a PMP Extremal by FMP 3.6 Concluding Remark: FMP as Numerical Method References Nonlocal Optimization Methods for Quadratic Control Systems with Terminal Constraints 1 Improving Control Problem 2 Iterative Methods 3 Example References Identification of the Thermal Conductivity Coefficient of a Substance from a Temperature Field in a Three-Dimensional Domain 1 Introduction 2 Formulation of the Problem 3 Numerical Solution of the Inverse Coefficient Problem 3.1 The First Series of Calculations 3.2 The Second Series of Calculations 3.3 The Third Series of Calculations 4 Conclusion References Operational Research and Mathematical Economics Dixit-Stiglitz-Krugman Model with Investments in R&D 1 Introduction 2 Model 2.1 Consumers 2.2 Producers 2.3 Symmetric Case 2.4 Symmetric Equilibrium 3 The Local Comparative Statics w.r.t. 3.1 Autarky 4 Proofs 4.1 Proof of Proposition 1 4.2 Proof of Proposition 2 5 Conclusion References On Contractual Approach for Non-convex Production Economies 1 Introduction 2 Non-convex Technologies in Arrow–Debreu Economies 2.1 Production Economies 2.2 Pareto Frontier and Tangent Cones 3 MCP-Equilibrium and Contracts in Economies with Non-convex Technologies 3.1 Marginal Cost Pricing 3.2 Contracts in Non-convex Arrow–Debreu Model References Optimization of Regulation and Infrastructure of the Electricity Market 1 Introduction 2 Spot Market Model and Formulation of Optimization Problem 3 Optimal Control of the Storage at the Local Market 4 Optimization of the Storage Parameters 5 The Optimal Control for the Stochastic Problem 6 Conclusion References Data Analysis Weakly Supervised Regression Using Manifold Regularization and Low-Rank Matrix Representation 1 Introduction 2 Problem Description and Notation 3 Manifold Regularization 4 Proposed Method 4.1 Objective Functional 4.2 Optimal Solution 4.3 Low-Rank Similarity Matrix Representation 4.4 Co-association Matrix of Cluster Ensemble 4.5 WSR-LRCM Algorithm 5 Monte-Carlo Experiments 5.1 First Example with Artificial Data 5.2 Second Example with Real Data References K-Means Clustering via a Nonconvex Optimization Approach 1 Introduction 2 Problem Statement 3 DC Representations of the Objective Function 4 Local Search 5 Optimality Conditions and the Global Search Scheme 6 Computational Experiments 7 Conclusion References Machine Learning Algorithms of Relaxation Subgradient Method with Space Extension 1 Introduction 2 A Space Extension Method for Solving Systems of Inequalities on Separable Sets 3 Minimization Algorithm 4 Computational Experiment 5 Conclusion References Author Index