A piecewise linearization framework for retail shelf space management models

Managing shelf space is critical for retailers to attract customers and optimize profits. This article develops a shelf-space allocation optimization model that explicitly incorporates essential in-store costs and considers space- and cross-elasticities. A piecewise linearization technique is used to approximate the complicated nonlinear space-allocation model. The approximation reformulates the non-convex optimization problem into a linear mixed integer programming (MIP) problem. The MIP solution not only generates near-optimal solutions for large scale optimization problems, but also provides an error bound to evaluate the solution quality. Consequently, the proposed approach can solve single category-shelf space management problems with as many products as are typically encountered in practice and with more complicated cost and profit structures than currently possible by existing methods. Numerical experiments show the competitive accuracy of the proposed method compared with the mixed integer nonlinear programming shelf-space model. Several extensions of the main model are discussed to illustrate the flexibility of the proposed methodology.     

Optimization of a Quadratic Function with a Circulant Matrix

A problem arising in the control of flutter in compression systems via mistuning is formulated as maximizing a quadratic function with a circulant matrix over a set of vectors whose every component can take one of three values (the three level problem) or one of two values (the two level problem).     

A branch-reduce-cut algorithm for the global optimization of probabilistically constrained linear programs

We consider probabilistically constrained linear programs with general distributions for the uncertain parameters. These problems involve non-convex feasible sets. We develop a branch-and-bound algorithm that searches for a global optimal solution to this problem by successively partitioning the non-convex feasible region and by using bounds on the objective function to fathom inferior partition elements. This basic algorithm is enhanced by domain reduction and cutting plane strategies to reduce the size of the partition elements and hence tighten bounds. The proposed branch-reduce-cut algorithm exploits the monotonicity properties inherent in the problem, and requires solving linear programming subproblems. We provide convergence proofs for the algorithm. Some illustrative numerical results involving problems with discrete distributions are presented.     

Necessary and sufficient conditions for the existence of complementary solutions and characterizations of the matrix classesQ andQ 0

We simplify a result by Mangasarian on the existence of solutions to the linear complementarity problem. The simplified condition gives a new geometric interpretation of the result. When used to characterize the matrix classesQ andQ ₀, our condition suggests a finitely checkable sufficient condition forP andP ₀.This work was supported in part by the Office of Naval Research under Contract No. N00014-86-K-0173, and by general research development funds provided by the Georgia Institute of Technology.     

Accelerating convergence of cutting plane algorithms for disjoint bilinear programming

This paper presents two linear cutting plane algorithms that refine existing methods for solving disjoint bilinear programs. The main idea is to avoid constructing (expensive) disjunctive facial cuts and to accelerate convergence through a tighter bounding scheme. These linear programming based cutting plane methods search the extreme points and cut off each one found until an exhaustive process concludes that the global minimizer is in hand. In this paper, a lower bounding step is proposed that serves to effectively fathom the remaining feasible region as not containing a global solution, thereby accelerating convergence. This is accomplished by minimizing the convex envelope of the bilinear objective over the feasible region remaining after introduction of cuts. Computational experiments demonstrate that augmenting existing methods by this simple linear programming step is surprisingly effective at identifying global solutions early by recognizing that the remaining region cannot contain an optimal solution. Numerical results for test problems from both the literature and an application area are reported.     

Global optimization of a nonconvex single facility location problem by sequential unconstrained convex minimization

The problem of maximizing the sum of certain composite functions, where each term is the composition of a convex decreasing function, bounded from below, with a convex function having compact level sets arises in certain single facility location problems with gauge distance functions. We show that this problem is equivalent to a convex maximization problem over a compact convex set and develop a specialized polyhedral annexation procedure to find a global solution for the case when the inside function is a polyhedral norm. As the problem was solved recently only for local solutions, this paper offers an algorithm for finding a global solution. Implementation and testing are not treated in this short communication.An earlier version of this paper appeared in the proceedings of a conference on Recent Advances in Global Optimization, C. Floudas and P. Pardalos, eds., Princeton University Press, 1991.