A mixed integer programming formulation for the 1-maximin problem

In this paper, I present a mixed integer programming (MIP) formulation for the 1-maximin problem with rectilinear distance. The problem mainly appears in facility location while trying to locate an undesirable facility. The rectilinear distance is quite commonly used in the location literature. Our numerical experiments show that one can solve reasonably large location problems using a standard MIP solver. We also provide a linear programming formulation that helps find an upper bound on the objective function value of the 1-maximin problem with any norm when extreme points of the feasible region are known. We discuss various extension alternatives for the MIP formulation.     

Mixed integer programming-based solution procedure for single-facility location with maximin of rectilinear distance

In this paper, we study the 1-maximin problem with rectilinear distance. We locate a single undesirable facility in a continuous planar region while considering the interaction between the facility and existing demand points. The distance between facility and demand points is measured in the rectilinear metric. The objective is to maximize the distance of the facility from the closest demand point. The 1-maximin problem has been formulated as an MIP model in the literature. We suggest new bounding schemes to increase the solution efficiency of the model as well as improved branch and bound strategies for implementation. Moreover, we simplify the model by eliminating some redundant integer variables. We propose an efficient solution algorithm called cut and prune method, which splits the feasible region into four equal subregions at each iteration and tries to eliminate subregions depending on the comparison of upper and lower bounds. When the sidelengths of the subregions are smaller than a predetermined value, the improved MIP model is solved to obtain the optimal solution. Computational experiments demonstrate that the solution time of the original MIP model is reduced substantially by the proposed solution approach.     

Two-Dimensional Solution Surface for Weighted Support Vector Machines

The support vector machine (SVM) is a popular learning method for binary classification. Standard SVMs treat all the data points equally, but in some practical problems it is more natural to assign different weights to observations from different classes. This leads to a broader class of learning, the so-called weighted SVMs (WSVMs), and one of their important applications is to estimate class probabilities besides learning the classification boundary. There are two parameters associated with the WSVM optimization problem: one is the regularization parameter and the other is the weight parameter. In this article, we first establish that the WSVM solutions are jointly piecewise-linear with respect to both the regularization and weight parameter. We then develop a state-of-the-art algorithm that can compute the entire trajectory of the WSVM solutions for every pair of the regularization parameter and the weight parameter at a feasible computational cost. The derived two-dimensional solution surface provides theoretical insight on the behavior of the WSVM solutions. Numerically, the algorithm can greatly facilitate the implementation of the WSVM and automate the selection process of the optimal regularization parameter. We illustrate the new algorithm on various examples. This article has online supplementary materials.     

Ordered median problem with demand distribution weights

The ordered median function unifies and generalizes most common objective functions used in location theory. It is based on the ordered weighted averaging (OWA) operator with the preference weights allocated to the ordered distances. Demand weights are used in location problems to express the client demand for a service thus defining the location decision output as distances distributed according to measures defined by the demand weights. Typical ordered median model allows weighting of several clients only by straightforward rescaling of the distance values. However, the OWA aggregation of distances enables us to introduce demand weights by rescaling accordingly clients measure within the distribution of distances. It is equivalent to the so-called weighted OWA (WOWA) aggregation of distances covering as special cases both the weighted median solution concept defined with the demand weights (in the case of equal all the preference weights), as well as the ordered median solution concept defined with the preference weights (in the case of equal all the demand weights). This paper studies basic models and properties of the weighted ordered median problem (WOMP) taking into account the demand weights following the WOWA aggregation rules. Linear programming formulations were introduced for optimization of the WOWA objective with monotonic preference weights thus representing the equitable preferences in the WOMP. We show MILP models for general WOWA optimization.     

Inverse 1-median problem on trees under weighted Hamming distance

The inverse 1-median problem consists in modifying the weights of the customers at minimum cost such that a prespecified supplier becomes the 1-median of modified location problem. A linear time algorithm is first proposed for the inverse problem under weighted l _?? norm. Then two polynomial time algorithms with time complexities O(n log n) and O(n) are given for the problem under weighted bottleneck-Hamming distance, where n is the number of vertices. Finally, the problem under weighted sum-Hamming distance is shown to be equivalent to a 0-1 knapsack problem, and hence is ${\mathcal{NP}}$ -hard.     

