ABSTRACT. In this paper, we consider two types of problems that have some similarity in their structure, namely, min-min problems and min-max saddle-point problems. Our approach is based on considering the outer minimization problem as a minimization problem with an inexact oracle. This inexact oracle is calculated via the inexact solution of the inner problem, which is either minimization or a maximization problem. Our main assumptions are that the problem is smooth and the available oracle is mixed: it is only possible to evaluate the gradient w.r.t. the outer block of variables which corresponds to the outer minimization problem, whereas for the inner problem only zeroth-order oracle is available. To solve the inner problem we use accelerated gradient-free method with zeroth-order oracle. To solve the outer problem we use either an inexact variant of Vaydya's cutting-plane method or a variant of accelerated gradient method. As a result, we propose a framework that leads to non-asymptotic complexity bounds for both min-min and min-max problems. Moreover, we estimate separately the number of first- and zeroth-order oracle calls which are sufficient to reach any desired accuracy.

ABSTRACT. In this paper we give some observation of applying modern optimization methods for functionals describing digital predistortion (DPD) of signals with orthogonal frequency division multiplexing (OFDM) modulation. The DPD functionals modeling the behavior of power amplifier are based on A Vinner-Hammerstain model. To achieve better DPD performance we consider state of the art optimization methods and strategies, which are used to optimize modern neural networks: various start initializations, which allow to get more global optimization minimum; different modern methods, which are applied for optimization of non-convex functions (Neural Net-works); different methodologies/techniques of learning rate changing, which allow to change optimization step and get high-performance of DPD model. To obtain the results of this research, we use different DPD functions and signals with OFDM modulation. To compare the performance of functions we use Normalized mean squared error (NMSE) as a criterion of checking results. Through this study, we selected best optimization methods, strategies of learning rate changing and start initialization, which increase the performance of the investigated models.

ABSTRACT. The intersectoral balance method is a tool for medium-term economic analysis. It is used to identify industries that act as drivers of economic growth, to analyze the mechanisms of shock propagation, and to assess the consequences of economic sanctions. The classical version of the method, based on the model of W. Leontief, is built on the hypothesis of the constancy of the norms of output costs. Since the 90-ies of XX century, the changing nature of economic growth, globalization of the world economy, priority development of the service sector have adversely affected the implementation of the basic hypothesis Leontief models and have stimulated the development of models that account for substitution of production factors. The paper develops a mathematical apparatus for medium-term analysis based on models of inter-industry balance with production functions from the class of functions with constant elasticity of substitution (CES). The developed approach is based on the use of the Yang transform to construct a dual convex programming problem for calculating Lagrange multipliers to inter-industry balance ratios that model price indices for industry products. The paper also sets the task of model identification. The method is tested on the Russian statistical data.

ABSTRACT. In the paper, the problem of aircraft flows merging is considered, which arises at the point of joining two or more air routes. It is assumed that the aircraft may be of different types. This results in their different parameters: safety interval between them, different intervals for varying the arrival instants, different costs for maneuvering, etc. The problem has two subtasks: the choice of the optimal order of the aircraft in the gathered queue and the assignment of the optimal arrival instants for the chosen order. Both subtasks are solved simultaneously by means of mixed-integer programming methods. Numerical simulation results are given for model examples.

ABSTRACT. In Two-Bar Charts Packing Problem, it is necessary to pack the set of bar charts consisting of two bars each into the unit-height strip of minimal length. When packing, it is allowed to move bars vertically within the strip, but it is forbidden to change the order and separate the chart's bars. Earlier, for this problem, which is a generalization of the Bin Packing Problem, several approximation algorithms with guaranteed estimates were proposed. However, these algorithms build a near-optimal solution. This fact inspired us to conduct a numerical experiment in which the approximate solutions are compared to each other and with the optimal one. We build the optimal solution by the CPLEX package by solving the BLP, which we have proposed in our previous papers. The results of the simulation make up the content of this paper.

