-
作者：Puerto, J; Tamir, A
作者单位：University of Sevilla; Tel Aviv University
摘要：In this paper we consider the location of a tree-shaped facility Son a tree network, using the ordered median function of the weighted distances to represent the total transportation cost objective. This function unifies and generalizes the most common criteria used in location modeling, e.g., median and center. If there are n demand points at the nodes of the tree T = (V, E), this function is characterized by a sequence of reals, Lambda = (lambda(1),...,lambda(n)), satisfying lambda(1) >= lam...
-
作者：Meyer, CA; Floudas, CA
作者单位：Princeton University
摘要：Deterministic global optimization algorithms frequently rely on the convex underestimation of nonconvex functions. In this paper we describe the structure of the polyhedral convex envelopes of edge-concave functions over polyhedral domains using geometric arguments. An algorithm for computing the facets of the convex envelope over hyperrectangles in R-3 is described. Sufficient conditions are described under which the convex envelope of a sum of edge-concave functions may be shown to be equiva...
-
作者：Tawarmalani, M; Sahinidis, NV
作者单位：Purdue University System; Purdue University; University of Illinois System; University of Illinois Urbana-Champaign
摘要：A variety of nonlinear, including semidefinite, relaxations have been developed in recent years for nonconvex optimization problems. Their potential can be realized only if they can be solved with sufficient speed and reliability. Unfortunately, state-of-the-art nonlinear programming codes are significantly slower and numerically unstable compared to linear programming software. In this paper, we facilitate the reliable use of nonlinear convex relaxations in global optimization via a polyhedra...
-
作者：Ramaswamy, R; Orlin, JB; Chakravarti, N
作者单位：Infosys Limited; Massachusetts Institute of Technology (MIT)
摘要：This paper addresses sensitivity analysis questions concerning the shortest path problem and the maximum capacity path problem in an undirected network. For both problems, we determine the maximum and minimum weights that each edge can have so that a given path remains optimal. For both problems, we show how to determine these maximum and minimum values for all edges in O(m + K log K) time, where m is the number of edges in the network, and K is the number of edges on the given optimal path.