顾客为子树结构的树上反中心选址问题

顾客为子树结构的树上反中心选址问题是在树T上寻找一点(位于顶点处或在边的内部),使得该点与子树结构的顾客之间的最小赋权带加数距离尽可能地大.给出了该问题的一个有效算法,其时间复杂度为O(cn+sum from j=1 to m n_j),其中n_j为各子树T_j的顶点个数,c为不同的子树权重个数,n为树的顶点数.     

On a class of weighted anisotropic Sobolev inequalities

In this article, motivated by a work of Caffarelli and Cordoba in phase transitions analysis, we prove new weighted anisotropic Sobolev type inequalities where different derivatives have different weight functions. These inequalities are also intimately connected to weighted Sobolev inequalities for Grushin type operators, the weights being not necessarily Muckenhoupt. For example we consider Sobolev inequalities on finite cylinders, the weight being a power of the distance function from the top or the bottom of the cylinder. We also prove similar inequalities in the more general case in which the weight is a power of the distance function from a higher codimension part of the boundary.     

Weighted L2 quantile distance estimators for randomly censored data

The asymptotic properties of a family of minimum quantile distance estimators for randomly censored data sets are considered. These procedures produce an estimator of the parameter vector that minimizes a weighted L² distance measure between the Kaplan-Meier quantile function and an assumed parametric family of quantile functions. Regularity conditions are provided which insure that these estimators are consistent and asymptotically normal. An optimal weight function is derived for single parameter families, which, for location/scale families, results in censored sample analogs of estimators such as those suggested by Parzen.     

Weighted L quantile distance estimators for randomly censored data

The asymptotic properties of a family of minimum quantile distance estimators for randomly censored data sets are considered. These procedures produce an estimator of the parameter vector that minimizes a weighted L² distance measure between the Kaplan-Meier quantile function and an assumed parametric family of quantile functions. Regularity conditions are provided which insure that these estimators are consistent and asymptotically normal. An optimal weight function is derived for single parameter families, which, for location/scale families, results in censored sample analogs of estimators such as those suggested by Parzen.     

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

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

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

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

Determination of common due window location in a single machine scheduling problem

We consider the static deterministic single machine scheduling problem in which all jobs have a common due window. Jobs that are completed within the window incur no penalty. The objective is to find the optimal sequence and the optimal common due window location given that the due window size is a problem parameter such that the weighted sum of earliness, tardiness, and due window location penalties is minimized. We propose an O(n log n) algorithm to solve the problem. We also consider two special cases for which simple solutions can be obtained.     

A Stochastic (Adaptive) Problem of Optimal Harvesting

We study a population-growth parametric model described by a Cauchy problem for an ordinary differential equation with the right-hand side depending on the population size, time, and a stochastic parameter. For this problem, we consider an adaptive optimal control problem, the problem of optimal harvesting. For the case where the stochastic parameter is piecewise constant and changes at fixed moments, we construct a synthesis of the adaptive trajectory and the optimal control strategy. The results are illustrated with five simple population-growth models.     

Improved estimation of duality gap in binary quadratic programming using a weighted distance measure

We present in this paper an improved estimation of duality gap between binary quadratic program and its Lagrangian dual. More specifically, we obtain this improved estimation using a weighted distance measure between the binary set and certain affine subspace. We show that the optimal weights can be computed by solving a semidefinite programming problem. We further establish a necessary and sufficient condition under which the weighted distance measure gives a strictly tighter estimation of the duality gap than the existing estimations.     

The probabilistic 1-maximal covering problem on a network with discrete demand weights

We discuss the probabilistic 1-maximal covering problem on a network with uncertain demand. A single facility is to be located on the network. The demand originating from a node is considered covered if the shortest distance from the node to the facility does not exceed a given service distance. It is assumed that demand weights are independent discrete random variables. The objective of the problem is to find a location for the facility so as to maximize the probability that the total covered demand is greater than or equal to a pre-selected threshold value. We show that the problem is NP-hard and that an optimal solution exists in a finite set of dominant points. We develop an exact algorithm and a normal approximation solution procedure. Computational experiment is performed to evaluate their performance.     

