An algorithm for finding an approximate solution to the Weber problem on a line with forbidden gaps

Under study is the problem of optimal location of interconnected objects on a line with forbidden gaps. The task is to minimize the total cost of links between objects and between objects and zones. The properties of the problem are found that allowed us to reduce the initial continuous problem to a discrete problem. Some algorithm for obtaining an approximate solution is developed, and the results of a computational experiment are given.     

混合体积、对数凹序列和B样条函数

本文主要通过样条函数方法研究与之相关的离散几何学和组合学问题.在离散几何学方面主要考虑超立方体切面(cube slicing)体积和混合体(mixed volume)的样条表示,利用B样条函数的几何解释,将超立方体切面问题转化为与之等价的样条函数问题,分别给出Laplace和P′olya关于超立方体切面定理的样条证明,将样条函数与混合体积联系起来,给出一类混合体积的样条解释.利用这种解释可以得到一类具有对数凹性质的组合序列,从而部分地回答了Schmidt和Simion所提出的关于混合体积的公开问题.在组合数学方面主要考虑多种组合多项式与样条函数的关联以及组合序列对数凹性质的样条方法研究.本文借助丰富的样条函数理论,不但验证了离散几何学和组合数学中很多现有的结果,而且得到了一系列离散数学对象的新性质,建立了离散数学问题与具有连续性特质的样条函数之间的内在联系.     

Frequency assignment in a SDMA satellite communication system with beam decentring feature

In satellite communication, Spatial Division Multiple Access (SDMA) has become one of the most promising techniques that can accommodate continuing increase in the number of users and traffic demands. The technology is based on radio resource sharing that separates communication channels in space. It relies on adaptive and dynamic beam-forming technology and well-designed algorithms for resource allocation among which frequency assignment is considered. This paper studies static Frequency Assignment Problem (FAP) in a satellite communication system involving a satellite and a number of users located in a service area. The objective is to maximize the number of users that the system can serve while maintaining the signal to interference plus noise ratio of each user under a predefined threshold. Traditionally, interference is treated as fixed (binary interferences or fixed minimal required separation between frequencies) . In this paper, the interference is cumulative and variable. To solve the problem, we work on both discrete and continuous optimizations. Integer linear programming formulations and greedy algorithms are proposed for solving the discrete frequency assignment problem. The solution is further improved by beam decentring algorithm which involves continuous adjustment of satellite beams and deals with non-linear change of interference.     

On optimality of a polynomial algorithm for random linear multidimensional assignment problem

We demonstrate that the linear multidimensional assignment problem with iid random costs is polynomially e{\varepsilon} -approximable almost surely (a.s.) via a simple greedy heuristic, for a broad range of probability distributions of the assignment costs. Specifically, conditions on discrete and continuous distributions of the cost coefficients, including distributions with unbounded support, have been established that guarantee convergence to unity in the a.s. sense of the cost ratio between the greedy solution and optimal solution. The corresponding convergence rates have been determined.     

Knapsack problems with sigmoid utilities: Approximation algorithms via hybrid optimization

We study a class of non-convex optimization problems involving sigmoid functions. We show that sigmoid functions impart a combinatorial element to the optimization variables and make the global optimization computationally hard. We formulate versions of the knapsack problem, the generalized assignment problem and the bin-packing problem with sigmoid utilities. We merge approximation algorithms from discrete optimization with algorithms from continuous optimization to develop approximation algorithms for these NP-hard problems with sigmoid utilities.     

Two heuristic solution concepts for the vehicle selection problem in line haul transports

In this article we will develop a mathematical model for a cost-efficient selection of vehicles with varying capacities for line haul transports with leasing options. For this integer optimization problem, which is a variant of the generalized assignment problem known as NP-hard, we will compare two heuristic solution concepts and try to answer the question in which cases a user should choose an exact or approximate solution concept depending on different data instances of the problem.     

Analysis of a Chimera method

Chimera is a variant of Schwarz' algorithm which is used in CFD to avoid meshing complicated objects. In a previous publication [3] we proposed an implementation for which convergence could be shown except that ellipticity was not proved for the discretized bilinear form with quadrature rules. Here we prove that the bilinear form of the discrete problem is strongly elliptic without compatibility condition for the mesh of the subdomains in their region of intersection.     

The Projected Power Method: An Efficient Algorithm for Joint Alignment from Pairwise Differences

