Combinatorial aspects of the sensor location problem

In this paper we address the Sensor Location Problem, that is the location of the minimum number of counting sensors, on the nodes of a network, in order to determine the arc flow volume of all the network. Despite the relevance of the problem from a practical point of view, there are very few contributions in the literature and no combinatorial analysis is performed to take into account particular structure of the network. We prove the problem is -complete in different cases. We analyze special classes of graphs that are particularly interesting from an application point of view, for which we give low order polynomial solution algorithms.     

p-Hub approach for the optimal park-and-ride facility location problem

Park and Ride facilities (P&R) are car parks at which users can transfer to public transportation to reach their final destination. We propose a mixed linear programming formulation to determine the location of a fixed number of P&R facilities so that their usage is maximized. The facilities are modeled as hubs. Commuters can use one of the P&R facilities or choose to travel by car to their destinations, and their behavior follows a logit model. We apply a p-hub approach considering that users incur in a known generalized cost of using each P&R facility as input for the logit model. For small instances of the problem, we propose a novel linearization of the logit model, which allows transforming the binary nonlinear programming problem into a mixed linear programming formulation. A modification of the Heuristic Concentration Integer (HCI) procedure is applied to solve larger instances of the problem. Numerical experiments are performed, including a case in Queens, NY. Further research is proposed.     

On the uniqueness of optimal solutions in continuous location theory

This paper deals with the uniqueness of an optimal solution in general continuous single facility minisum and minimax location problems. We define the concept of an S-norm and obtain general conditions which guarantee the existence of a unique optimal location. Some consequences for the uniqueness of optimal locations in multi-facility location problems are discussed.     

Stability of solutions in optimal reinsurance problem

A discrete-time insurance model with stop-loss reinsurance is considered. One-period insurance claims form a sequence of independent identically distributed nonnegative random variables with finite mean. The insurer maintains the company surplus above a chosen level a by capital injections. We study the stability of optimal capital injections to the variability of claims distribution. The term “optimal” means the minimal amount of injections that can be found from the corresponding Bellman equation.     

On the expected number of optimal and near-optimal solutions to the Euclidean travelling salesman problem

An algorithm for empirically calculating the expected number of optimal and near-optimal solutions in a random Euclidean travelling salesman problem is presented. The algorithm is based on well known geometric properties of the optimal tour. For problems involving up to 15 points uniformily distributed in the unit square, experiments show this expected number to be extremely small.     

On the empirical scaling of run-time for finding optimal solutions to the travelling salesman problem

The travelling salesman problem (TSP)   is one of the most prominent NP-hard combinatorial optimisation problems. After over fifty years of intense study, the TSP continues to be of broad theoretical and practical interest. Using a novel approach to empirical scaling analysis, which in principle is applicable to solvers for many other problems, we demonstrate that some of the most widely studied types of TSP instances tend to be much easier than expected from previous theoretical and empirical results. In particular, we show that the empirical median run-time required for finding optimal solutions to so-called random uniform Euclidean (RUE) instances – one of the most widely studied classes of TSP instances – scales substantially better than Θ(2ⁿ)$\Theta (2^n)$ with the number n of cities to be visited. The Concorde solver, for which we achieved this result, is the best-performing exact TSP solver we are aware of, and has been applied to a broad range of real-world problems. Furthermore, we show that even when applied to a broad range of instances from the prominent TSPLIB benchmark collection for the TSP, Concorde exhibits run-times that are surprisingly consistent with our empirical model of Concorde’s scaling behaviour on RUE instances. This result suggests that the behaviour observed for the simple random structure underlying RUE is very similar to that obtained on the structured instances arising in various applications.     

指派问题的多重最优解的择优方法

在某些情况下,经典指派问题的最优解不唯一．不同的最优解对参与人的影响不同,导致每个参与人会争取最有利于自身的最优解．为解决这个问题,通过研究允许合作指派问题的合作对策解的形成,提出允许合作指派问题的讨价还价模型和个体理性激励函数．在此基础上,提出了一个考虑个体理性的指派问题多重最优解的择优方法,从而保证了指派问题最优解的唯一性．     

