A PRACTICAL APPROACH TO THE LARGE-SCALE FOREST SCHEDULING PROBLEM*

A large-scale forest cutting schedule problem involving 1166 forest units to be cut over a 24–year planning period is discussed. The problem is formulated as a generalized version of the basic transportation problem. The conversion procedure for such a problem to the standard transportation format is outlined. The proposed approach is then compared with a linear programming decomposition approach on the basis of operating results obtained and computer time required by each approach. It is shown that this new approach will solve a real world problem about 40 times faster than the usual linear programming decomposition approach.     

可变维核心矩阵LU分解方法

在线性规划问题的发展过程中,基的分解技术一直是求解线性规划问题算法实现的一个重要问题。在传统的线性规划算法中,基逆的乘积形式(PFI)方法和LU分解方法很好的解决了基逆的稀疏性、累计误差等问题。随着线性规划动态分解和核心矩阵的出现,矩阵的动态分解成为了一个新的研究课题。本文主要研究和分析单纯形算法中的核心矩阵的动态分解和存储方法,将经典的LU分解方法应用于核心矩阵的动态分解和存储中,保持了核心距阵的数值稳定性和稀疏性。同时,本文提出置换消元方法可以大大减少LU更新的时间。     

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.     

On Integer Programming Approaches for Morphological Template Decomposition Problems in Computer Vision

In morphological image processing and analysis, a template or structuringelement is applied to an image. Often savings in computation time and abetter fit to the given computer architecture can be achieved by using thetechnique of template decomposition. Researchers have written a multitude ofpapers on finding such decompositions for special classes of templates.Justifying recent integer programming approaches to the morphologicaltemplate decomposition problem in its general form, this paper proves theNP-completeness of this problem.     

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

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

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.     

Branch-and-Bound Strategies for the Log Bucking Problem

Tree bucking is the initial production process in converting felled trees into useable wood products. This process has been previously modelled as a dynamic programming problem. Unlike other production problems that have been modelled as dynamic programming problems, there have been no serious attempts to formulate this problem as a branch-and-bound model and then examine the model's performance. This research develops the tree bucking problem as a branch-and-bound model to be tested by varying several parameters. The testing is performed in two phases: (1) a sensitivity analysis is performed to test two key parameters used by the model, and (2) branching strategies are tested on various problem scenarios. The size of the solution sets searched by the technique vary from as low as 40 to as many as 41,000 possible combinations.     

The bandpass problem: combinatorial optimization and library of problems

A combinatorial optimization problem, called the Bandpass Problem, is introduced. Given a rectangular matrix A of binary elements {0,1} and a positive integer B called the Bandpass Number, a set of B consecutive non-zero elements in any column is called a Bandpass. No two bandpasses in the same column can have common rows. The Bandpass problem consists of finding an optimal permutation of rows of the matrix, which produces the maximum total number of bandpasses having the same given bandpass number in all columns. This combinatorial problem arises in considering the optimal packing of information flows on different wavelengths into groups to obtain the highest available cost reduction in design and operating the optical communication networks using wavelength division multiplexing technology. Integer programming models of two versions of the bandpass problems are developed. For a matrix A with three or more columns the Bandpass problem is proved to be NP-hard. For matrices with two or one column a polynomial algorithm solving the problem to optimality is presented. For the general case fast performing heuristic polynomial algorithms are presented, which provide near optimal solutions, acceptable for applications. High quality of the generated heuristic solutions has been confirmed in the extensive computational experiments. As an NP-hard combinatorial optimization problem with important applications the Bandpass problem offers a challenge for researchers to develop efficient computational solution methods. To encourage the further research a Library of Bandpass Problems has been developed. The Library is open to public and consists of 90 problems of different sizes (numbers of rows, columns and density of non-zero elements of matrix A and bandpass number B), half of them with known optimal solutions and the second half, without.     

混合离散差分进化算法在单机批处理调度中的应用

本文研究单机批处理调度问题,批处理机有批次容量限制,批处理时间由每个批次所含作业中的最长作业处理时间决定。每个作业具有不同的大小、处理时间、提前拖期惩罚权重,所有作业具有公共交货期,且交货期无限晚。目标函数为最小化所有作业的加权提前拖期惩罚之和。该问题已被证明为NP难题,本研究找到了其最优解具有的一些性质,在此基础上利用它们提出了一种动态规划(DP)与差分进化(DE)算法相结合的混合离散差分进化(HDDE)算法来求解该问题,通过与传统的遗传算法、模拟退火算法和迭代贪婪算法进行对比,HDDE算法显示了更加强大的全局搜索能力。     

A Note on “An Efficient Zero-One Formulation of the Multilevel Lot-Sizing Problem”

In a recent paper, McKnew, Saydam, and Coleman [3] presented a novel zero-one integer programming formulation of the multilevel dynamic, deterministic lot-sizing problem in assembly systems. They stated that “the relaxed linear programming solution to this formulation will always be integer’ [3, p. 280] since the constraint matrix is totally unimodular. In this note, we point out that the constraint matrix is not totally unimodular and therefore the authors’claim that a linear relaxation of the zero-one integer formulation always yields an integer solution is not true.     

A fast FPTAS for single machine scheduling problem of minimizing total weighted earliness and tardiness about a large common due date

We address the single machine scheduling problem to minimize the total weighted earliness and tardiness about a nonrestrictive common due date. This is a basic problem with applications to the just-in-time manufacturing. The problem is linked to a Boolean programming problem with a quadratic objective function, known as the half-product. An approach to developing a fast fully polynomial-time approximation scheme (FPTAS) for the problem is identified and implemented. The running time matches the best known running time for an FPTAS for minimizing a half-product with no additive constant.     

Coordinated Capacitated Lot‐Sizing Problem with Dynamic Demand: A Lagrangian Heuristic

