Optimization Problems and Their Applications

The problem of minimizing a supermodular set function is considered. A special case of this problem is the well-known NP-hard minimization p-median problem. The main results of the paper are tight a priori and a posteriori bounds on worst-case behaviour of a “reverse” greedy (steepest descent) algorithm of minimizing a supermodular set function on comatroid. As a corollary, approximation guarantees of this algorithm for the general minimization p-median problem improving the known bounds are obtained.

In this paper, a new optimization model of competitive facility location and pricing is introduced. This model is an extension of the well-known (r|p)-centroid problem. In the model, two companies compete for the client’s demand. Each client has a finite budget and a finite demand. First, a company-leader determines a location of p facilities. Taking into account the location of leader’s facilities, the company-follower determines a location of its own r facilities. After that, each company assigns a price for each client. When buying a product, the client pays the price of the product and its transportation. A client buys everything from a company with lower total costs if their total costs do not exceed the budget of the client. If the cost of buying a product from both companies is the same, the demand of clients is distributed equally among them. The goal is to determine a location of leader’s facilities and set the prices in which the total income of the leader is maximal. Results about the computational complexity of the model are presented. Several special cases are considered. These cases can be divided into three categories: (1) polynomially solvable problems; (2) NP-hard problems; (3) problems related to the second level of the polynomial hierarchy. Finally, the complexity of the maxmin-2-Sat problem is discussed.

The problem of location of connected rectangular facilities on parallel lines in the presence of forbidden gaps is studied. The rectangular metric is used. The centers of the placed facilities are connected with the centers of the gaps. The facilities are impossible to place in forbidden gaps. It is necessary to place the facilities on the lines so that the total cost of connections between the facilities and between facilities and gaps was minimized. The problem is an adequate model of many practical situations. It is known that the original continuous problem for one–line variant is reduced to discrete subproblems. In this paper, the review of the properties and the algorithms for solving of the problem on one line are described. The branch and bound method for solving the problem is proposed. Results of computational experiments on comparison of the branch and bound method and a heuristic proposed in [27] are reported. In the experiments, a integer programming model and IBM ILOG CPLEX package are used.

We study the two-machine Open Shop problem with exact delays. When all delays are equal to zero this problem converts to the no-wait two-machine Open Shop problem, which is known to be NP-hard. We prove that even the proportionate case of Open Shop problem with exact delays does not admit approximations with ratio \(1.5-\varepsilon \) unless P \(=\) NP. We also consider the very special case when the delays take at most two different values and prove that the existence of a \((1.25-\varepsilon )\)-approximation algorithm for it implies P \(=\) NP.

In this study, one variant of multi-product scheduling problem is considered. The problem asks to find the optimal selection of a set of tasks to produce a given number of products in required amounts, to allocate the task on units, and to find the order of execution of tasks for each unit. The production rates for each task, the task-unit suitability matrix, and the sequence dependent changeover times for task pairs are given.

For the one-unit problem, two combinatorial algorithms are proposed: a branch-and-bound algorithm and a parallel dynamic programming algorithm. The last one is implemented using the CUDA library for running on a Graphical Processing Unit (GPU). For the multiple-units problem, both approaches are combined in a branch-and-bound algorithm with bounds provided by the dynamic programming procedure.

The algorithms are compared with CPLEX solver applied to the considered problem formulated as a mixed integer linear program. Although, the main limitation of using the proposed algorithms is a requirement of large amount of memory, the experiments showed their superior performance over CPLEX in terms of running time for rather large sized instances. The advantage of parallelization and using the GPU is also demonstrated.

We consider the Euclidean Generalized Traveling Salesman Problem in Grid Clusters (EGTSP-GC), a special geometric subclass of the famous Generalized TSP, introduced by Bhattacharya et al. They showed that the problem is strongly NP-hard if the number of clusters k belongs to the instance and proposed the first polynomial time algorithm with a fixed approximation ratio. Recently, we proved that EGTSP-GC belongs to PTAS when \(k=O(\log n)\) and \(k=n-O(\log n)\). Meanwhile, being the special case of GTSP, for any fixed k, EGTSP-GC can be solved to optimality in polynomial time. Therefore, it seems interesting to describe the most general case of the problem sharing this property. Recently, by virtue of generalized pyramidal routes, we provided an optimal algorithm with \(O(n^3)\) time complexity bound for the case of EGTSP-GC, whose grid height does not exceed 2. In this paper, we extend this result to the case of EGTSP-GC defined by a grid of any fixed height.