Closed-form solutions of a general inequality-constrained lq optimal control problem

A general linear quadratic (LQ) optimal control problem, with the dynamic system being governed by a higher-order vector-valued ordinary differential equation and with inequality-constraints on the state vector and/or the control input, is studied. Based on an explicit characterization result, optimal solutions are obtained in closed-form. A constructive method for finding the closed-form optimal solutions is proposed, and two illustrative examples are included     

An optimal boundary control problem for the motion equations of polymer solutions

We study an optimal boundary control problem for stationary equations of a model of the motion of weakly concentrated water solutions of polymers. Sufficient conditions are obtained for the solvability of the problem. Some properties of the set of optimal solutions are established.     

Stability analysis of the Pareto optimal solutions for some vector boolean optimization problem

In this article we consider the boolean optimization problem of finding the set of Pareto optimal solutions. The vector objectives are the positive cuts of linear functions to the non-negative semi-axis. Initial data are subject to perturbations, measured by the l ₁-norm in the parameter space of the problem. We present the formula expressing the extreme level (stability radius) of such perturbations, for which a particular solution remains Pareto optimal.     

On solutions to the Goldshtik problem

The Goldshtik model for separated flows in an incompressible fluid is considered. A solution to this two-dimensional problem of mathematical physics for a finite domain is found with a finite element method. Estimates of the differential operator are obtained. A result on the number of solutions to the Goldshtik problem is obtained using a variational method.     

Compactness of solutions to the Yamabe problem

We establish compactness of solutions to the Yamabe problem on any smooth compact connected Riemannian manifold (not conformally diffeomorphic to standard spheres) of dimension n?7 as well as on any manifold of dimension n?8 under some additional hypothesis. To cite this article: Y.Y. Li, L. Zhang, C. R. Acad. Sci. Paris, Ser. I 338 (2004).     

On optimal solutions of general continuous-singular stochastic control problem of McKean-Vlasov type

In this paper, we establish general necessary optimality conditions for stochastic continuous-singular control of McKean-Vlasov type equations. The coefficients of the state equation depend on the state of the solution process as well as of its probability law and the control variable. The coefficients of the system are nonlinear and depend explicitly on the absolutely continuous component of the control. The control domain under consideration is not assumed to be convex. The proof of our main result is based on the first- and second-order derivatives, with respect to measure in Wasserstein space of probability measures, and by using variational method.     

Sequential location of two facilities: comparing random to optimal location of the first facility

We review our recent results in the development of optimal algorithms for the minimization of a strictly convex quadratic function subject to separable convex inequality constraints and/or linear equality constraints. A unique feature of our algorithms is the theoretically supported bound on the rate of convergence in terms of the bounds on the spectrum of the Hessian of the cost function, independent of representation of the constraints. When applied to the class of convex QP or QPQC problems with the spectrum in a given positive interval and a sparse Hessian matrix, the algorithms enjoy optimal complexity, i.e., they can find an approximate solution at the cost that is proportional to the number of unknowns. The algorithms do not assume representation of the linear equality constraints by full rank matrices. The efficiency of our algorithms is demonstrated by the evaluation of the projection of a point to the intersection of the unit cube and unit sphere with hyperplanes.     

Regularity of solutions for an optimal control problem with mixed control-state constraints

A class of optimal control problems for a semilinear elliptic partial differential equation with mixed control-state constraints is considered. Existence results of an optimal control and necessary optimality conditions are stated. Moreover, a projection formula is derived that is equivalent to the necessary optimality conditions. As main result, the Lipschitz continuity of the optimal control is obtained.     

Pareto optimal solutions of a cost–time trade-off bulk transportation problem

A cost–time trade-off bulk transportation problem with the objectives to minimize the total cost and duration of bulk transportation without according priorities to them is considered. The entire requirement of each destination is to be met from one source only; however a source can supply to any number of destinations subject to the availability of the commodity at it. Two new algorithms are provided to obtain the set of Pareto optimal solutions of this problem. This work extends and generalizes the work related to single-objective and prioritized two-objective bulk transportation problems done in the past while providing flexibility in decision making.