Coordinated replenishment problems are common in manufacturing and distribution when a family of items shares a common production line, supplier, or a mode of transportation. In these situations the coordination of shared, and often limited, resources across items is economically attractive. This paper describes a mixed‐integer programming formulation and Lagrangian relaxation solution procedure for the single‐family coordinated capacitated lot‐sizing problem with dynamic demand. The problem extends both the multi‐item capacitated dynamic demand lot‐sizing problem and the uncapacitated coordinated dynamic demand lot‐sizing problem. We provide the results of computational experiments investigating the mathematical properties of the formulation and the performance of the Lagrangian procedures. The results indicate the superiority of the dual‐based heuristic over linear programming‐based approaches to the problem. The quality of the Lagrangian heuristic solution improved in most instances with increases in problem size. Heuristic solutions averaged 2.52% above optimal. The procedures were applied to an industry test problem yielding a 22.5% reduction in total costs.     

Maximum latency scheduling problem on two-person cooperative games

This paper studies a two-person cooperative game in which a set of jobs has to be processed jointly by two people. Each of them has a single machine and his processing cost is defined as the minimum value of the maximum latency of his negotiably assigned jobs. The objective is to maximize the multiplication of their rational positive cooperative profits. In the case where all jobs have the same processing time, if they have a common due date, the problem is polynomial-time solvable; if due dates can be different, there exits an optimal schedule in which the jobs assigned to each person are scheduled in Earlier Due Date first (EDD) order and a polynomial-time dynamic programming is further proposed. In the case where processing times can be different, the NP-completeness of this problem is proved, and a pseudo-polynomial-time dynamic programming algorithm is developed.     

A note on pre-emptive scheduling with earliness and tardiness costs

The option of pre-emption seems to have escaped the attention of existing literature on scheduling problems with earliness and tardiness costs. This note presents an attempt to accommodate pre-emption in such settings. The focus is on models with a common due date for all jobs under different cost structures ( job dependent versus job independent), and different objectives ( minsum and minmax). It appears that only one of these cases is not polynomially solvable: the case of minsum objective and job-dependent ( linear) cost. An exact dynamic programming algorithm is introduced for this problem, as well as an efficient heuristic, which is shown to perform extremely well in our numerical tests.     

一种具有不确定偏好序信息的多指标群决策方法

针对具有不确定偏好序信息的多指标群决策问题,给出了一种决策分析方法。在本文中,首先对具有不确定偏好序信息的多指标群决策问题进行了描述;然后给出了将不确定偏好序转换为投票数的计算公式;进一步地,依据Bernardo方法的基本思想,根据每个专家给出的不确定偏好序信息,计算相应的投票数并构建群体投票矩阵,并基于群体投票矩阵构建0-1整数规划模型,通过求解模型可得到方案排序结果。最后,通过一个算例以及与已有方法的对比分析说明了本文给出的方法的可行性和有效性。     

Linear programming approach to solve interval-valued matrix games

Matrix game theory is concerned with how two players make decisions when they are faced with known exact payoffs. The aim of this paper is to develop a simple and an effective linear programming method for solving matrix games in which the payoffs are expressed with intervals. Because the payoffs of the matrix game are intervals, the value of the matrix game is an interval as well. Based on the definition of the value for matrix games, the value of the matrix game may be regarded as a function of values in the payoff intervals, which is proven to be non-decreasing. A pair of auxiliary linear programming models is formulated to obtain the upper bound and the lower bound of the value of the interval-valued matrix game by using the upper bounds and the lower bounds of the payoff intervals, respectively. By the duality theorem of linear programming, it is proven that two players have the identical interval-type value of the interval-valued matrix game. Also it is proven that the linear programming models and method proposed in this paper extend those of the classical matrix games. The linear programming method proposed in this paper is demonstrated with a real investment decision example and compared with other similar methods to show the validity, applicability and superiority.     

Column generation approach for the point-feature cartographic label placement problem

This paper proposes a column generation approach for the Point-Feature Cartographic Label Placement problem (PFCLP). The column generation is based on a Lagrangean relaxation with clusters proposed for problems modeled by conflict graphs. The PFCLP can be represented by a conflict graph where vertices are positions for each label and edges are potential overlaps between labels (vertices). The conflict graph is decomposed into clusters forming a block diagonal matrix with coupling constraints that is known as a restricted master problem (RMP) in a Dantzig-Wolfe decomposition context. The clusters’ sub-problems are similar to the PFCLP and are used to generate new improved columns to RMP. This approach was tested on PFCLP instances presented in the literature providing in reasonable times better solutions than all those known and determining optimal solutions for some difficult large-scale instances.     

The Flow Shop Scheduling Polyhedron with Setup Times

This paper addresses the problem of improving the polyhedral representation of a certain class of machine scheduling problems. Despite the poor polyhedral representation of many such problems in general, it is shown that notably tighter linear programming representations can be obtained for many important models. In particular, we study the polyhedral structure of two different mixed-integer programming formulations of the flow shop scheduling problem with sequence-dependent setup times, denoted by SDST flow shop. The first is related to the asymmetric traveling salesman problem (ATSP) polytope. The second is less common and is derived from a model proposed by Srikar and Ghosh based on the linear ordering problem (LOP) polytope. The main contribution of this work is the proof that any facet-defining inequality (facet) of either of these polytopes (ATSP and LOP) induces a facet for the corresponding SDST flow shop polyhedron. The immediate benefit of this result is that all developments to date on facets and valid inequalities for both the ATSP and the LOP can be applied directly to the machine scheduling polytope. In addition, valid mixed-integer inequalities based on variable upper-bound flow inequalities for either model are developed as well. The derived cuts are evaluated within a branch-and-cut framework.