Computing the variance of tour costs over the solution space of the TSP in polynomial time

We give an O(n ²) time algorithm to find the population variance of tour costs over the solution space of the n city symmetric Traveling Salesman Problem (TSP). The algorithm has application in both the stochastic case, where the problem is specified in terms of edge costs which are pairwise independently distributed random variables with known mean and variance, and the numeric edge cost case. We apply this result to provide empirical evidence that, in a range of real world problem sets, the optimal tour cost correlates with a simple function of the mean and variance of tour costs.     

Time optimal sampled-data controls for the heat equation

In this paper, we first design a time optimal control problem for the heat equation with sampled-data controls, and then use it to approximate a time optimal control problem for the heat equation with distributed controls.The study of such a time optimal sampled-data control problem is not easy, because it may have infinitely many optimal controls. We find connections among this problem, a minimal norm sampled-data control problem and a minimization problem, and obtain some properties on these problems. Based on these, we not only build up error estimates for optimal time and optimal controls between the time optimal sampled-data control problem and the time optimal distributed control problem, in terms of the sampling period, but we also prove that such estimates are optimal in some sense.     

Piecewise optimal distributed Controls for 2D Boussinesq equations

In this article, we study the dynamics of a piecewise (in time) distributed optimal control problem for the Boussinesq equations which model velocity tracking over time coupled to thermal dynamics. We also study the dynamics of semidiscrete approximation of this problem. We prove that the rates of velocity tracking coupled to thermal dynamics are exponential and that the difference between the solution of the semi‐discrete piecewise optimal control problem and the desired states in L² and H¹ norms decay to zero exponentially as n→∞. Copyright © 2000 John Wiley & Sons, Ltd.     

A Mixed Linear Quadratic Optimal Control Problem with a Controlled Time Horizon

A mixed linear quadratic (MLQ) optimal control problem is considered. The controlled stochastic system consists of two diffusion processes which are in different time horizons. There are two control actions: a standard control action \(u(\cdot )\) enters the drift and diffusion coefficients of both state equations, and a stopping time \(\tau \) , a possible later time after the first part of the state starts, at which the second part of the state is initialized with initial condition depending on the first state. A motivation of MLQ problem from a two-stage project management is presented. It turns out that solving an MLQ problem is equivalent to sequentially solve a random-duration linear quadratic (RLQ) problem and an optimal time (OT) problem associated with Riccati equations. In particular, the optimal cost functional can be represented via two coupled stochastic Riccati equations. Some optimality conditions for MLQ problem is therefore obtained using the equivalence among MLQ, RLQ and OT problems. In case of seeking the optimal time in the family of deterministic times (even through somewhat restrictive, such seeking is still reasonable from practical standpoint), we give a more explicit characterization of optimal actions.     

Error estimates for three-dimensional Stokes problem with non-standard boundary conditions

This work is devoted to the optimal and a posteriori error estimates of the Stokes problem with some non-standard boundary conditions in three dimensions. The variational formulation is decoupled into a system for the velocity and a Poisson equation for the pressure. The velocity is approximated with curl conforming finite elements and the pressure with standard continuous elements. Next, we establish optimal a posteriori estimates.     

Asymptotically optimal idling in the GI/GI/N+GI queue

We formulate a control problem for a GI/GI/N+GI queue, whose objective is to trade off the long-run average operational costs with server utilization costs. To solve the control problem, we consider an asymptotic regime in which the arrival rate and the number of servers grow large. The solution to an associated fluid control problem motivates that non-idling service disciplines are not in general optimal, unless some arrivals are turned away. We propose an admission control policy designed to ensure that servers have sufficient idle time, which we show is asymptotically optimal.     

Reformulation and solution approach for non-separable integer quadratic programs

We consider quadratic programs with pure general integer variables. The objective function is quadratic and convex and the constraints are linear. An exact solution approach is proposed. It is decomposed into two phases. In the first phase, the initial problem is reformulated into an equivalent problem with a separable objective function. This is done by use of a Gauss decomposition of the Hessian matrix of the initial problem and requires the addition of some continuous variables and constraints. In the second phase, the reformulated problem is linearized by an approximation of each squared term by a set of K linear functions that correspond to the tangents of a hyperbola in K points. We give a proof of the intuitive property that when K is large enough, the optimal value of the obtained linear program is very close to optimal value of the two previous problems, the initial problem and the reformulated separable problem. The reminder is dedicated to the implementation of a branch-and-bound algorithm for the solution of linearized problem, and its application to a set of instances. Several points are considered among which choice of the right value for parameter K and the implementation of a sophisticated heuristic solution algorithm. The numerical comparison is done with CPLEX 12.2 since, in this case, the initial problem as well as the problem reformulated by the first step can be solved by CPLEX. We show that with our approach, the total CPU time is divided by a factor ranging from 1.2 to 131.6 for instances with 40–60 variables.     

