Approximately global optimization for assortment problems using piecewise linearization techniques

Recently, Li and Chang proposed an approximate model for assortment problems. Although their model is quite promising to find approximately global solution, too many 0–1 variables are required in their solution process. This paper proposes another way for solving the same problem. The proposed method uses iteratively a technique of piecewise linearization of the quadratic objective function. Numerical examples demonstrate that the proposed method is computationally more efficient than the Li and Chang method.     

On the assortment optimization with endogenized market size

In this paper, we consider the joint effects of product substitution and market size endogenization. Under the substitution effects, a product’s demand may be cannibalized by other substitutable products; while the market size, measured by the number of customers who are interested in the products from the same category, may be largely influenced by the product offer set. We establish the computational complexity for the assortment problem under the joint effects, and develop a fully polynomial-time approximation scheme (FPTAS).     

Robust assortment optimization using worst-case CVaR under the multinomial logit model

We consider robust assortment optimization problems with partial distributional information of parameters in the multinomial logit choice model. The objective is to find an assortment that maximizes a revenue target using a distributionally robust chance constraint, which can be approximated by the worst-case Conditional Value-at-Risk. We show that our problems are equivalent to robust assortment optimization problems over special uncertainty sets of parameters, implying the optimality of revenue-ordered assortments under certain conditions.     

On the sharpness of two-sided bounds for the Perron Root and of the related eigenvalue inclusion sets

The paper considers the sharpness problem for certain two-sided bounds for the Perron root of an irreducible nonnegative matrix. The results obtained are applied to prove the sharpness of the related eigenvalue inclusion sets in classes of matrices with fixed diagonal entries, bounded above deleted absolute row sums, and a partly specified irreducible sparsity pattern.     

A fuzzy goal programming approach for mid-term assortment planning in supermarkets

We develop a fuzzy mixed integer non-linear goal programming model for the mid-term assortment planning of supermarkets in which three conflicting objectives namely profitability, customer service, and space utilization are incorporated. The items and brands in a supermarket compete to obtain more space and better shelf level. This model offers different service levels to loyal and disloyal customers, applies joint replenishment policy, and accounts for the holding time limitation of perishable items. We propose a fuzzy approach due to the imprecise nature of the goals’ target levels and priorities as well as critical data. A heuristic method inspiring by the problem-specific rules is developed to solve this complex model approximately within a reasonable time. Finally, the proposed approach is validated through several numerical examples and results are reported.     

Parametric error bounds for convex approximations of two-stage mixed-integer recourse models with a random second-stage cost vector

We consider two-stage recourse models with integer restrictions in the second stage. These models are typically non-convex and hence, hard to solve. There exist convex approximations of these models with accompanying error bounds. However, it is unclear how these error bounds depend on the distributions of the second-stage cost vector q. In this paper, we derive parametric error bounds whose dependence on the distribution of q is explicit: they scale linearly in the expected value of the ${?}_1$-norm of q.     

Assortment optimization under the multinomial logit model with product synergies

In synergistic assortment optimization, a product’s attractiveness changes as a function of which other products are offered. We represent synergy structure graphically. Vertices denote products. An edge denotes synergy between two products, which increases their attractiveness when both are offered. Finding an assortment to maximize retailer’s expected profit is NP-hard in general. We present efficient algorithms when the graph is a path, a tree, or has low treewidth. We give a linear program to recover the optimal assortment for paths.     

Exponential behaviour of the Butkovi?-Zimmermann algorithm for solving two-sided linear systems in max-algebra

In [P. Butkovi?, K. Zimmermann, A strongly polynomial algorithm for solving two-sided linear systems in max-algebra, Discrete Applied Mathematics 154 (3) (2006) 437-446] an ingenious algorithm for solving systems of two-sided linear equations in max-algebra was given and claimed to be strongly polynomial. However, in this note we give a sequence of examples showing exponential behaviour of the algorithm. We conclude that the problem of finding a strongly polynomial algorithm is still open.     

A strongly polynomial algorithm for solving two-sided linear systems in max-algebra

An algorithm for solving m×n systems of (max,+)-linear equations is presented. The systems have variables on both sides of the equations. After O(m⁴n⁴) iterations the algorithm either finds a solution of the system or finds out that no solution exists. Each iteration needs O(mn) operations so that the complexity of the presented algorithm is O(m⁵n⁵).     

Assortment optimization with repeated exposures and product-dependent patience cost

In this paper, we study the assortment optimization problem faced by many online retailers such as Amazon. We develop a cascade multinomial logit model, based on the classic multinomial logit model, to capture the consumers' purchasing behavior across multiple stages. Unlike most of existing studies, our model allows for repeated exposures of a product. In addition, each consumer has a patience budget that is sampled from a known distribution and each product is associated with a patience cost, which is the required amount of the cognitive efforts on browsing that product. We propose an approximation solution to the assortment optimization problem under cascade multinomial logit model.     