The paper presents the worst-case analysis of a polynomial-time approximation algorithm for the maximum lateness scheduling problem with parallel identical machines, arbitrary processing times and arbitrary precedence constraints. The algorithm is a modification of the Brucker-Garey-Johnson algorithm originally developed as an exact algorithm for the case of the problem with unit execution time tasks and precedence constraints represented by an in-tree. For the case when the largest processing time does not exceed the number of machines, we obtain a worst-case performance guarantee which is tight for arbitrary large instances of the considered maximum lateness problem. It is shown that, if the largest processing time is greater than the number of machines, then the worst-case performance guarantee for the list algorithm, obtained by Hall and Shmoys, is tight.

We consider the bicriteria asymmetric traveling salesman problem (bi-ATSP). Optimal solution to a multicriteria problem is usually supposed to be the Pareto set, which is rather wide in real-world problems. We apply to the bi-ATSP the axiomatic approach of the Pareto set reduction proposed by V. Noghin. We identify series of “quanta of information” that guarantee the reduction of the Pareto set for particular cases of the bi-ATSP. An approximation of the Pareto set to the bi-ATSP is constructed by a new multi-objective genetic algorithm. The experimental evaluation carried out in this paper shows the degree of reduction of the Pareto set approximation for various “quanta of information” and various structures of the bi-ATSP instances generated randomly.

We consider two strongly NP-hard problems of clustering a finite set of points in Euclidean Space. Both problems have applications, in particular, in data analysis, data mining, pattern recognition, and machine learning. In the first problem, an input set is given and we need to find a cluster (i.e., a subset) of a given size which minimizes the sum of squared distances between the elements of this cluster and its centroid (the geometric center). Every point outside this cluster is considered as singleton cluster. In the second problem, we need to partition a finite set into two clusters minimizing the sum over both clusters of the weighted intracluster sums of the squared distances between the elements of the clusters and their centers. The center of the first cluster is unknown and determined as the centroid, while the center of the second one is the origin. The weight factors for both intracluster sums are the given clusters sizes. In this paper, we present parameterized randomized algorithms for these problems. For given upper bounds of the relative error and failure probability, the parameter value is defined for which both our algorithms find approximate solutions in a polynomial time. This running time is linear on the space dimension and on the input set size. The conditions are found under which these algorithms are asymptotically exact and have the time complexity that is linear on the space dimension and quadratic on the size of the input set.

The following problem is considered. Given a finite sequence of Euclidean points, find a subsequence of the longest length (size) such that the sum of squared distances between the elements of this subsequence and its unknown centroid (geometrical center) is at most a given percentage of the sum of squared distances between the elements of the input sequence and its centroid. This problem models, in particular, one of the data analysis problems, namely, search for the maximum subset of elements close to each other in the sense of the bounded from above the total quadratic scatter in the set of time-ordered data. It can be treated as a data editing problem aimed at the removal of extraneous (dissimilar) elements. It is shown that the problem is strongly NP-hard. A polynomial time approximation algorithm is proposed. It either finds out that the problem has no solutions or outputs a 1/2-approximate solution if the length \(M^*\) of an optimal subsequence is even, or it outputs a \((M^* - 1)/2M^*\)-approximate solution if \(M^*\) is odd. Some examples of numerical experiments illustrating the algorithm suitability are presented.

We consider a problem of finding a subset of the smallest size in the given set of vectors such that the norm of sum vector is greater or equal to some given value. We show that the problem can be solved optimally with the same complexity as the problem of finding the subset of given cardinality with minimum norm of sum vector.

Fast numerical evaluation of forward models is central for a broad range of inverse problems. Here we propose a method for deriving computationally efficient representations of periodic solutions of parameterized systems of nonlinear ordinary differential equations. These representations depend on parameters of the system explicitly, as quadratures of parameterized computable functions. The method applies to systems featuring both linear and nonlinear parametrization, and time-varying right-hand side. In addition, it opens possibilities to invoke scalable parallel computations and suitable function approximation schemes for numerical evaluation of solutions for various parameter values. Application of the method to the problem of parameter estimation of nonlinear ordinary differential equations is illustrated with a numerical example for the Morris–Lecar system.

Following the seminal work of Padberg on the Boolean quadric polytope BQP and its LP relaxation \(BQP_{LP}\), we consider a natural extension: the polytopes SATP and \(SATP_{LP}\), with \(BQP_{LP}\) being a projection of \(SATP_{LP}\) face (and BQP – projection of SATP face). Various special instances of 3-SAT problem like NAE-3-SAT, 1-in-3-SAT, weighted MAX-3-SAT, and others can be solved by integer programming over \(SATP_{LP}\). We consider the properties of SATP 1-skeleton and \(SATP_{LP}\) fractional vertices. Like \(BQP_{LP}\), the polytope \(SATP_{LP}\) has the Trubin-property being quasi-integral (1-skeleton of SATP is a subset of 1-skeleton of \(SATP_{LP}\)). However, unlike BQP, not all vertices of SATP are pairwise adjacent, the diameter of SATP equals 2, and the clique number of 1-skeleton is superpolynomial in dimension. It is known that the fractional vertices of \(BQP_{LP}\) are half-integral (0, 1 or 1/2 valued). We establish that the denominators of \(SATP_{LP}\) fractional vertices can take any integer values.