ABSTRACT. In Two-Bar Charts Packing Problem, it is necessary to pack the set of bar charts consisting of two bars each into the unit-height strip of minimal length. When packing, it is allowed to move bars vertically within the strip, but it is forbidden to change the order and separate the chart's bars. Earlier, for this problem, which is a generalization of the Bin Packing Problem, several approximation algorithms with guaranteed estimates were proposed. However, these algorithms build a near-optimal solution. This fact inspired us to conduct a numerical experiment in which the approximate solutions are compared to each other and with the optimal one. We build the optimal solution by the CPLEX package by solving the BLP, which we have proposed in our previous papers. The results of the simulation make up the content of this paper.

ABSTRACT. The problem of single machine with equal length of jobs and the preemption is considered. The optimization criterion is the weighted average time completion of jobs. The properties of the problem are investigated. An algorithm for constructing a finite set of schedules containing an optimal solution is proposed.

ABSTRACT. The continuous p-median problem is a classical global optimization model used both for finding optimal locations of facilities on a plane, and as a clustering model. The problem is to find p points (medians) such that the sum of the distances from known demand points to the nearest median is minimal. Such a clustering model is less sensitive to "outliers" (separately located demand points that are not included in any cluster), compared with models such as k-means. This feature is important for such clustering problems as groupping highly-reliable electronic devices into homogeneous production batches. Many heuristic approaches were proposed for this NP-hard problem. The genetic algorithms with a greedy agglomerative crossover operator are some of the most accurate heuristic methods. However, such a crossover operator is computationally expensive which limits its applicability for large-scale problems. A parameter of this operator (parameter r) determinates the efficiency of the whole genetic algorithm. Moreover, the optimal value of this parameter is hardly predictable based on numerical parameters of the problem such as the numbers of demand points and medians. We investigate its influence on the result of the algorithm, and also propose a simple procedure for adjusting the algorithm parameter. The advantages of the self-adjusting algorithm are shown for problems with a data volume of up to 2,000,000 objects.

ABSTRACT. We consider the following problem of a gas production company. There is a gas-bearing region with natural gas fields. The produced gas must be delivered to the main pipelines by laying a network of pipelines from fields to main pipelines (supply route). Before the gas enters the main pipeline, it must be processed in a gas treatment unit. Gas treatment units have to be located in some fields. The goal is to minimize the total cost of laying pipelines and placing gas treatment units.

We propose a mathematical model of this problem in the form of a mixed-integer linear programming problem. Based on this mathematical model, we present the results of the free solver PULP on real data from a well-known gas company. Also, we present a hybrid metaheuristic algorithm based on the local search, variable neighborhood search, and greedy algorithm. The main idea of the hybrid algorithm is the separation of gas processing and supply. First of all, we define the gas processing locations. Then we build the supply tree. The use of metaheuristics can significantly reduce the complexity of each stage.

The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. 0314-2019-0014)

ABSTRACT. We study a monopolistic competition model in the open economy case. The utility of consumers is additively separable. The producers can choose the technology (R&D) endogenously. We examine the local comparative statics of market equilibrium with respect to transport cots (of iceberg type). Early, we find the following preliminary result: increasing transport cost has opposite impacts on the mass of firms and productivity. In the present paper, we study, mainly, the local comparative statics w.r.t. transport costs for the case of autarky (the very big transport costs). For the case of linear production costs, the known (and counter-intuitive!) result is that the social welfare increases near autarky. We generalize this result for the model with investments in R&D, this is the main result of the paper.

ABSTRACT. We study the market equilibrium in international trade monopolistic competition model a'la Dixit-Stiglitz-Krugman with homogeneous firms. The utility of consumers is additively separable. 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. Earlier, for the case of international trade between two countries, we examined the local symmetric comparative statics of equilibrium variables with respect to transport costs of iceberg type. In the present paper, we develop the previous results in the case of international trade between more than two countries. The main attention we pay to the cases of free trade (the very small transport costs) and autarky (the very big transport costs). For autarky, we consider the different cases of pre-autarky.