Single machine common flow allowance scheduling with controllable processing times

In this paper, we consider single machine SLK due date assignment scheduling problem in which job processing times are controllable variables with linear costs. The objective is to determine the optimal sequence, the optimal common flow allowance and the optimal processing time compressions to minimize a total penalty function based on earliness, tardiness, common flow allowance and compressions. We solve the problem by formulating it as an assignment problem which is polynomially solvable. For some special cases, we present an O(n logn) algorithm to obtain the optimal solution respectively.     

A boundary parametric approximation to the linearized scalar potential magnetostatic field problem

We consider the linearized scalar potential formulation of the magnetostatic field problem in this paper. Our approach involves a reformulation of the continuous problem as a parametric boundary problem. By the introduction of a spherical interface and the use of spherical harmonics, the infinite boundary conditions can also be satisfied in the parametric framework. That is the field in the exterior of a sphere is expanded in a ‘harmonic series’ of eigenfunctions for the exterior harmonic problem. The approach is essentially a finite element method coupled with a spectral method via a boundary parametric procedure. The reformulated problem is discretized by finite element techniques which leads to a discrete parametric problem which can be solved by well conditioned iteration involving only the solution of decoupled Neumann type elliptic finite element systems and L² projection onto subspaces of spherical harmonics. Error and stability estimates given show exponential convergence in the degree of the spherical harmonics and optimal order convergence with respect to the finite element approximation for the resulting fields in L².     

On coupled Boltzmann transport equation related to radiation therapy

We consider a system of Boltzmann transport equations which models the charged particle evolution in media. The system is related to the dose calculation in radiation therapy. Although only one species of particles, say photons is invasing these particles mobilize other type of particles (electrons and positrons). Hence in realistic modelling of particle transport one needs a coupled system of three Boltzmann transport equations. The solution of this system must satisfy the inflow boundary condition. We show existence and uniqueness result of the solution applying generalized Lax-Milgram Theorem. In addition, we verify that (in the case of external therapy) under certain assumptions the “incoming flux to dose operator” D₁ is compact. Also the adjoint is analyzed. Finally we consider the inverse planning problem as an optimal control problem. Its solution can be used as an initial solution of the actual inverse planning problem.     

Formulations and Benders decomposition algorithms for multidepot salesmen problems with load balancing

This paper describes new models and exact solution algorithms for the fixed destination multidepot salesmen problem defined on a graph with n nodes where the number of nodes each salesman is to visit is restricted to be in a predefined range. Such problems arise when the time to visit a node takes considerably longer as compared to the time of travel between nodes, in which case the number of nodes visited in a salesman’s tour is the determinant of their ‘load’. The new models are novel multicommodity flow formulations with O(n²) binary variables, which is contrary to the existing formulations for the same (and similar) problems that typically include O(n³) binary variables. The paper also describes Benders decomposition algorithms based on the new formulations for solving the problem exactly. Results of the computational experiments on instances derived from TSPLIB show that some of the proposed algorithms perform remarkably well in cases where formulations solved by a state-of-the-art optimization code fail to yield optimal solutions within reasonable computation time.     

A distributed Douglas-Rachford splitting method for multi-block convex minimization problems

A customized Douglas-Rachford splitting method (DRSM) was recently proposed to solve two-block separable convex optimization problems with linear constraints and simple abstract constraints. The algorithm has advantage over the well-known alternating direction method of multipliers (ADMM), the dual application of DRSM to the two-block convex minimization problem, in the sense that the subproblems can have larger opportunity of possessing closed-form solutions since they are unconstrained. In this paper, we further study along this way by considering the primal application of DRSM for the general case m≥3, i.e., we consider the multi-block separable convex minimization problem with linear constraints where the objective function is separable into m individual convex functions without coupled variables. The resulting method fully exploits the separable structure and enjoys decoupled subproblems which can be solved simultaneously. Both the exact and inexact versions of the new method are presented in a unified framework. Under mild conditions, we manage to prove the global convergence of the algorithm. Preliminary numerical experiments for extracting the background from corrupted surveillance video verify the encouraging efficiency of the new algorithm.     

Optimal cubature formulas for tensor products of certain classes of functions

We study the problem of constructing an optimal formula of approximate integration along a d-dimensional parallelepiped. Our construction utilizes mean values along intersections of the integration domain with n hyperplanes of dimension (d−1), each of which is perpendicular to some coordinate axis. We find an optimal cubature formula of this type for two classes of functions. The first class controls the moduli of continuity with respect to all variables, whereas the second class is the intersection of certain periodic multivariate Sobolev classes. We prove that all node hyperplanes of the optimal formula in each case are perpendicular to a certain coordinate axis and are equally spaced and the weights are equal. For specific moduli of continuity and for sufficiently large n, the formula remains optimal for the first class among cubature formulas with arbitrary positions of hyperplanes.     

