Convex Optimization 2026, 35 - Placement and Location

A placement problem describes a situation where N points in ℝ² or ℝ³ are pairwise connected by links, and some subset of N is fixed. The remaining places are then meant to be placed in that graph in a way that satisfies some constraints (p. 432). This includes the family of linear facility location problems where the cost is associated with the distance between nodes. These arcs can be weighed for a more sophisticated version (8.7.1). Constraints can be applied to the placements directly in a way that preserves convexity. This is usually done using some bounding box. As long as the box is convex, so is the problem (8.7.2). More generally, each arc's cost could be weighed with a nonlinear increasing function of the length, so that this nonlinear placement problem minimizes ∑_{i<j< data-preserve-html-node="true"/sub>wijh(||xi - xj||) where h is an increasing and convex function and the weight w is non-negative (8.7.3). A p-link path along the points x1, ..., xN is described by a sequence of nodes, and the length of the path is given by a convex function. We consider a directed acyclic graph with nodes 1, ..., N and arcs. A node i is a source node if no arc points to it, and a sink node if no arc leaves from it. The paths of interest are those with source and sink node. The minimax delay placement problem has some node locations as fixed, and the free node locations are optimized to minimize or maximize the total delay for any path from a source node to a sink node (8.7.4).}