ABSTRACT. We study the monopolistic competition models a'la Dixit-Stiglitz with vertical market interaction of several manufacturers, a retailer, and consumers. The utility is Ottaviano-Tabuchi-Thisse type. The cost functions of manufacturers and of retailers are linear. Earlier we provided Stackelberg equilibrium under the leadership of retailer; study the consequences, on social welfare and the consumer surplus. In the present paper, we develop the model by introducing the entrance fee for manufacturers.

ABSTRACT. We solve a weakly supervised regression problem. Under ''weakly" we understand that for some training points the labels are known, for some unknown and for others uncertain due to presence of random noise or other reasons such as lack of resources. The solution process requires to optimize a certain objective function (the loss function), which combines manifold regularization and low-rank matrix decomposition techniques. These low-rank approximations allow us to speed up all matrix calculations and reduce storage requirements. This is especially crucial for large datasets. Ensemble clustering is used for obtaining the co-association matrix which we consider as the similarity matrix. Utilization of these techniques allows us to increase the quality and stability of the solution. In the numerical section, we study the proposed method on artificial data sets using Monte-Carlo modeling.

ABSTRACT. In relaxation subgradient minimization methods, a descent direction is constructed based on information about the subgradients obtained at the iteration. This direction forms an obtuse angle with all subgradients in the neighborhood of the current minimum, and minimization along this direction allows us to go beyond this neighborhood and eliminate the method looping effects. Algorithms of this type have a broad practical use due to their fast convergence and the ability to minimize non-convex functions, for example, when estimating the parameters of mathematical models with non-smooth regularization. The idea of optimizing the space extension parameter choice in accordance with the current state of the search can be applied to create new algorithms.

We formulate the problem of the descent direction search as a problem of solving systems of inequalities, and propose an algorithm with space extension for solving them. This algorithm is close to the iterative least squares method. With relatively low computational costs per iteration, the proposed algorithm has a high convergence rate and is efficient in the absence of convexity and smoothness. Therefore, in terms of applicability and computational efficiency, it complements the well-known minimization methods based on quadratic or piecewise linear models.

In addition, we present an example of the implementation of such an algorithm, which confirms the effectiveness of theoretical constructions. Theoretical analysis of the learning algorithm with space extension allowed us to identify the components of the algorithm and replace them, which enables us, depending on the situation, to use increased values of the extension parameter. On this basis, a theoretically new learning method with space extension and the corresponding subgradient method for solving problems of minimizing non-smooth functions were developed and substantiated.

Our computational experiment confirms the efficiency of the proposed relaxation subgradient method.

ABSTRACT. Clustering is one of the basic tasks in machine learning and data mining. Euclidean minimum-sum-of-squares clustering problem is probably the most common clustering model. It consists in finding $k$ cluster centers or representatives so as the sum of squared Euclidean distances from a set of points and their closest centers is minimized. The problem is known to be non-convex and NP-hard even in the planner case. In this paper, we propose a new DC programming approach to the problem. First, we cast the original non-convex problem as a continuous optimization problem with the objective function represented as a DC function. We then devise a solution algorithm, resting upon the global optimality conditions and global search scheme for DC minimization problems proposed by A.S. Strekalovsky. We implement the developed algorithm and compare it with k-means clustering algorithms on generated datasets.

ABSTRACT. The paper considers the problem of finding low-energy metallic Gupta clusters, which reduces to the global minimization of the multiextremal potential function. We propose algorithms and computational techniques for the study of these atomic-molecular clusters. Problems with a small, a medium, and a large number of atoms are investigated to check the performance of the developed methods. System computational experiments were performed to search for a global minimum in the Gupta model of extremely large dimensions (from 126 to 156 atoms). The authors are not aware of other works in which the results of computations for clusters of the specified number of atoms are given.

