Establishing Nash equilibrium of the manufacturer–supplier game in supply chain management

We study a game model of multi-leader and one-follower in supply chain optimization where n suppliers compete to provide a single product for a manufacturer. We regard the selling price of each supplier as a pre-determined parameter and consider the case that suppliers compete on the basis of delivery frequency to the manufacturer. Each supplier's profit depends not only on its own delivery frequency, but also on other suppliers' frequencies through their impact on manufacturer's purchase allocation to the suppliers. We first solve the follower's (manufacturer's) purchase allocation problem by deducing an explicit formula of its solution. We then formulate the n leaders' (suppliers') game as a generalized Nash game with shared constraints, which is theoretically difficult, but in our case could be solved numerically by converting to a regular variational inequality problem. For the special case that the selling prices of all suppliers are identical, we provide a sufficient and necessary condition for the existence and uniqueness of the Nash equilibrium. An explicit formula of the Nash equilibrium is obtained and its local uniqueness property is proved.     

Optimal supplier choice with discounting

This paper investigates a model for pricing the demand for a set of goods when suppliers operate discount schedules based on total business value. We formulate the buyers's decision problem as a mixed binary integer program, which is a generalization of the capacitated facility location problem (CFLP). A branch and bound (BnB) procedure using Lagrangean relaxation and subgradient optimization is developed for solving large-scale problems that can arise when suppliers’ discount schedules contain multiple price breaks. Results of computer trials on specially adapted large benchmark instances of the CFLP confirm that a sub-gradient optimization procedure based on Shor and Zhurbenko's r-algorithm, which employs a space dilation in the direction of the difference between two successive subgradients, can be used efficiently for solving the dual problem at any node of the BnB tree.     

价格与质量双重竞争下电商平台渠道模式决策研究

近年来传统电商正加速从经销商转变为连接消费者与供应商的在线市场中间商, 电商平台与供应商形成三种渠道结构:经销商模式、混合模式和在线市场模式。本文通过构建Stackelberg博弈模型讨论产品质量与价格双重竞争情境下电商平台与供应商销售合作模式最新选择问题。研究表明,当价格竞争强度适中而佣金比例较大时,混合模式是电商平台最优选择,此时产品质量差异最大;当价格竞争强度较小而佣金比例较大时,在线市场模式则是最优选择;在其他条件下,经销商模式是其最优选择。本文结论对电商平台与供应商合作模式选择、产品质量与定价决策具有参考价值。     

The 0–1 knapsack problem with multiple choice constraints

In this paper we consider the 0–1 knapsack problem with multiple choice constraints appended. Such a problem may arise in a capital budgeting context where only one project may be selected from a particular group of projects. Thus the problem is to choose one project from each group such that the budgetary constraint is satisfied and the maximum return is realized. We formulate two branch and bound algorithms which use two different relaxations as the primary bounding relaxations. In addition, theoretical results are given for a simple reduction in the number of variables in the problem.     

A hierarchy of relaxations for linear generalized disjunctive programming

Generalized disjunctive programming (GDP), originally developed by Raman and Grossmann (1994), is an extension of the well-known disjunctive programming paradigm developed by Balas in the mid 70s in his seminal technical report (Balas, 1974). This mathematical representation of discrete-continuous optimization problems, which represents an alternative to the mixed-integer program (MIP), led to the development of customized algorithms that successfully exploited the underlying logical structure of the problem. The underlying theory of these methods, however, borrowed only in a limited way from the theories of disjunctive programming, and the unique insights from Balas’ work have not been fully exploited.In this paper, we establish new connections between the fields of disjunctive programming and generalized disjunctive programming for the linear case. We then propose a novel hierarchy of relaxations to the original linear GDP model that subsumes known relaxations for this model, and show that a subset of these relaxations are tighter than the latter. We discuss the usefulness of these relaxations within the context of MIP and illustrate these results on the classic strip-packing problem.     

Equilibrium contract selection strategy in chain-to-chain competition with demand uncertainty

This paper investigates the equilibrium contract selection problem for the dominant suppliers in two competing supply chains with stochastic and price-sensitive demand. The two suppliers, acting as the Stackelberg leaders, produce substitutable products and distribute them through each exclusive retailer, and can provide either a consignment contract or a wholesale-price contract. The equilibrium behaviours of the suppliers and retailers are investigated in three different scenarios: (1) the consignment contract scenario; (2) the wholesale-price contract scenario; and (3) the hybrid contract scenario. We prove that the equilibrium contracting strategy is of the threshold type: when the cost-share rates of the two retailers are above certain thresholds, both suppliers select consignment contracts; when the cost-share rates of the two retailers are lower than certain thresholds, both suppliers select wholesale-price contracts; when one retailer’s cost-share rate is above a certain threshold and the other is lower than a certain threshold, the supplier with large retailer’s cost-share rate selects the consignment contract and the other supplier with small retailer’s cost-share rate selects the wholesale-price contract. Furthermore, these thresholds depend on price sensitivities.     

Lower and upper bounds for the spanning tree with minimum branch vertices

We study a variant of the spanning tree problem where we require that, for a given connected graph, the spanning tree to be found has the minimum number of branch vertices (that is vertices of the tree whose degree is greater than two). We provide four different formulations of the problem and compare different relaxations of them, namely Lagrangian relaxation, continuous relaxation, mixed integer-continuous relaxation. We approach the solution of the Lagrangian dual both by means of a standard subgradient method and an ad-hoc finite ascent algorithm based on updating one multiplier at the time. We provide numerical result comparison of all the considered relaxations on a wide set of benchmark instances. A useful follow-up of tackling the Lagrangian dual is the possibility of getting a feasible solution for the original problem with no extra costs. We evaluate the quality of the resulting upper bound by comparison either with the optimal solution, whenever available, or with the feasible solution provided by some existing heuristic algorithms.     

机场蓄车池出租车司机的选择决策研究 ——以首都机场为例

随着中国全面小康的逐步实现,乘客下飞机后乘坐出租车回市区已经成为大多数人的选择.着眼出租车送客至机场后的情景,以出租车司机的盈利最大化为目标,讨论出租车司机的两种决策选择——决策A是留在机场蓄车池等待回城区的乘客,决策B是空载回城找生意.控制时间相同的条件下,用机场接客的订单金额来估计决策A的收益,用司机单位时间内平均收益乘以经营时长来衡量决策B的收益.以北京市首都国际机场为例,从数学模型的角度为出租车司机提供决策条件,有效实现司机利润最大化.     

The Effect of Acceptance Sampling and Risk Aversion on the Quality Delivered by Suppliers

Firms often use acceptance sampling to monitor the quality of the raw materials and components delivered by suppliers. In this paper, we use numerical methods to examine how a risk averse supplier reacts to the acceptance sampling plan used by a customer. We assume that the supplier produces and delivers a quality level that maximizes the supplier's expected utility. We examine the sensitivity of the optimal delivered quality to changes in the price, to changes in the supplier's level of risk aversion, and to changes in the parameters of the customer's sampling plan. We conclude that risk averse suppliers deliver higher quality, that higher capability suppliers do not necessarily deliver higher quality, and that the optimal quality is sensitive to the lot size. We also conclude that since the risk of rejection motivates suppliers to improve quality, customers have an economic justification for using acceptance sampling even when there is no statistical justification.     

The impact of cost uncertainty on the location of a distribution center

The location of a distribution center (DC) is a key consideration for the design of supply chain networks. When deciding on it, firms usually allow for transportation costs, but not supplier prices. We consider simultaneously the location of a DC and the choice of suppliers offering different, possibly random, prices for a single product. A buying firm attempts to minimize the sum of the price charged by a chosen supplier, and inbound and outbound transportation costs. No costs are incurred for switching suppliers. We first derive a closed-form optimal location for the case of a demand-populated unit line between two suppliers offering deterministic prices. We then let one of the two suppliers offer a random price. If the price follows a symmetric and unimodal distribution, the optimal location is closer to the supplier with a lower mean price. We also show the dominance of high variability: the buyer can decrease the total cost more for higher price variability for any location. The dominance result holds for normal, uniform, and gamma distributions. We propose an extended model with more than two suppliers on a plane and show that the dominance result still holds. From numerical examples for a line and a plane, we observe that an optimal location gets closer to the center of gravity of demands as the variability of any supplier’s price increases.     

Coordinated decisions for substitutable products in a common retailer supply chain

This paper studies coordination mechanisms in a supply chain which consists of two suppliers with capacity uncertainties selling differential yet substitutable products through a common retailer who faces price-sensitive random demand of these two products. We develop in a noncompetitive setting three coordination models – revenue sharing, return policy, and combination of revenue sharing and return policy – and contrast them with a basic and uncoordinated model. We are able to establish the ordinal relationship among the retailer’s ordering and pricing decisions and analytically compare the performances between certain models when two suppliers are identical. We find that the retailer’s ordering and pricing decisions in the model with return policy in the case of identical suppliers are independent of demand or supply uncertainty. Our numerical results reveal that the performances of coordination models in the case of nonidentical suppliers resemble those in the case of identical suppliers. We find that the retailer will place a larger order quantity in models where her average cost per unit sold is smaller. We also find that product substitutability and uncertainties have different effects on chain performances.     

Correlative sparsity structures and semidefinite relaxations for concave cost transportation problems with change of variables

We present a hierarchy of semidefinite programming (SDP) relaxations for solving the concave cost transportation problem (CCTP), which is known to be NP-hard, with p suppliers and q demanders. In particular, we study cases in which the cost function is quadratic or square-root concave. The key idea of our relaxation methods is in the change of variables to CCTPs, and due to this, we can construct SDP relaxations whose matrix variables are of size O((min {p, q}) ^ω ) in the relaxation order ω. The sequence of optimal values of SDP relaxations converges to the global minimum of the CCTP as the relaxation order ω goes to infinity. Furthermore, the size of the matrix variables can be reduced to O((min {p, q}) ^ω-1 ), ω ≥  2 by using Reznick’s theorem. Numerical experiments were conducted to assess the performance of the relaxation methods.     

LP relaxations for a class of linear semi-infinite programming problems

In this paper, we consider a subclass of linear semi-infinite programming problems whose constraint functions are polynomials in parameters and index sets are polyhedra. Based on Handelman’s representation of positive polynomials on a polyhedron, we propose two hierarchies of LP relaxations of the considered problem which respectively provide two sequences of upper and lower bounds of the optimum. These bounds converge to the optimum under some mild assumptions. Sparsity in the LP relaxations is explored for saving computational time and avoiding numerical ill behaviors.     

Handelman’s hierarchy for the maximum stable set problem

The maximum stable set problem is a well-known NP-hard problem in combinatorial optimization, which can be formulated as the maximization of a quadratic square-free polynomial over the (Boolean) hypercube. We investigate a hierarchy of linear programming relaxations for this problem, based on a result of Handelman showing that a positive polynomial over a polytope with non-empty interior can be represented as conic combination of products of the linear constraints defining the polytope. We relate the rank of Handelman’s hierarchy with structural properties of graphs. In particular we show a relation to fractional clique covers which we use to upper bound the Handelman rank for perfect graphs and determine its exact value in the vertex-transitive case. Moreover we show two upper bounds on the Handelman rank in terms of the (fractional) stability number of the graph and compute the Handelman rank for several classes of graphs including odd cycles and wheels and their complements. We also point out links to several other linear and semidefinite programming hierarchies.     

A partial cooperation model for non-unique linear two-level decision problems

This paper examines a linear static Stackelberg game where the follower's optimal reaction is not unique. Traditionally, the problem has been approached using either an optimistic or a pessimistic framework, respectively, representing the two extreme situations of full cooperation and zero cooperation from the follower. However, partial cooperation from the follower is a viable option. For partial cooperation, the leader's optimal strategy may be neither optimistic nor pessimistic. Introducing a cooperation index to describe the degree of follower cooperation, we first formulate a partial cooperation model for the leader. The two-level problem is then reformulated into a single-level model. It is shown that the optimistic and pessimistic situations are special cases of the general model, and that the leader's optimal choice may be an intermediate solution.     

Product line selection and pricing analysis: Impact of genetic relaxations

A model for the product line selection and pricing problem (PLSP) is presented andthree solution procedures based on a genetic algorithm are developed to analyze the results based on consumer preference patterns. Since the PLSP model is nonlinear and integer, two of the solution procedures use genetic encoding to “relax” the NP hard model. The relaxations result in linear integer and shortest path models for the fitness evaluation which are solved using branch and bound and labeling algorithms, respectively. Performance of the quality of solutions generated by the procedures is evaluated for various problem sizes and customer preference structures. The results show that the genetic relaxations provide efficient and effective solution methodologies for the problem, when compared to the pure artificial intelligence technique of genetic search. The impact of the preference structure on the product line and the managerial implications of the solution characteristics generated by the genetic relaxations are also discussed. The models can be used to explicitly consider tradeoffs between marketing and operations concerns in designing a product line.     

Heuristics for sourcing from multiple suppliers with alternative quantity discounts

In this paper, we analyze the impact of supplier pricing schemes and supplier capacity limitations on the optimal sourcing policy for a single firm. We consider the situation where the total quantity to be procured for a single period is known by the firm and communicated to the supplier set. In response to this communication, each supplier quotes a price and a capacity limit in terms of a maximum quantity that can be supplied to the buyer. Based on this information, the buyer makes a quantity allocation decision among the suppliers and corresponding to this decision is the choice of a subset of suppliers who will receive an order. Based on industry observations, a variety of supplier pricing schemes from the constituent group of suppliers are analyzed, including linear discounts, incremental units discounts, and all units discounts. Given the complexity of the optimization problem for certain types of pricing schemes, heuristic solution methodologies are developed to identify a quantity allocation decision for the firm. Through an extensive computational comparison, we find that these heuristics generate near-optimal solutions very quickly. Data from a major office products retailer is used to illustrate the resulting sourcing strategies given different pricing schemes and capacity limitations of suppliers in this industry. We find for the case of capacity constrained suppliers, the optimal quantity allocations for two complex pricing schemes (linear discount, and incremental units discount) are such that at most one selected supplier will receive an order quantity that is less than its capacity.     

The effect of supplier capacity on the supply chain profit

In this paper, we study the role of capacity on the efficiency of a two-tier supply chain with two suppliers (leaders, first tier) and one retailer (follower, second tier). The suppliers compete via pricing (Bertrand competition) and, as one would expect in practice, are faced with production capacity. We consider a model with differentiated substitutable products where the suppliers are symmetric differing only by their production capacity. We characterize the prices, production amounts and profits in three cases: (1) the suppliers compete in a decentralized Nash equilibrium game, (2) the suppliers “cooperate” to optimize the total suppliers’ profit, and (3) the two tiers of the supply chain are centrally coordinated. We show that in a decentralized setting, the supplier with a lower capacity may benefit from restricting her capacity even when additional capacity is available at no cost. We also show that the loss of total profit due to decentralization cannot exceed 25 % of the centralized chain profits. Nevertheless, the loss of total profit is not a monotonic function of the “degree of asymmetry” of the suppliers’ capacities. Furthermore, we provide an upper bound on the supplier profit loss at equilibrium (compared with the cooperation setting) that depends on the “market power” of the suppliers as well as their market size. We show that there is less supplier profit loss as the asymmetry (in terms of their capacities) increases between the two suppliers. The worst case arises when the two suppliers are completely symmetric.     

A decomposition approach for a new test-scenario in complex problem solving

Over the last years, psychological research has increasingly used computer-supported tests, especially in the analysis of complex human decision making and problem solving. The approach is to use computer-based test scenarios and to evaluate the performance of participants and correlate it to certain attributes, such as the participant's capacity to regulate emotions. However, two important questions can only be answered with the help of modern optimization methodology. The first one considers an analysis of the exact situations and decisions that led to a bad or good overall performance of test persons. The second important question concerns performance, as the choices made by humans can only be compared to one another, but not to the optimal solution, as it is unknown in general.Additionally, these test-scenarios have usually been defined on a trial-and-error basis, until certain characteristics became apparent. The more complex models become, the more likely it is that unforeseen and unwanted characteristics emerge in studies. To overcome this important problem, we propose to use mathematical optimization methodology not only as an analysis and training tool, but also in the design stage of the complex problem scenario.We present a novel test scenario, the IWR Tailorshop, with functional relations and model parameters that have been formulated based on optimization results. We also present a tailored decomposition approach to solve the resulting mixed-integer nonlinear programs with nonconvex relaxations and show some promising results of this approach.