Decentralization in Linear Programming Models

This paper proposes a decomposition of a linear programming problem based on the structure of the optimal basis matrix. If this matrix contains a zero matrix of appropriate dimensions, the problem may be decomposed into a price-setting problem and a quantity-setting problem. This decomposition is valid for a set of coefficients of the problem to be determined by parametric programming. It can be applied to problems with common constraints or common variables. An application to dairy production planning is discussed and a comparison with the Dantzig-Wolfe decomposition principle is given.     

A New Dynamic Programming Decomposition Method for the Network Revenue Management Problem with Customer Choice Behavior

In this paper, we propose a new dynamic programming decomposition method for the network revenue management problem with customer choice behavior. The fundamental idea behind our dynamic programming decomposition method is to allocate the revenue associated with an itinerary among the different flight legs and to solve a single‐leg revenue management problem for each flight leg in the airline network. The novel aspect of our approach is that it chooses the revenue allocations by solving an auxiliary optimization problem that takes the probabilistic nature of the customer choices into consideration. We compare our approach with two standard benchmark methods. The first benchmark method uses a deterministic linear programming formulation. The second benchmark method is a dynamic programming decomposition idea that is similar to our approach, but it chooses the revenue allocations in an ad hoc manner. We establish that our approach provides an upper bound on the optimal total expected revenue, and this upper bound is tighter than the ones obtained by the two benchmark methods. Computational experiments indicate that our approach provides significant improvements over the performances of the benchmark methods.     

The coordination of short-run decision-making with long-range planning

The dichotomy of short-run and long-run decision-making in economic enterprises has gained widespread acceptance, both in practice and in the related literature despite the inherent interdependence of these decisions. The problem addressed in this paper deals with the proper coordination of short- and long-run planning. Structuring the overall decision problem of the firm as a dynamic programming problem, we find that a natural decomposition into long- and short-range planning results. In this decomposition, all decisions which must be made in the first segment of the planning period are allocated to the short-run decision-makers and all subsequent decisions to the long-range planners. Though several formats have been suggested in the literature for linking short- and long-run plans, most notably the use of shadow prices and of targets or quotas, we find that from a conceptual viewpoint these are inadequate mechanisms and that the proper connection involves the dynamic programming return function.     

Multilocation plant sizing and timing problem: a study of spatial—temporal decomposition procedure

An attempt has been made to develop a spatial-temporal decomposition procedure to solve the multilocation plant sizing and timing problem (MLPSTP). MLPSTP involves the determination of site, location, timing and utilization of the plants to meet the demands of geographically distributed customers. These decisions are assumed to interact through a common objective of minimizing the net present value (NPV) of capital costs and streams of operating and transportation costs. A solution procedure for MLPSTP is proposed using aggregation and disaggregation methodology. In the aggregation phase, MLPSTP is considered to be a single-period problem. This problem is decomposed over different geographical areas to obtain a set of feasible sites and projects. These projects are then sequenced over a finite planning horizon in the disaggregation phase. A multiple criteria based evaluation of spatial decomposition, temporal decomposition, and spatial-temporal decomposition is provided.     

Hierarchical production planning for multi-product lines in the beverage industry¶

Multi-commodity production and distribution scheduling is one of the most complex and crucial problems facing many manufacturing companies. For a major European manufacturer specialising in bottling juices and drinks, we have designed and developed a hierarchical decomposition approach to the solution of the multi-commodity production planning problem. In this paper we focus our attention on the coarsest decomposition level, called multi-commodity aggregate production planning (MCAP). It concerns the choice of the best feasible production plan for a set of products (commodities) over an extended time horizon so as to meet forecast aggregate demands throughout the horizon. At this level, the problem constraints include hard constraints (such as production lines having a maximum capacity and products having short life-times), and soft constraints (budgetary concerns.) The objective is to determine the production plan that covers each period's demands as best as possible, while minimizing all relevant costs. Our method for solving MCAP produces optimal plans in negligible times in commodity PC workstations.     

Models and algorithms for the design of survivable multicommodity flow networks with general failure scenarios

We consider the design of a multicommodity flow network, in which point-to-point demands are routed across the network subject to link capacity restrictions. Such a design must build enough capacity and diverse routing paths through the network to ensure that feasible multicommodity flows continue to exist, even when components of the network fail. In this paper, we examine several methodologies to optimally design a minimum-cost survivable network that continues to support a multicommodity flow under any of a given set of failure scenarios, where each failure scenario consists of the simultaneous failure of multiple arcs. We begin by providing a single extensive form mixed-integer programming formulation for this problem, along with a Benders decomposition algorithm as an alternative to the extensive form approach. We next investigate strategies to improve the performance of the algorithm by augmenting the master problem with several valid inequalities such as cover constraints, connectivity constraints, and path constraints. For the smallest instances (eight nodes, 10 origin–destination pairs, and 10 failure scenarios), the Benders implementation consumes only 10% of the time required by the mixed-integer programming formulation, and our best augmentation strategy reduces the solution time by another 50%. For medium- and large-sized instances, the extensive form problem fails to terminate within 2 h on any instance, while our decomposition algorithms provide optimal solutions on all but two problem instances.     