ABSTRACT. In this paper we describe a new evolutionary strategy. It is based on the common (1+1) random mutation scheme which was augmented with metaheuristic technique named merging variables principle, that was proposed by us in previous works. We show that the new variant of (1+1)-EA has asymptotically lower worst case estimation than the original (1+1)-EA. In the experimental part we conduct comparison of the proposed strategy with several known variants of (1+1)-EA and demonstrate its practical applicability on several hard variants of MaxSAT problem.

ABSTRACT. In the capacitated facility location and design problem with elastic demand a new Company planes to open service facilities. The Company fights with a Competitor for a serviced share of all customer demand. This share varies elastically depending on the location and design of the facilities being opened. In this formulation, customer demand is known and assumed to be unchanged. However, in real-world situations, when planning for a certain period of time, the demand changes, and instead of exact values, its estimates can be given. Therefore, robust placement problems have appeared that take this fact into account. In this paper, we formulate a new robust model of the capacitated facility location and design problem with elastic demand. A problem-specified version of the annealing simulation algorithm is developed. To organize the search for a solution, new types of neighborhoods are constructed. The results of computational experiments are performed.

ABSTRACT. We consider the real-world Drilling Rig Routing Problem (DRRP) in an uncertain environment. There is a set of objects that are exploration sites requiring well-drilling work. Each object includes a known number of wells that need to be drilled within a given time interval, and it is allowed to partition the set of wells so that several drilling rigs perform the required work. In the real world, unforeseen circumstances can affect drilling time, and that, if disregarded, can lead to a disruption of the work plan. Thus, in this problem, we maximize the error in the drilling time estimates when there is still a set of routes and schedules for a fleet of drilling rigs to perform all well-drilling requests in time with total traveling costs no more than a given threshold. It is a so-called threshold robustness approach. In this research, we propose an integer linear programming model for the DRRP with uncertainties and a method based on Adaptive Large Neighborhood Search (ALNS). Computational results for our algorithm and a state-of-the-art MILP solver are presented.

ABSTRACT. We consider the problem of scheduling multiprocessor jobs to minimize the total completion time under the given energy budget. Each multiprocessor job requires more than one processor at the same moment of time. Processors may operate at variable speeds. Running a job at a slower speed is more energy efficient, however it takes longer time and affects the performance. The complexity of both parallel and dedicated versions of the problem is investigated. We propose approximation and exact algorithms for various particular cases. In our algorithms, initially a sequence of jobs and their processing times are calculated and then a feasible solution is constructed using list-type scheduling rule.

ABSTRACT. We consider a new scheduling problem originated from the order picking at an automatic warehouse. We have a finite set of orders. Each order consists of a set of items. All items are stored in pallets at the automatic flat warehouse. Each order should process through the picking station where items are extracted from pallets and packing in a box. We have some parallel picking machines and some parking places for pallets. Each machine can use all pallets at the parking places at the same time. Each pallet should be bringing from the automatic warehouse to the picking station and return back by a transport robot. The number of robots is limited. Our goal is to minimize makespan. We design a local search heuristic to tackle the problem. Feasible solutions are coded by a permutation of items. The decoder procedure creates a corresponding active schedule for parallel machines taking into account the limited number of transport robots. Computational experiments for real data of a big electronic device warehouse indicate the high efficiency of the approach.

ABSTRACT. Stackelberg's game of three players is considered. There are the leader company, the follower company, and their clients. First, the leader sets own price for his facilities, then the follower chooses the optimal price for products for his facilities, taking into account the leader's choice. After that, each client chooses where to purchase a unit of goods in such a way that their transport and purchase costs are minimal. The product is purchased only if the client's budget allows it. The goal of the game is to find the price vector at which the leader's income will be the maximum. Two problem statements are considered: when mill pricing is at the first level, uniform pricing is at the second level, and vice versa. In the levels with mill pricing, the choice of the optimal facility location of enterprises has been added.