In this paper, the alternative duality schemes for mathematical programming problems are considered. These schemes are based on the Lagrange function regularized by Tikhonov in primal and dual variables simultaneously. Earlier such schemes were investigated for convex programming problems only, and the conditions were found which guarantee a convergence of both primal and dual components of the saddle point of the regularized Lagrange function to the optimal sets of primal and dual problems respectively. In addition, some accuracy estimates were obtained for deviation of only one of these components from the normal solution (solution with minimal the Euclidean norm) of the corresponding problem, primal or dual. Unfortunately, these estimates are valid only if primal and dual parameters of regularization have a different order of smallness. In this article, the linear case is investigated in detail. It is shown that for linear programming problem both mentioned sequences converge to the normal solutions of primal and dual programs simultaneously, and it is not essential for such a convergence whether the regularization parameters have a different or the same order of smallness. Also, the alternative accuracy estimates are presented which appear to be more precise and efficient in comparison with the estimates known for a convex case.

A point is called binary if its coordinates are equal to either zero or one. It is well known that it is hard to find a binary solution to the system of linear equations whose coefficients are integers with small absolute values. The aim of the article is to propose an effective probabilistic reduction from the system to the unique equation when there is a small difference between the number of binary solutions to the first equation and the number of binary solutions to the system. There exist nontrivial examples of linear equations with small positive coefficients having a small number of binary solutions in high dimensions.

We propose a method of solving a convex programming problem, which is based on the ideas of cutting plane methods and the method of penalty functions. To construct each approximation, the method uses an operation of immersing the epigraph of auxiliary function into a polyhedral set. The auxiliary function is constructed as the sum of the objective function and the external penalty function of the constraint area. In addition, an admissible set of the original problem is immersed in the polyhedron simultaneously. In connection with this, the problem of constructing an iterative point is a linear programming problem, in which constraints are polyhedrons approximating the epigraph of auxiliary function and the admissible set. Both next approximating sets are based on the previous ones by cutting off the iterative point from them by hyperplanes. The convergence of the method is proved. We describe its algorithms. One of them can be the implementation of the method of penalty functions.

At the present time, the discrete-time models are not given enough attention. But these models are more realistic than the continuous models, because the allocation of funds is discrete. In the paper a new discrete model of optimal advertising is proposed. This model takes into account the uncertainties. These uncertainties are caused by acts of a set of the small companies. The companies’ problem is to maximize their market share taking into account the reaction of competitors. The problem is a discrete multistep optimal control problem. For this model the optimal control problem is solved explicitly. The Bellman method of dynamic programming is used to construct the guaranteed equilibrium.

An analysis is presented of a public-private partnership model in the natural resources sector of Russia, whereby the government provides tax incentives and supports the investor in infrastructure development and, to some extent, in the implementation of mandatory environmental measures. The analysis builds on the Stackelberg model and an original iterative solution algorithm based on probabilistic local search. A full-size model test site is constructed to demonstrate the capabilities of the approach. The actual data and dimensions of the model test site capture the specificity of the modeled object and make possible a practical study of the properties of the Stackelberg equilibrium. Based on the modeling results, an assessment is made of the impact of various factors on the effectiveness of the subsoil development program and the basic principles are formulated for government decision-making in this area.

An important feature of the mixed economic system under consideration, besides the presence of a mixed production sector, is that two different regulation mechanisms function jointly: central planning and flexible market prices. Thus, this model is characterized by the presence of dual markets. In the first market, prices are stable and the allocation of commodities is determined by rationing schemes and governmental orders. In the second market, prices are flexible and are formed by the standard mechanism of equating demand and supply. We assume that the excess of any commodity purchased in the first market may be resold by any economic agent at flexible market prices. Whereas a lot of papers are devoted to existence and efficiency of mixed market equilibria, this paper investigates extremal properties of equilibrium allocations in a mixed economy of Arrow-Debreu type. A notion of fuzzy domination in a mixed environment is given, and coincidence of the fuzzy core and equilibrium allocations in certain specifications of economy in question is shown to hold.