Single machine scheduling problems with controllable processing times and total absolute differences penalties

In this paper, we consider single machine scheduling problem in which job processing times are controllable variables with linear costs. We concentrate on two goals separately, namely, minimizing a cost function containing total completion time, total absolute differences in completion times and total compression cost; minimizing a cost function containing total waiting time, total absolute differences in waiting times and total compression cost. The problem is modelled as an assignment problem, and thus can be solved with the well-known algorithms. For the case where all the jobs have a common difference between normal and crash processing time and an equal unit compression penalty, we present an O(n log n) algorithm to obtain the optimal solution.     

Optimal on-line flow time with resource augmentation

We study the problem of scheduling n jobs that arrive over time. We consider a non-preemptive setting on a single machine. The goal is to minimize the total flow time. We use extra resource competitive analysis: an optimal off-line algorithm which schedules jobs on a single machine is compared to a more powerful on-line algorithm that has ? machines. We design an algorithm of competitive ratio , where Δ is the maximum ratio between two job sizes, and provide a lower bound which shows that the algorithm is optimal up to a constant factor for any constant ?. The algorithm works for a hard version of the problem where the sizes of the smallest and the largest jobs are not known in advance, only Δ and n are known. This gives a trade-off between the resource augmentation and the competitive ratio.We also consider scheduling on parallel identical machines. In this case the optimal off-line algorithm has m machines and the on-line algorithm has ?m machines. We give a lower bound for this case. Next, we give lower bounds for algorithms using resource augmentation on the speed. Finally, we consider scheduling with hard deadlines, and scheduling so as to minimize the total completion time.     

Generalized H ∞-optimal filtering under external and initial perturbations

We consider the problem of optimal filtering of unmeasured variables of a linear dynamical system by linear stationary filters. The filtering performance functional to be minimized is given by the maximum relative integral filtering error over all external perturbations as well as initial perturbations caused by the unknown initial conditions of the system. We show that the optimal filter implements a trade-off between an H _∞-optimal filter and a minimax observer.     

One‐level and two‐level finite element methods for the Boussinesq problem

Previous works on the convergence of numerical methods for the Boussinesq problem were conducted, while the optimal L²‐norm error estimates for the velocity and temperature are still lacked. In this paper, the backward Euler scheme is used to discrete the time terms, standard Galerkin finite element method is adopted to approximate the variables. The MINI element is used to approximate the velocity and pressure, the temperature field is simulated by the linear polynomial. Under some restriction on the time step, we firstly present the optimal L² error estimates of approximate solutions. Secondly, two‐level method based on Stokes iteration for the Boussinesq problem is developed and the corresponding convergence results are presented. By this method, the original problem is decoupled into two small linear subproblems. Compared with the standard Galerkin method, the two‐level method not only keeps good accuracy but also saves a lot of computational cost. Finally, some numerical examples are provided to support the established theoretical analysis.     

Parametric approach to optimal control

We consider the optimal control problem from view point of parametric aspects. We have examined two cases of the parameterized problems. First case describes the situation when the objective functional contains time t as a parameter. We also show how to apply the parametric optimization techniques, such as pathfollowing methods, for finding a nominal optimal control path.     

David G. Luenberger,Linear and nonlinear programming, 2nd edition,Addison-Wesley,Reading (1984), xv + 492 pages, $35.50

This paper considers a stochastic version of the linear continuous type knapsack problem in which the cost coefficients are random variables. The problem is to find an optimal solution and an optimal probability level of the chance constraint. This problem P₀ is first transformed into a deterministic equivalent problem P. Then a subproblem with a positive parameter is introduced and a close relation between P and its subproblem is shown. Further, an auxiliary problem of the subproblem is introduced and a direct relation between P and the auxiliary problem is derived through a relation connecting the subproblem and its auxiliary problem. Fully utilizing these relations, an efficient algorithm is proposed that finds an optimal solution of P in at most O(n⁴) computational time where n is the number of decision variables. Finally, further research problems are discussed.     

Optimal recovery of isotropic classes of rth differentiable multivariate functions

Estimates are given for the optimal recovery of functions in d variables, which are known to have (r?1)st absolutely continuous and rth bounded derivatives in any direction over, either a bounded convex d-dimensional body G, or which are periodic over a d dimensional lattice. The information is the values of the function and all its derivatives of order less than r at n points. We obtain some asymptotic estimates for this problem, and some exact results for several special cases which contain the results of Babenko, Borodachov, and Skorokhodov.