Various applications involve assigning discrete label values to a collection of objects based on some pairwise noisy data. Due to the discrete—and hence nonconvex—structure of the problem, computing the optimal assignment (e.g., maximum‐likelihood assignment) becomes intractable at first sight. This paper makes progress towards efficient computation by focusing on a concrete joint alignment problem; that is, the problem of recovering n discrete variables x_i ∊ {1, …, m}, 1 ≤ i ≤ n, given noisy observations of their modulo differences {x_i — x_j mod m}. We propose a low‐complexity and model‐free nonconvex procedure, which operates in a lifted space by representing distinct label values in orthogonal directions and attempts to optimize quadratic functions over hypercubes. Starting with a first guess computed via a spectral method, the algorithm successively refines the iterates via projected power iterations. We prove that for a broad class of statistical models, the proposed projected power method makes no error—and hence converges to the maximum‐likelihood estimate—in a suitable regime. Numerical experiments have been carried out on both synthetic and real data to demonstrate the practicality of our algorithm. We expect this algorithmic framework to be effective for a broad range of discrete assignment problems.© 2018 Wiley Periodicals, Inc.     

Integer programming models for the multidimensional assignment problem with star costs

We consider a variant of the multidimensional assignment problem (MAP) with decomposable costs in which the resulting optimal assignment is described as a set of disjoint stars. This problem arises in the context of multi-sensor multi-target tracking problems, where a set of measurements, obtained from a collection of sensors, must be associated to a set of different targets. To solve this problem we study two different formulations. First, we introduce a continuous nonlinear program and its linearization, along with additional valid inequalities that improve the lower bounds. Second, we state the standard MAP formulation as a set partitioning problem, and solve it via branch and price. These approaches were put to test by solving instances ranging from tripartite to 20-partite graphs of 4 to 30 nodes per partition. Computational results show that our approaches are a viable option to solve this problem. A comparative study is presented.     

Vibrational stabilization and the Brockett problem

The present paper deals with the exposition of methods for solving the Brockett problem on the stabilization of linear control systems by a nonstationary feedback. The paper consists of two parts. We consider continuous linear control systems in the first part and discrete systems in the second part. In the first part, we consider two approaches to the solution of the Brockett problem. The first approach permits one to obtain low-frequency stabilization, and the second part deals with high-frequency stabilization. Both approaches permit one to derive necessary and sufficient stabilization conditions for two-dimensional (and three-dimensional, for the first approach) linear systems with scalar inputs and outputs. In the second part, we consider an analog of the Brockett problem for discrete linear control systems. Sufficient conditions for low-frequency stabilization of linear discrete systems are obtained with the use of a piecewise constant periodic feedback with sufficiently large period. We obtain necessary and sufficient conditions for the stabilization of two-dimensional discrete systems. In the second part, we also consider the control problem for the spectrum (the pole assignment problem) of the monodromy matrix for discrete systems with a periodic feedback.     

The auction algorithm for the transportation problem

The auction algorithm is a parallel relaxation method for solving the classical assignment problem. It resembles a competitive bidding process whereby unassigned persons bid simultaneously for objects, thereby raising their prices. Once all bids are in, objects are awarded to the highest bidder. This paper generalizes the auction algorithm to solve linear transportation problems. The idea is to convert the transportation problem into an assignment problem, and then to modify the auction algorithm to exploit the special structure of this problem. Computational results show that this modified version of the auction algorithm is very efficient for certain types of transportation problems.     

Discretisation and duality of optimal Skorokhod embedding problems

We prove a strong duality result for a linear programming problem which has the interpretation of being a discretised optimal Skorokhod embedding problem, and we recover this continuous time problem as a limit of the discrete problems. With the discrete setup we show that for a suitably chosen objective function, the optimiser takes the form of a hitting time for a random walk. In the limiting problem we then reprove the existence of the Root, Rost, and cave embedding solutions of the Skorokhod embedding problem.The main strength of this approach is that we can derive properties of the discrete problem more easily than in continuous time, and then prove that these properties hold in the limit. For example, a consequence of the strong duality result is that dual optimisers exist, and our limiting arguments can be used to derive properties of the continuous time dual functions. These arguments are applied in Cox and Kinsley (2017), where the existence of dual solutions is required to prove characterisation results for optimal barriers in a financial application.     

Assignment problems with changeover cost

We consider some variant models, having changeover cost, of the assignment problem. In these models, multiple assignments to an operator are allowed. In addition to assignment costs, a changeover cost is incurred if an operator does one job after another is completed. Two different types of changeover costs and related two models are considered. Mathematical programming formulations are given for the models. When changeover costs are dependent on the operator but independent of the jobs and are non-negative, a linear programming model is obtained. For the case when changeover costs are dependent on the jobs, a linear integer programming formulation is obtained. We also show that, this problem is strongly NP-hard. A heuristic solution method is suggested for it. Numerical findings on the performance of the method are given.     

Long Time Asymptotic Behavior of Solution of Difference Scheme for a Semilinear Parabolic Equation