The problems under consideration are a generalization of the problems discussed earlier ([1], [2]). To solve the generalized case, it is proposed to extend the existing exact algorithms that have proved to be the best for these problems. The algorithm is based on decomposition for the problem with uniform pricing for the leader and mill pricing for the follower. And the algorithm is based on projecting lower-level variables onto the upper one for the second problem. The results of a computational experiment are presented.

The study was carried out within the framework of the state contract of the Sobolev Institute of Mathematics (project no. 0314-2019-0014)

ABSTRACT. This article continues the author’s research into cooperation between public and private investors in the resource region. Unlike previous works, here an attempt was made to explicitly take into account the interests of the local population. This work aims to analyze the partnership mechanisms in terms of efficiency, using the game-theoretical Stackelberg model. Such mechanisms determine the economic policy of the state and play an important role for addressing a whole range of issues related to the strategic management of the natural resource sector in Russia. Models are formulated as bilevel mathematical programming problems with two optimization criteria at the upper level. Effective solution algorithms based on metaheuristics and allowing solving large-dimensional problems will be developed. This opens up the possibility of practical study on the real data of the properties of Stackelberg equilibrium, which determines the design of the mechanism for the formation of economic policy, clearly taking into account the interests of the local population. The simulation results will allow not only to assess the impact of various factors on the effectiveness of the generated subsoil development program but also to formulate the basic principles that should guide the state in the strategic management process. This work is supported by Russian Foundation for Basic Research (projects numbers 20–010–00151 and 19–410–240003).

ABSTRACT. In this paper, we consider the precoding problem for wireless MIMO systems. This task is crucial for modern cellular 5G networks. The optimal precoding matrix is determined by a special hard to solve non-convex constrained optimization problem. That is why in practice heuristic algorithms for precoding are mainly used, such as Maximal-Ratio Transmission or Zero-Forcing. In this paper, we propose to find precoding matrix using optimization of spectral efficiency in special families of matrices. We are testing the proposed approach in several scenarios generated using Quadriga - an open source software for generating realistic radio channel impulse response. Our method shows monotonic improvement over heuristic methods with reasonable computation time.

ABSTRACT. We propose a dengue transmission model of SIR(S)-SI type that accounts for two sex-structured mosquito populations: the wild mosquitoes (males and females that are Wolbachia-free), and those deliberately infected with either wMel or wMelPop strain of Wolbachia symbiotic bacterium. Laboratory experiments have revealed that Wolbachia induces the inhibition of the dengue virus inside the mosquitoes which leads to a considerable reduction of dengue morbidity in human populations. Wolbachia-based biocontrol of dengue operates by releases of Wolbachia-infected mosquitoes seeking to crush the populations of wild insects.

In the present study, we bring forth the methodology capable of providing quantitative estimations of the three key metrics of Wolbachia-based biocontrol when the initial size of the wild mosquito population can be fairly assessed. The proposed methodology stems from the optimal control approach for the design of strain-dependent optimal release programs that can be characterized by the following three quantifications: (a) optimal time of effective releases; (b) a total number of Wolbachia-carrying insects to be mass-reared, and (c) the estimated number of human infections to be prevented.

Additionally, our discussion is also focused on the cost-effectiveness of two Wolbachia strains, wMel and wMelPop, that are usually employed for Wolbachia-based dengue control.

ABSTRACT. We consider an optimal control problem for a linear continuity equation in the space of probability measures, subject to additonal integral constraint on control. The latter establishes a connection of the addressed model with the framework of impulsive control. Dynamical systems in the space of measures are used to model (infinite) ensembles of microscopic individuals (agents) driven by a common vector field. The control is a function of time variable only, i.e., it is common for all the individuals. For the case, when the agents do not interact one with another, we present a necessary optimality condition of the type of feedback minimum principle (FMP), which employs the constructions of Pontryagin's Maximum Principle (PMP) for designing an ensemble-feedback control. We give an example showing that FMP can be used to discard non-optimal PMP extrema, and discuss the algorithmic feature of FMP, which implies its realization as an iterative numeric algorithm for optimal impulsive control.

