双会议服务器选址问题研究

中位选址问题一直是管理学科的研究热点,本文考虑平面点集选址问题中的双会议服务器选址问题,该问题可以看成是2中位问题的衍生问题。令P为平面上包含n个点的点集,双会议服务器选址问题即为寻找由该点集构成的一棵二星树,使得这棵树上所有叶子之间的距离和最小。本文给出求解该问题的关键几何结构和最优解算法设计,并证明所给算法时间复杂性为O(n³logn)。     

设施选址问题的近似算法综述

设施选址问题是运筹学和理论计算机科学中的经典问题之一.本文介绍设施选址问题及其变形的近似算法设计与分析思想,并总结设施选址问题的研究中若干未解决的重要问题.     

两个逆网络选址问题的计算复杂性

本文考虑两个我们称之为逆网络选址的改进问题,它们是修改网络上各个边的长度,分别使得网络上某个给定的顶点到网络上所有点的最大距离以及该点到其它顶点的距离之和不大于预先给定的上界,并且所做的修改总量最小.我们将证明这两个逆网络选址问题都是强NP困难的.     

一类多商品设施选址问题的基于线性松弛解的启发式方法

多商品设施选址问题是众多设施选址问题中一类重要而困难的问题.在这一问题中,顾客的需求可能包含不止一种商品.对于大规模问题,成熟的商业求解器往往不能在满意的时间内找到高质量的可行解.研究了无容量限制的单货源多商品设施选址问题的一般形式,并给出了应用于此类问题的两个启发式方法.这两个方法基于原选址问题的线性规划松弛问题的最优解,分别通过求解紧问题和邻域搜索的方式给出了原问题的一个可行上界.理论分析指出所提方法可以实施于任意可行问题的实例.数值结果表明所提方法可以显著地提高求解器求解此类设施选址问题的求解效率.     

一类带单源约束的选址运输问题算法研究

带单源约束的选址运输问题是在经典的选址运输问题基础上考虑每个顾客需求的产品仅由一家工厂供应的情况。所建立的模型是整数规划，是NP难的。本文先考虑了开办费用为零的带单源约束的选址运输问题，即带单源约束的运输问题。松弛其中一种变量约束，借鉴求解运输问题的表上作业法，给出了一种修正的表上作业法，然后将算法推广。最后给出了将算法应用在Excel随机生成的测试问题上所得到的结果，与LINDO求得的最优解相比，差距很小。由此得出结论：对规模较小的带单源约束的选址运输问题，本文提出的算法是简便且行之有效的。     

平方度量动态设施选址问题的近似算法

研究了单阶段度量设施选址问题的推广问题平方度量动态设施选址问题.研究中首先利用原始对偶技巧得到9-近似算法,然后利用贪婪增广技巧将近似比改进到2.606,最后讨论了该问题的相应变形问题.     

鲁棒动态设施选址问题的近似算法

设施选址问题是组合优化中重要问题之一。动态设施选址问题是传统设施选址问题的推广,其中度量空间中设施的开设费用和顾客的需求均随着时间的变化而变化。更多地,经典设施选址问题假设所有的顾客都需要被服务。在这个模型假设下,所有的顾客都需要服务。但事实上,有时为服务距离较远的顾客,需要单独开设设施,导致了资源的浪费。因此,在模型设置中,可以允许一些固定数目的顾客不被服务 (带异常点的设施选址问题),此外也可以通过支付一些顾客的惩罚费用以达到不服务的目的 (带惩罚的设施选址问题)。本文将综合以上两种鲁棒设置考虑同时带有异常点和惩罚的动态设施选址问题,通过原始-对偶框架得到近似比为3的近似算法。     

区间图上可带负权的2-中位选址问题（英文）

Abstract本文研究了区间图上可带负权的2-中位选址问题.根据目标函数的不同,可带负权的p-中位选址问题（p≥2）可分为两类：即MWD和WMD模型;前者是所有顶点与服务该顶点的设施之间的最小权重距离之和,后者是所有顶点与相应设施之间的权重最小距离之和.在本篇论文中,我们讨论了区间图上可带负权2-中位选址问题的两类模型,并分别设计时间复杂度为O（n~2）的多项式时间算法.     

离散设施选址问题研究综述

本文首先回顾了设施选址问题百年发展历史,认为其研究经历了零散研究、系统研究、不确定性研究三个阶段.离散选址问题包括中值问题、覆盖问题、中心问题、多产品问题、动态问题、多目标问题、路径选址问题、网络中心选址问题8个子问题.最后作者讨论了选址问题研究中存在的问题以及今后发展的趋势.     

基于一类光滑函数法求解选址问题

选址问题是组合优化中一类有着重要理论意义和广泛实际背景的问题.在利用数学模型解决这类问题时经常会遇到非线性L_1问题,也就是不可微优化问题.为了解决这类问题,构造了适合于选址问题的一类新的光滑函数,并对这类光滑函数进行了性质描述,然后在此基础上提出了基于有效集法进行优化求解的计算步骤.最后,以实例证明了这类光滑函数应用在选址问题的优化求解上是有效的.     

Integer linear programming models for grid-based light post location problem