In this paper we prove that the solution of implicit difference scheme for a semilinear parabolic equation converges to the solution of difference scheme for the corresponding nonlinear stationary problem as $t\rightarrow\infty$. For the discrete solution of nonlinear parabolic problem, we get its long time asymptotic behavior which is similar to that of the continuous solution. For simplicity, we consider one-dimensional problem.     

Continuous dependence on data for bilocal difference equations

The continuous dependence on data is studied for a class of second order difference equations governed by a maximal monotone operator A in a Hilbert space. A nonhomogeneous term f appears in the equation and some bilocal boundary conditions a, b are added. One shows that the function which associates to {a, b, A, f} the solution of this boundary value problem is continuous in a specific sense. One uses the convergence of a sequence of operators in the sense of the resolvent. The problem studied here is the discrete variant of a problem from the continuous case.     

The incorporation of fixed cost and multilevel capacities into the discrete and continuous single source capacitated facility location problem

In this study we investigate the single source location problem with the presence of several possible capacities and the opening (fixed) cost of a facility that is depended on the capacity used and the area where the facility is located. Mathematical models of the problem for both the discrete and the continuous cases using the Rectilinear and Euclidean distances are produced. Our aim is to find the optimal number of open facilities, their corresponding locations, and their respective capacities alongside the assignment of the customers to the open facilities in order to minimise the total fixed and transportation costs. For relatively large problems, two solution methods are proposed namely an iterative matheuristic approach and VNS-based matheuristic technique. Dataset from the literature is adapted to assess our proposed methods. To assess the performance of the proposed solution methods, the exact method is first applied to small size instances where optimal solutions can be identified or lower and upper bounds can be recorded. Results obtained by the proposed solution methods are also reported for the larger instances.

     

A System Dynamics Model of Submarine Operations and Maintenance Schedules

The extent to which a proposed military force will achieve operational objectives is a prime concern of defence planners. This paper discusses the problem in the context of the exercise of sea power in distant waters and shows that a model of the whole problem would require a feedback analysis, for which an appropriate approach would be system dynamics. Such models have, in general, been continuous, but ships are discrete objects. The paper therefore addresses the construction of discrete system dynamics models as the basis for a model of the whole problem. Two models of a submarine force are presented. The first deals with the construction and major refit programmes, to evaluate the periods of fleet service availability achievable from a submarine force of a given size. The second examines unit usage during periods of fleet service.     

Linear programming insights into solvable cases of the quadratic assignment problem

The quadratic assignment problem is an NP-hard discrete optimization program that has been extensively studied for over 50 years. It has a variety of applications in many fields, but has proven itself extremely challenging to solve. As a result, an area of research has been to identify special cases which admit efficient solution strategies. This paper examines four such cases, and shows how each can be explained in terms of the dual region to the continuous relaxation of a classical linear reformulation of the problem known as the level-1 RLT representation. The explanations allow for simplifications and/or generalizations of the conditions defining the special cases.     

Algorithm for min-range multiplication of affine forms

We consider an approximate method based on the alternate trapezoidal quadrature for the eigenvalue problem given by a periodic singular Fredholm integral equation of second kind. For some convolution-type integral kernels, the eigenvalues of the discrete eigenvalue problem provided by the alternate trapezoidal quadrature method have multiplicity at least two, except up to two eigenvalues of multiplicity one. In general, these eigenvalues exhibit some symmetry properties that are not necessarily observed in the eigenvalues of the continuous problem. For a class of Hilbert-type kernels, we provide error estimates that are valid for a subset of the discrete spectrum. This subset is further enlarged in an improved quadrature method presented herein. The results are illustrated through numerical examples.     

Optimizing Bernoulli Routing Policies for Balancing Loads on Call Centers and Minimizing Transmission Costs

We address the problem of assigning probabilities at discrete time instants for routing toll-free calls to a given set of call centers to minimize a weighted sum of transmission costs and load variability at the call centers during the next time interval.We model the problem as a tripartite graph and decompose the finding of an optimal probability assignment in the graph into the following problems: (i) estimating the true arrival rates at the nodes for the last time period; (ii) computing routing probabilities assuming that the estimates are correct. We use a simple approach for arrival rate estimation and solve the routing probability assignment by formulating it as a convex quadratic program and using the affine scaling algorithm to obtain an optimal solution.We further address a practical variant of the problem that involves changing routing probabilities associated with k nodes in the graph, where k is a prespecified number, to minimize the objective function. This involves deciding which k nodes to select for changing probabilities and determining the optimal value of the probabilities. We solve this problem using a heuristic that ranks all subsets of k nodes using gradient information around a given probability assignment.The routing model and the heuristic are evaluated for speed of computation of optimal probabilities and load balancing performance using a Monte Carlo simulation. Empirical results for load balancing are presented for a tripartite graph with 99 nodes and 17 call center gates.