Good Lattice Rules in Weighted Korobov Spaces with General Weights

We study the problem of multivariate integration and the construction of good lattice rules in weighted Korobov spaces with general weights. These spaces are not necessarily tensor products of spaces of univariate functions. Sufficient conditions for tractability and strong tractability of multivariate integration in such weighted function spaces are found. These conditions are also necessary if the weights are such that the reproducing kernel of the weighted Korobov space is pointwise non-negative. The existence of a lattice rule which achieves the nearly optimal convergence order is proven. A component-by-component (CBC) algorithm that constructs good lattice rules is presented. The resulting lattice rules achieve tractability or strong tractability error bounds and achieve nearly optimal convergence order for suitably decaying weights. We also study special weights such as finite-order and order-dependent weights. For these special weights, the cost of the CBC algorithm is polynomial. Numerical computations show that the lattice rules constructed by the CBC algorithm give much smaller worst-case errors than the mean worst-case errors over all quasi-Monte Carlo rules or over all lattice rules, and generally smaller worst-case errors than the best Korobov lattice rules in dimensions up to hundreds. Numerical results are provided to illustrate the efficiency of CBC lattice rules and Korobov lattice rules (with suitably chosen weights), in particular for high-dimensional finance problems.     

Chebyshev approximation of the null function by an affine combination of complex exponential functions

We describe the theoretical solution of an approximation problem that uses a finite weighted sum of complex exponential functions. The problem arises in an optimization model for the design of a telescope array occurring within optical interferometry for direct imaging in astronomy. The problem is to find the optimal weights and the optimal positions of a regularly spaced array of aligned telescopes, so that the resulting interference function approximates the zero function on a given interval. The solution is given by means of Chebyshev polynomials.     

TRACTABILITY OF MULTIVARIATE INTEGRATION PROBLEM FOR PERIODIC CONTINUOUS FUNCTIONS

The authors study the tractability and strong tractability of a multivariate integration problem in the worst case setting for weighted l-periodic continuous functions spaces of d coordinates with absolutely convergent Fourier series.The authors reduce the initial error by a factor ε for functions from the unit ball of the weighted periodic contin- uous functions spaces.Tractability is the minimal number of function samples required to solve the problem in polynomial in ε~(-1)and d.and the strong tractability is the pres- ence of only a polynomial dependence in ε.This problem has been recently studied for quasi-Monte Carlo quadrature rules.quadrature rules with non-negative coefficients. and rules for which all quadrature weights are arbitrary for weighted Korobov spaces of smooth periodic functions of d variables.The authors show that the tractability and strong tractability of a multivariate integration problem in worst case setting hold for the weighted periodic continuous functions spaces with absolutely convergent Fourier series under the same assumptions as in Ref.[14]on the weights of the Korobov space for quasi-Monte Carlo rules and rules for which all quadrature weights are non-negative.The arguments are not constructive.     

Local convergence in a generalized Fermat-Weber problem

In the Fermat-Weber problem, the location of a source point in ^N is sought which minimizes the sum of weighted Euclidean distances to a set of destinations. A classical iterative algorithm known as the Weiszfeld procedure is used to find the optimal location. Kuhn proves global convergence except for a denumerable set of starting points, while Katz provides local convergence results for this algorithm. In this paper, we consider a generalized version of the Fermat-Weber problem, where distances are measured by anl _p norm and the parameterp takes on a value in the closed interval [1, 2]. This permits the choice of a continuum of distance measures from rectangular (p=1) to Euclidean (p=2). An extended version of the Weiszfeld procedure is presented and local convergence results obtained for the generalized problem. Linear asymptotic convergence rates are typically observed. However, in special cases where the optimal solution occurs at a singular point of the iteration functions, this rate can vary from sublinear to quadratic. It is also shown that for sufficiently large values ofp exceeding 2, convergence of the Weiszfeld algorithm will not occur in general.