A station-oriented enumerative algorithm for two-sided assembly line balancing

In this paper, a station-oriented enumerative algorithm for two-sided assembly lines balancing (TALB) is proposed. First, the time transfer function is defined and combined with the precedence relation to compute the earliest and the latest start time of tasks. With the direction and cycle time constraints, a station-oriented procedure based on the start time is designed to assign tasks, starting from the left station to the rightstation of the position. Some unsuitable position assignments would be finally removed by checking the precedence constraints among the assigned tasks. The proposed algorithm is integrated with the Hoffmann heuristic to develop a system for solving TALB problems. The test is performed on the well-known benchmark set of problem instances. Experimental results demonstrate that the proposed procedure is efficient.     

Pricing to accelerate demand learning in dynamic assortment planning for perishable products

Retailers, from fashion stores to grocery stores, have to decide what range of products to offer, i.e., their product assortment. Frequent introduction of new products, a recent business trend, makes predicting demand more difficult, which in turn complicates assortment planning. We propose and study a stochastic dynamic programming model for simultaneously making assortment and pricing decisions which incorporates demand learning using Bayesian updates. We show analytically that it is profitable for the retailer to use price reductions early in the sales season to accelerate demand learning. A computational study demonstrates the benefits of such a policy and provides managerial insights that may help improve a retailer’s profitability.     

Refinement of Lagrangian bounds in optimization problems

Lagrangian constraint relaxation and the corresponding bounds for the optimal value of an original optimization problem are examined. Techniques for the refinement of the classical Lagrangian bounds are investigated in the case where the complementary slackness conditions are not fulfilled because either the original formulation is nonconvex or the Lagrange multipliers are nonoptimal. Examples are given of integer and convex problems for which the modified bounds improve the classical Lagrangian bounds.     

A joint optimisation model for inventory replenishment,product assortment,shelf space and display area allocation decisions

In this paper, we propose an optimisation model to determine the product assortment, inventory replenishment, display area and shelf space allocation decisions that jointly maximize the retailer’s profit under shelf space and backroom storage constraints. The variety of products to be displayed in the retail store, their display locations within the store, their ordering quantities, and the allocated shelf space in each display area are considered as decision variables to be determined by the proposed integrated model. In the model formulation, we include the inventory investment costs, which are proportional to the average inventory, and storage and display costs as components of the inventory costs and make a clear distinction between showroom and backroom inventories. We also consider the effect of the display area location on the item demand. The developed model is a mixed integer non-linear program that we solved using LINGO software. Numerical examples are used to illustrate the developed model.     

On generic quadratic penalty embeddings for nonlinear optimization problems

The generic character of regularity in the sense of Jongen, Jonker and Twilt is studied for a particular class of embeddings, which represents a quadratric penalty procedure. In this paper we state a suitable perturbation result (into the mentioned class) which is the main part for the proof of the genericity     

A PTAS for capacitated sum-of-ratios optimization

Motivated by an application in assortment planning under the nested logit choice model, we develop a polynomial-time approximation scheme for the sum-of-ratios optimization problem with a capacity constraint and a fixed number of product groups.     

On the first passage times of reflected O-U processes with two-sided barriers

In this article, we give the Laplace transform of the first passage times of reflected Ornstein-Uhlenbeck process with two-sided barriers. AMS Subject Classifications 60H10 · 60G40 · 90B05 Supported by NSF of China.     

基于Logit离散选择模型的品类优化问题综述

品类优化问题(Assortment Optimization Problem)是收益管理的经典问题.它研究零售商在满足运营约束的前提下,应如何从给定产品集合中选择一个子集提供给消费者,以最大化预期收益.该问题的核心在于如何准确地刻画消费者在面对细分产品时的选择行为、建立相应的优化模型并设计高效率的求解算法.基于Logit离散选择模型的品类优化问题:首先,介绍了基于Multinomial Logit模型的品类优化问题.然后介绍了两个更复杂的变种:第一个是基于两层以及多层Nested Logit模型的品类优化问题,这类问题可合理刻画细分产品之间的"替代效应";第二个是基于Mixtures of Multinomial Logits模型的品类优化问题,这类问题可充分考虑消费者群体的异质性.随后,介绍了数据驱动的品类优化问题的相关进展.最后,指出该问题未来可能的若干研究方向.     

A branch-and-bound algorithm to minimize the line length of a two-sided assembly line

A new branch-and-bound algorithm is presented to solve the two-sided assembly line balancing problem of type 1 (TALB-1). First, a pair of two directly facing station is defined as a position, and then the two-sided assembly line (TAL) is relaxed to a one-sided assembly line (OAL). Some new lower bound on positions are computed, and dominance rules and reduction rules for the one-sided assembly line balancing problem of type 1 (OALB-1) are extended and incorporated into a station-oriented assignment procedure for the TALB-1 problem. Finally, the tests are carried out on a well-known benchmark set of problem instances, and experimental results demonstrate that the proposed procedure is efficient.