贵金属期货价格预测方法及实证研究

本文融合了二次分解与极限学习机的优势,提出了VMD-Res.-EEMD-ELM贵金属期货价格预测模型,选择变分模态分解(VMD)作为主要的分解技术,生成模态分量序列(VMFi)和残差序列(Res.),采用集合经验模态分解(EEMD)对残差序列进行二次分解,并使用具有良好泛化能力的极限学习机(ELM)对各分量进行预测,最后叠加各模态分量和残差的预测值形成收益率的最终预测结果。所提出的模型不仅充分发挥了二次分解技术的优势,而且解决了传统变分模态分解组合预测模型未考虑残差影响因素的问题。实证研究表明,本文所提出的组合模型能够全面捕捉黄金、白银期货价格日收益率序列的特征,方向性预测准确率分别为83.33%和93.33%,误差指标MAE分别为0.15和0.11,经比较本文所提出的模型具有良好的预测性能。     

An integrated supplier selection and inventory problem with multi-sourcing and lateral transshipments

In this research, we consider the supplier selection problem of a firm offering a single product via multiple warehouses. The warehouses face stationary, stochastic demand and replenish their inventory via multiple suppliers, to be determined from a set of candidates, with varying price, capacity, quality, and disruption characteristics. Additionally, the warehouses may simultaneously replenish their inventory from other warehouses proactively. With these characteristics, the problem is a multi-sourcing, supplier selection, and inventory problem with lateral transshipments. Even though the benefits of multi-sourcing and lateral transshipments have been presented in the literature individually to mitigate risks associated with uncertain demand and disrupted supply, the intertwined sourcing and inventory decisions under these settings have not been investigated from a quantitative perspective. We develop a decomposition based heuristic algorithm, powered with simulation. While the decomposition based heuristic determines a solution with supplier selection and inventory decisions, the simulation model evaluates the objective function value corresponding to each generated solution. Experimental results show, contrary to the existing literature, inferior decisions may result when considering the selection of suppliers solely on unit and/or contractual costs. We also evaluate the impact of multi-sourcing with rare but long disruptions compared to frequent but short ones.     

Sports league scheduling: Graph- and resource-based models

Generating a sports league schedule is a challenging task due to the variety of different requirements which have to be addressed. This has led to a multitude of alternative approaches. Most of them rely on graph-theoretical concepts and the solution of the overall problem is based on the decomposition of the problem into certain subproblems. In this paper, we give a comprehensive survey of these more traditional approaches. Furthermore, we present a new resource-based model which shall serve as a starting point for the development of new solution algorithms.     

Decomposition algorithms for the integrated process planning and scheduling problem

There are several algorithms to solve the integrated process planning and scheduling (IPPS) problem (i.e., flexible job shop scheduling with process plan flexibility) in the literature. All the existing algorithms for IPPS are heuristic-based search methods and no research has investigated the use of exact solution methods for this problem. We develop several decomposition approaches based on the logic-based Benders decomposition (LBBD) algorithm. Our LBBD algorithm allows us to partition the decision variables in the IPPS problem into two models, master-problem and sub-problem. The master-problem determines process plan and operation-machine assignment, while the sub-problem optimizes sequencing and scheduling decisions. To achieve faster convergence, we develop two relaxations for the optimal makespan objective function and incorporate them into the master-problem. We analyze the performance and further enhance the algorithm with two ideas, a Benders optimality cut based on the critical path and a faster heuristic way to solve the sub-problem. 16 standard benchmark instances available in the literature are solved to evaluate and compare the performances of our algorithms with those of the state-of-the-art methods in the literature. The proposed algorithm either results in the optimal solution or improves the best-known solutions in all the existing instances, demonstrating its superiority to the existing state-of-the-art methods in literature.     

基于二阶段随机规划的城市医疗废弃物回收网络设计

城市医疗废弃物日益增加,且回收需求量受诸多因素的影响,难以准确预测,假定回收需求为确定值的医疗废弃物网络优化设计不能与实际需求相匹配。本文考虑了离散随机参数环境下,医疗回收网络设计中选址规划、分配计划及运输规划的协同优化问题,建立了以选址成本、运输成本最小为目标,设施与车辆能力限制为约束的二阶段随机规划模型。根据模型特点,设计了基于Benders decomposition的求解算法,同时,设计了一系列加速技术用于提高算法的求解效率。最后,以国内某城市医疗回收网络为背景设计算例,检验本文模型和求解策略的可行性和有效性。结果表明：相比确定性规划,随机规划的解能够节约总成本,结合一系列加速技术的Benders decomposition方法比CPLEX与纯的Benders decomposition更有优势。     

Logic-based Benders decomposition for an inventory-location problem with service constraints