We consider the problem of empty tank cars relocation in a railway petroleum transportation. Biggest petroleum carrier in Kazakhstan railway network provides transportation service to the customers. The majority of its expenses consist of an empty run of the cars, as they move to the load stations. Given the demand for empty tank cars, the company seeks to reduce total costs to satisfy all the demand within a planning period. We provide a mathematical model for this problem in terms of integer programming and perform an experimental study with LP solver. Numerical calculations show that new model allows to significantly reduce empty run of the tank cars on the railway petroleum logistics market lowering the total expenses of the company by more than 10% level.

We consider a bi-objective optimization problem of choosing the buffers capacity in a production system of parallel tandem lines, each consisting of two machines with a single intermediate buffer. During operation of the system, the equipment stops occur due to failures and these stops are random in the moments when they arise and in their durations. The product is accumulated in an intermediate buffer if the downstream machine is less productive than the upstream machine.

We study the complexity of exact and approximate computations of a Pareto front for the following two bi-objective problem formulations: (i) the expected revenue maximization with minimization of buffers allocation cost and (ii) the expected revenue maximization with minimization of expected inventory costs. The expected revenue is assumed to be an increasing function of the expected throughput of the system.

On the one hand, fully polynomial-time approximation schemes for approximation of Pareto fronts of these problems are proposed and an exact pseudo-polynomial time algorithm is suggested for the first problem in the case of integer buffer capacity costs. On the other hand, we show that both of these problems are intractable even in the case of just one tandem two-machine line.

We study a spare part supply system where both Traditional Manufacturing and Additive Manufacturing (also know as 3D printing) are used for replenishment of the spare parts inventories. Demands for the spare parts occur according to a Poisson process, and the failed parts are immediately replaced from the inventory, if available. If inventory is not available, items are backordered and fulfilled when a spare becomes available (i.e., a replenishment is received from one of the suppliers). Additive Manufacturing offers the advantage of shorter lead times, however, at higher production costs. Moreover, Additive Manufacturing processes often have uncertain yield, leading to the fact that not every produced part will satisfy the quality control and can be used to replenish the inventory. In this paper, we propose a Linear Programming (LP) based optimization problem that decides which of the processes to use for replenishment of the inventory while minimizing the total (holding + backorder) system costs.

We study a pooling-inventory-capacity problem that arises in the design of repair shops for repairable spare part logistic systems. We formulate the problem as a stochastic nonlinear integer programming model and propose a two-stage sequential solution algorithm. At the first stage, a genetic algorithm (GA) generates a set of feasible pooled repair shop design schemes. A pooled design can be viewed and modeled as the union of mutually exclusive and total exhaustive multi-class multi-server queueing systems. Thus, we exploit this fact and optimize each queueing system separately. In the second stage, optimal inventory and capacity levels for each independent system are calculated by using a queueing approximation technique and a local greedy heuristic. Finally, the performed numerical experiments show that proposed two-stage approach achieves high-quality solutions in reasonable time.

We study a new bin packing problem with a color constraint. A finite set of items and an unlimited number of identical bins are given. Each item has a set of colors. Each bin has a color capacity. The set of colors for a bin is the union of colors for its items and its cardinality can not exceed the bin capacity. We need to pack all items into the minimal number of bins. For this NP-hard problem, we design the core heuristic based on the column generation approach for the large-scale formulation. A hybrid VNS matheuristic with large neighborhoods is used for solving the pricing problem. We use our core heuristic in the exact branch-and-price method. Computational experiments illustrate the ability of the core heuristic to produce optimal solutions for randomly generated instances with the number of items up to 250. High-quality solutions on difficult instances with regular structure are found.

We study the problem of estimating a probability that a flow of a given capacity may be transferred in a communication network. Network is represented by a random graph with absolutely reliable nodes and unreliable links with given operational probabilities and capacities. The algorithm for fast decision making whether a network is reliable enough for transmission of a given flow is proposed. Case studies show applicability of the proposed approach.

We present a new optimization model to maximize the total operating profit of a harbor logistics company on a finite time horizon. Some local providers supply the company with a scrap-metal materials of different qualities. The materials are reprocessed into the high-quality product and exported to abroad by different types of ships. The company has to cover the purchase cost for the materials, the transportation cost to deliver the materials, the reprocessing and storage cost in a warehouse, shipping cost, and payment for international declarations. To find the best strategy for the company we present a mixed integer nonlinear model. We linearize the objective function and aggregate the set of providers in order to apply CPLEX software efficiently. We conduct computational experiments on real test instances and discuss how to use the model for planning fleet of vehicles, a capacity of the warehouse, and price strategy for the company.