ABSTRACT. During the last year the pandemic of COVID-19 affected 192 countries with over 100 million confirmed people. There was determined seven SARS-CoV-2 strains and created a lot of vaccines and mathematical models that needed to be investigated in short and long terms. The simulation of different scenarios of epidemy propagation in Novosibirsk region depend on interventions and vaccination procedure can be used for developing of effective programs for control the epidemy. We propose the updated agent-based mathematical model of COVID-19 propagation in Novosibirsk region based on COVASIM software [1]. At the first step of modeling data analysis using machine learning approach is carried out. It allows to determine the correlated datasets and find some features that used in modeling procedure. At the second step unknown model parameters that depend on intervention dates such as reproduction number, number of asymptomatic patients, etc. are calibrated using additional measurements about number of daily confirmed, tested, death cases as well as statistic information about disease. We use OPTUNA [2] optimization approach for minimization the misfit function and identifiability analysis for regularization [3]. At the third step we analyze different scenarios of COVID-19 propagation depend on interventions and vaccination [4]. This work is supported by the Russian Science Foundation (project no. 18-71-10044) and the Council for Grants of the President of the Russian Federation (project no. МК-4994.2021.1.1).

References: [1] C. C. Kerr, R. M. Stuart, D. Mistry, R. G. Abeysuriya, G. Hart, K. Rosenfeld, P. Selvaraj, R. C. Nunez,B. Hagedorn, L. George, A. Izzo, A. Palmer, D. Delport, C. Bennette, B. Wagner, S. Chang, J. A. Cohen,J. Panovska-Griffiths, M. Jastrzebski, A. P. Oron, E. Wenger, M. Famulare, D. J. Klein. Covasim: an agent-based model of covid-19 dynamics and interventions, medRxiv (2020). DOI: 10.1101/2020.05.10.20097469. [2] A hyperparameter optimization framework optuna, https://optuna.org/. [3] Krivorotko O.I., Andornaya D.V., Kabanikhin S.I. Sensitivity analysis and practical identifiability of some mathematical models in biology. Journal of Applied and Industrial Mathematics. 2020; 14:115–130. DOI: 10.1134/S1990478920010123. [4] Krivorotko O.I., Kabanikhin S.I., Zyatkov N.Yu., Prikhodko A.Yu., Prokhoshin N.M., Shishlenin M.A. Mathematical modeling and forecasting of COVID-19 in Moscow and Novosibirsk region. Siberian Journal of Numerical Mathematics. 2020; 23(4):395–414. DOI: 10.15372/SJNM20200404

ABSTRACT. In my talk, I will introduce several mathematical directions from the domain of Discrete Optimization and Operational Research and having importance in different technologies researched by Mathematical Modeling Laboratory at Huawei. There are no engineering prerequisites required, and my target is to show many opportunities to do mathematical research with an impact on technologies.

ABSTRACT. We introduce a new temporal bin packing problem that originated from cloud computing. We have a finite set of items. For each item, we know an arriving time, processing time, and two weights (CPU, RAM). Some items we call large. Each bin (server) has two capacities and is divided into two identical parts (left and right). A regular item can be placed in one of them. A large item is divided into two identical parts and placed in both parts of a bin. Our goal is to pack all items into the minimum number of bins. For this NP-hard problem, we design a heuristic that is based on column generation to get lower and upper bounds. Preliminary computational experiments for real test instances indicate a small gap between the bounds. The average relative error is at most 0.5% for one week planning horizon and about 50000 items. The average running time is 24 seconds for a personal computer.