Selecting optimal location is a key decision problem in business and engineering. This research focuses to develop mathematical models for a special type of location problems called grid-based location problems. It uses a real-world problem of placing lights in a park to minimize the amount of darkness and excess supply. The non-linear nature of the supply function (arising from the light physics) and heterogeneous demand distribution make this decision problem truly intractable to solve. We develop ILP models that are designed to provide the optimal solution for the light post problem: the total number of light posts, the location of each light post, and their capacities (i.e., brightness). Finally, the ILP models are implemented within a standard modeling language and solved with the CPLEX solver. Results show that the ILP models are quite efficient in solving moderately sized problems with a very small optimality gap.     

GASUB: finding global optima to discrete location problems by a genetic-like algorithm

In many discrete location problems, a given number s of facility locations must be selected from a set of m potential locations, so as to optimize a predetermined fitness function. Most of such problems can be formulated as integer linear optimization problems, but the standard optimizers only are able to find one global optimum. We propose a new genetic-like algorithm, GASUB, which is able to find a predetermined number of global optima, if they exist, for a variety of discrete location problems. In this paper, a performance evaluation of GASUB in terms of its effectiveness (for finding optimal solutions) and efficiency (computational cost) is carried out. GASUB is also compared to MSH, a multi-start substitution method widely used for location problems. Computational experiments with three types of discrete location problems show that GASUB obtains better solutions than MSH. Furthermore, the proposed algorithm finds global optima in all tested problems, which is shown by solving those problems by Xpress-MP, an integer linear programing optimizer (21). Results from testing GASUB with a set of known test problems are also provided.     

When are NP-hard location problems easy?

We discuss in this paper several location problems for which it is an NP-hard problem to find an approximate solution. Given certain assumptions on the input distributions, we present polynomial algorithms that deliver a solution asymptotically close to the optimum with probability that is asymptotically one (the exact nature of this asymptotic convergence is described in the paper). In that sense the subproblems defined on the specified family of inputs are in fact easy.This research was supported in part by the National Science Foundation under grant ECS-8204695.     

Helly’s Principle and Its Application to an Infinite-Horizon Optimal Control Problem

In this paper, a numerical method is presented to solve singularly-perturbed two-point boundary-value problems for second-order ordinary differential equations with a discontinuous source term. First, an asymptotic expansion approximation of the solution of the boundary-value problem is constructed using the basic ideas of the well-known WKB perturbation method. Then, some initial-value problems and terminal-value problems are constructed such that their solutions are the terms of this asymptotic expansion. These initial-value problems and terminal-value problems are singularly-perturbed problems and therefore fitted mesh method (Shishkin mesh) are used to solve these problems. Necessary error estimates are derived and examples are provided to illustrate the method.     

Simple dynamic location problem with uncertainty: a primal-dual heuristic approach

Abstract

In this paper, the simple dynamic facility location problem is extended to uncertain realizations of the potential locations for facilities and the existence of customers as well as fixed and variable costs. With limited knowledge about the future, a finite and discrete set of scenarios is considered. The decisions to be made are where and when to locate the facilities, and how to assign the existing customers over the whole planning horizon and under each scenario, in order to minimize the expected total costs. Whilst assignment decisions can be scenario dependent, location decisions have to take into account all possible scenarios and cannot be changed according to each scenario in particular. We first propose a mixed linear programming formulation for this problem and then we present a primal-dual heuristic approach to solve it. The heuristic was tested over a set of randomly generated test problems. The computational results are provided.     

Generalized Symmetric Vector Quasiequilibrium Problems

We establish an existence result for scalar quasiequilibrium problems without any continuity requirement on noncompact subsets of locally convex topological vector spaces. As a consequence, we obtain a solution of symmetric scalar quasiequilibrium problem. Moreover, using a so-called nonlinear scalarization function, existence theorems for vector quasiequilibrium problems and general symmetric vector quasiequilibrium problems are obtained. The authors express their sincere gratitude to the referee for valuable comments and suggestions. This research was in part supported by a grant from IPM (No. 86470016) and the Center of Excellence for Mathematics, University of Isfahan.     

Nondifferentiability Detection and Dimensionality Reduction in Minisum Multifacility Location Problems

The minisum multifacility location problem is regarded as hard to solve, due to nondifferentiabilities whenever two or more facilities coincide. Recently, several authors have published conditions for the coincidence of facilities. In the present paper, these conditions are extended to more general location problems and improved with respect to new sufficient coincidence conditions for location problems with mixed asymmetric gauges. Some of these conditions are formulated only in terms of the given weights and certain values from a preprocessing step.     

A memetic algorithm for multi-objective dynamic location problems

This paper describes a new multiobjective interactive memetic algorithm applied to dynamic location problems. The memetic algorithm integrates genetic procedures and local search. It is able to solve capacitated and uncapacitated multi-objective single or multi-level dynamic location problems. These problems are characterized by explicitly considering the possibility of a facility being open, closed and reopen more than once during the planning horizon. It is possible to distinguish the opening and reopening periods, assigning them different coefficient values in the objective functions. The algorithm is part of an interactive procedure that asks the decision maker to define interesting search areas by establishing limits to the objective function values or by indicating reference points. The procedure will be applied to some illustrative location problems.     

A special class of extended multicriteria location problems

This paper is devoted to the study of extended multicriteria location problems, which are obtained from a given planar single-facility multicriteria location problem with respect to the maximum norm by adding new cost functions. By means of an appropriate decomposition approach, we develop an implementable algorithm for generating an efficient solution of such extended problems.