We study an integrated inventory-location problem with service requirements faced by an aerospace company in designing its service parts logistics network. Customer demand is Poisson distributed and the service levels are time-based leading to highly non-linear, stochastic service constraints and a nonlinear, mixed-integer optimization problem. Unlike previous work in the literature, which propose approximations for the nonlinear constraints, we present an exact solution methodology using logic-based Benders decomposition. We decompose the problem to separate the location decisions in the master problem from the inventory decisions in the subproblem. We propose a new family of valid cuts and prove that the algorithm is guaranteed to converge to optimality. This is the first attempt to solve this type of problem exactly. Then, we present a new restrict-and-decompose scheme to further decompose the Benders master problem by part. We test on industry instances as well as random instances. Using the exact algorithm and restrict-and-decompose scheme we are able to solve industry instances with up to 60 parts within reasonable time, while the maximum number of parts attempted in the literature is 5.     

An improved linear convergence of FISTA for the LASSO problem with application to CT image reconstruction

Journal of Combinatorial Optimization - The LASSO problem has been explored extensively for CT image reconstruction, the most useful algorithm to solve the LASSO problem is the FISTA. In this...     

Metachoice for strategic analysis

A necessary precursor to strategic choice is the selection of a strategic choice evaluation method — metachoice. Unfortunately, managers are unlikely to find much guidance on how to conduct metachoice analysis in the strategy literature. In light of this problem, a template is presented based on two questions that must be addressed by those engaged in strategic analysis generally and metachoice specifically: (1) what are the organization's strategic goals? (2) how willing are they to monetize their predictions and valuations? Four resulting choice methods are presented and discussed: Discounted Cash Flow Analysis (including variants based on real options), Profitability Analysis, Modified Discounted Cash Flow Analysis and Multi-Goal Analysis.     

Efficient Benders decomposition for distance-based critical node detection problem

This paper addresses the critical node detection problem which seeks a subset of nodes for removal in order to maximize the disconnectivity of the residual graph with respect to a specific distance-based measure, namely the Wiener index. Such a measure is defined based on the all-pair shortest path distances in the residual graph so that the longer the total length of shortest paths, the greater the value of the disconnectivity measure. In the literature, a mixed integer linear programming model and an exact iterative-based method have been presented for this problem; however, both approaches become very time-consuming on graphs having large diameter and non-unit edge lengths. To overcome this shortcoming, in this paper, we present a new formulation for the problem and solve it by Benders decomposition algorithm. We improve the performance of Benders algorithm by several techniques (including analytical calculation of dual variables, generation of good-quality initial optimality cuts, considering master's optimality cuts as lazy constraints, etc.) to reduce the total running time. The extensive computational experiments on instances, taken from the literature or generated randomly, confirm the effectiveness of the new approaches.     

随机环境中的生产作业计划问题

生产系统中通常会涉及各种不确定因素 ,如不确定的顾客定单、不确定的生产作业时间等 .在当今时间竞争非常激烈的时代中 ,生产型企业如何把握生产系统中的这些不定因素变得尤为关键 .本文研究在不确定的作业时间、工序间延迟时间等情况下的生产作业计划问题 ,利用 scenario模型把这类随机生产计划问题归纳为一个多阶段随机决策问题 .进而 ,采用Lagrangian松弛和 scenario分解的方法求解这样一个大型的决策问题 .最后 ,就一个实例建立模型、进行计算和分析 ,以说明本文提出的随机生产计划方法的特点和有效性     

Algorithms for the minimum weight k-fold (connected) dominating set problem

In this paper, we study the problem of computing a minimum weight k-fold dominating set (MWkDS) or a minimum weight k-fold connected dominating set (MWkCDS) in a unit ball graph (UBG). Using slab decomposition and dynamic programming, we give two exact algorithms for the computation of MWkDS and MWkCDS which can be executed in polynomial time if the thickness of the graph is bounded above.     

Nonparametric Stochastic Discount Factor Decomposition

Stochastic discount factor (SDF) processes in dynamic economies admit a permanent‐transitory decomposition in which the permanent component characterizes pricing over long investment horizons. This paper introduces an empirical framework to analyze the permanent‐transitory decomposition of SDF processes. Specifically, we show how to estimate nonparametrically the solution to the Perron–Frobenius eigenfunction problem of Hansen and Scheinkman, 2009. Our empirical framework allows researchers to (i) construct time series of the estimated permanent and transitory components and (ii) estimate the yield and the change of measure which characterize pricing over long investment horizons. We also introduce nonparametric estimators of the continuation value function in a class of models with recursive preferences by reinterpreting the value function recursion as a nonlinear Perron–Frobenius problem. We establish consistency and convergence rates of the eigenfunction estimators and asymptotic normality of the eigenvalue estimator and estimators of related functionals. As an application, we study an economy where the representative agent is endowed with recursive preferences, allowing for general (nonlinear) consumption and earnings growth dynamics.