Retailers, from fashion stores to grocery stores, have to decide what range of products to off er, i.e., their product assortment. New business trends, such as mass customization and shorter product life cycles, make predicting demand more difficult, which in turn complicates assortment planning. We propose and study a stochastic dynamic programming model for simultaneously making … Read more
Recently, a worst-case O(1/t) convergence rate was established for the Douglas-Rachford alternating direction method of multipliers in an ergodic sense. This note proposes a novel approach to derive the same convergence rate while in a non-ergodic sense. ArticleDownload View PDF
We study the problem of minimizing a nonnegative separable concave function over a compact feasible set. We approximate this problem to within a factor of 1+epsilon by a piecewise-linear minimization problem over the same feasible set. Our main result is that when the feasible set is a polyhedron, the number of resulting pieces is polynomial … Read more
The single row facility layout problem (SRFLP) is the problem of arranging facilities with given lengths on a line, while minimizing the weighted sum of the distances between all pairs of facilities. The problem is NP-hard. In this paper, we present two tabu search implementations, one involving an exhaustive search of the 2-opt neighborhood and … Read more
The single row facility layout problem (SRFLP) is the problem of arranging facilities with given lengths on a line, while minimizing the weighted sum of the distances between all pairs of facilities. The problem is known to be NP-hard. In this paper, we present a neighborhood search heuristic called LK-INSERT which uses a Lin-Kernighan neighborhood … Read more
We propose easily implementable algorithms for minimizing the norm with pseudomonotone variational inequality constraints. This bilevel problem arises in the Tikhonov regularization method for pseudomonone variational inequalities. Since the solution set of the lower variational inequality is not given explicitly, the available methods of mathematical programming and variational inequality can not be applied directly. With … Read more
The contributions of the first half of this thesis are on the computational and algebraic aspects of convexity in polynomial optimization. We show that unless P=NP, there exists no polynomial time (or even pseudo-polynomial time) algorithm that can decide whether a multivariate polynomial of degree four (or higher even degree) is globally convex. This solves … Read more
In this paper, we give two new results on the proximal point algorithm for finding a zero point of any given maximal monotone operator. First, we prove that if the sequence of regularization parameters is non-increasing then so is that of residual norms. Then, we use it to show that the proximal point algorithm can … Read more
This paper is devoted to the so-called pessimistic version of bilevel programming programs. Minimization problems of this type are challenging to handle partly because the corresponding value functions are often merely upper (while not lower) semicontinuous. Employing advanced tools of variational analysis and generalized differentiation, we provide rather general frameworks ensuring the Lipschitz continuity of … Read more
Power grid vulnerability analysis is often performed through solving a bi-level optimization problem, which, if solved to optimality, yields the most destructive interdiction plan with the worst loss. As one of the most effective operations to mitigate deliberate outages or attacks, transmission line switching recently has been included and modeled by a binary variable in … Read more