ABSTRACT. In this paper we address the so-called two-dimensional Multiple Strip Packing Problem (MSPP). Given a set of rectangles and a set of strips, each strip has a pre-defined width, the problem is to find a feasible packing of all the rectangles into the strips so as the maximal height of the packing over all the strips is minimized. A packing is feasible if all the rectangles are placed into the strips and not overlapped. In case of only one strip, the problem is widely known as the Strip Packing Problem (SPP). Many effective constructive heuristics for SPP are based on the so-called skyline representation of a packing pattern. We generalized this approach for the case of multiple strips and developed a randomized local search, which embeds the proposed skyline heuristic to compute the objective value for a packing. We also introduced the two-dimensional level multiple strip packing problem and developed some level-based constructive heuristics. We report computational results on real-life problem instances arisen in an application of MSPP in scheduling computing jobs on multiple Spark computer clusters.

ABSTRACT. Modern wireless cellular networks use massive multiple-input multiple-output (MIMO) technology. This involves operations with an antenna array at a base station that simultaneously serves multiple mobile devices that also use multiple antennas on their side. For this, various Beamforming and Detection techniques are used, allowing each user to receive the signal intended for him from the base station. There is an important class of linear Precoding called Regularized Zero-Forcing (RZF). In this work, we propose a special kind of regularization matrix with different regularization for different UE (Adaptive RZF), using singular values of multi-antenna users. Proposed algorithm has a simple analytical formula and is provided with theoretical study and asymptotic behavior. We also show the results in comparison with other linear Precoding algorithms on simulations with the Quadriga channel model. The proposed approach leads to a significant increase in quality with the same computation time as in the baseline methods.

ABSTRACT. The Shortest Simple Path Problem with Must-Pass Nodes (SSPP-MPN) is the well-known combinatorial optimization problem having numerous applications in operations research. In this paper, we show that this problem remains intractable even in the case of any fixed number of nodes to visit. Our main result is the novel problem-specific branch-and-bound algorithm for this problem. We prove its high performance by a numerical evaluation carried out on the real-life benchmark dataset 'Rome99' taken from the 9th DIMACS Implementation (shortest paths) Challenge. The results show that the proposed algorithm outperforms the well-known solver Gurobi equipped with the best known MILP models both in obtained accuracy and execution time.

ABSTRACT. We consider a real-life problem that arises in an industrial process of a big electronic device manufacturer. A warehouse, which stores the finished products is involved in the orders packing and delivery process. Each order should process through two stages to be prepared for delivery. During the first stage, picking, the ordered goods have to be extracted from the storage. During the second stage, these goods have to be packed into the boxes and transferred to the delivery service. The problem is to arrange the schedule and the way the orders have to process through the stages, in order to maximize the throughput of the warehouse. We propose a set of constructive heuristics and hybrid approaches for this problem and discuss the results of computational experiments on real data, provided by the Huawei company.

ABSTRACT. The last ten years have seen much progress in the field of so-called extended formulations, which aims at reformulating effectively a problem/polyhedron with the help of (exponentially many) additional variables. In particular, network-flow formulations have received increasing interest from the community. A considerable difficulty to overcome when dealing with such a formulation is to handle its size. In this talk, we recall some key results concerning these formulations and present several recent successful applications that have been obtained using innovative aggregation/disaggregation techniques.

ABSTRACT. Integer programs (IP) with m constraints are solvable in pseudo-polynomial time. We give a new algorithm based on the Steinitz Lemma and dynamic programming with a better pseudo-polynomial running time than previous results.

Moreover, we establish a strong connection to the problem (min,+) - convolution. (min,+) - convolution has a trivial quadratic time algorithm and it has been conjectured that this cannot be improved significantly.

Finally, we show for the feasibility problem also a tight lower bound, which is based on the Strong Exponential Time Hypothesis (SETH), and give some applications for knapsack and scheduling problems. This is joint work with Lars Rohwedder.