Approximate and Exact Algorithms for Constrained (Un) Weighted Two-dimensional Two-staged Cutting Stock Problems

In this paper we propose two algorithms for solving both unweighted and weighted constrained two-dimensional two-staged cutting stock problems. The problem is called two-staged cutting problem because each produced (sub)optimal cutting pattern is realized by using two cut-phases. In the first cut-phase, the current stock rectangle is slit down its width (resp. length) into a set of vertical (resp. horizontal) strips and, in the second cut-phase, each of these strips is taken individually and chopped across its length (resp. width).First, we develop an approximate algorithm for the problem. The original problem is reduced to a series of single bounded knapsack problems and solved by applying a dynamic programming procedure. Second, we propose an exact algorithm tailored especially for the constrained two-staged cutting problem. The algorithm starts with an initial (feasible) lower bound computed by applying the proposed approximate algorithm. Then, by exploiting dynamic programming properties, we obtain good lower and upper bounds which lead to significant branching cuts. Extensive computational testing on problem instances from the literature shows the effectiveness of the proposed approximate and exact approaches.     

A Note on the Max-Min 0-1 Knapsack Problem

In this paper we propose new lower and upper bounds for the max-min 0-1 knapsack problem, employing a mixture of two relaxations. In addition, in order to expose whether the bounds are practical or not, we implement a method incorporating the bounds to achieve an optimal solution of the problem.     

Attacking the Market Split Problem with Lattice Point Enumeration

The market split problem was proposed by Cornuéjols and Dawande as benchmark problem for algorithms solving linear systems with 0/1 variables. Here, we present an algorithm for the more general problem A · x = b with arbitrary lower and upper bound on the variables. The algorithm consists of exhaustive enumeration of all points of a suitable lattice which are contained in a given polyhedron. We present results for the feasibility version as well as for the integer programming version of the market split problem which indicate that the algorithm outperforms the previously published approaches to this problems considerably.     

Plausible Upper Bounds: Are Their Sums Plausible?1

Quantitative cancer risk assessments are typically expressed as plausible upper bounds rather than estimates of central tendency. In analyses involving several carcinogens, these upper bounds are often summed to estimate overall risk. This begs the question of whether a sum of upper bounds is itself a plausible estimate of overall risk. This question can be asked in two ways: whether the sum yields an improbable estimate of overall risk (that is, is it only remotely possible for the true sum of risks to match the sum of upper bounds), or whether the sum gives a misleading estimate (that is, is the true sum of risks likely to be very different from the sum of upper bounds). Analysis of four case studies shows that as the number of risk estimates increases, their sum becomes increasingly improbable, but not misleading. Though the overall risk depends on the independence, additivity, and number of risk estimates, as well as the shapes of the underlying risk distributions, sums of upper bounds provide useful information about the overall risk and can be adjusted downward to give a more plausible [perhaps probable] upper bound, or even a central estimate of overall risk.     

A hybrid heuristic for the uncapacitated single allocation hub location problem

The uncapacitated single allocation hub location problem (USAHLP), with the hub-and-spoke network structure, is a decision problem in regard to the number of hubs and location–allocation. In a pure hub-and-spoke network, all hubs, which act as switching points for internodal flows, are interconnected and none of the non-hubs (i.e., spokes) are directly connected. The key factors for designing a successful hub-and-spoke network are to determine the optimal number of hubs, to properly locate hubs, and to allocate the non-hubs to the hubs. In this paper two approaches to determine the upper bound for the number of hubs along with a hybrid heuristic based on the simulated annealing method, tabu list, and improvement procedures are proposed to resolve the USAHLP. Computational experiences indicate that by applying the derived upper bound for the number of hubs the proposed heuristic is capable of obtaining optimal solutions for all small-scaled problems very efficiently. Computational results also demonstrate that the proposed hybrid heuristic outperforms a genetic algorithm and a simulated annealing method in solving USAHLP.     

A successive approximation algorithm for the multiple knapsack problem

It is well-known that the multiple knapsack problem is NP-hard, and does not admit an FPTAS even for the case of two identical knapsacks. Whereas the 0-1 knapsack problem with only one knapsack has been intensively studied, and some effective exact or approximation algorithms exist. A natural approach for the multiple knapsack problem is to pack the knapsacks successively by using an effective algorithm for the 0-1 knapsack problem. This paper considers such an approximation algorithm that packs the knapsacks in the nondecreasing order of their capacities. We analyze this algorithm for 2 and 3 knapsack problems by the worst-case analysis method and give all their error bounds.     

The weighted link ring loading problem

In the weighted link ring loading problem, we are given an n-node undirected ring network. Each of its links is associated with a weight. Traffic demands are given for each pair of nodes in the ring. The load of a link is the sum of the flows routed through the link, and the weighted load of a link is the product of its weight and the smallest integer not less than its load. The objective of the problem is to find a routing scheme such that the maximum weighted load on the ring is minimized. In this paper we consider three variants: (i) demands may be split into two parts, and then each part is sent in a different direction; (ii) demands are allowed to be split into two parts but restricted to be integrally split; (iii) each demand must be entirely routed in either of the two directions, clockwise or counterclockwise. We first prove that the first variant is polynomially solvable. We then present a pseudo-polynomial time algorithm for the second one. Finally, for the third one, whose NP-hardness can be drawn from the result in the literature, we derive a polynomial-time approximation scheme (PTAS).     

基于遗传算法的具有主次仓库的企业资源供应链管理模型研究

本文研究如何在有容量限制的主次仓库间分配客户需求的企业资源供应链管理问题,当主仓库不能满足客户需求时,通过一个次仓库弥补主仓库的不足。首先把该问题构造成一个整数规划模型,其次,运用遗传算法加以解决,实际应用和数值分析说明了该遗传算法在解决这类问题中的有效性和实用生。     

基于随机p-鲁棒优化的国家血液战略储备库选址-库存模型

以往的救灾实践对建立国家血液战略储备体系提出了迫切要求。国家血液战略储备库的建设问题亟待解决。由于血液产品特性以及应急血液保障特性的存在，使得国家血液战略储备库的选址决策具有一定的复杂性。本文将问题定位为选址-库存问题。首先，以应急条件下血液保障及时度最高为目标，构建了一个不确定环境下考虑多情景、多血型、多阶段、带提前期、有容量限制、日常随机需求、有预算约束及协同定位的国家血液战略储备库选址-库存模型。同时，为了规避应急条件下的不确定风险，进一步构建了国家血液战略储备库选址-库存问题的随机p-鲁棒优化模型。该模型为离散非线性混合整数规划模型，难以快速精确求解。故基于模型性质，设计了相应的遗传算法。最后，设计了两组算例验证模型与算法的有效性。其中，第1组算例基于我国大陆地区31个省级血液中心与省级行政区的数据，并根据不同预算值给出6个算例，得到了国家血液战略储备库的选址-库存决策方案。第2组算例为6个不同规模的模拟算例，用来测试不同规模下的算法性能。算例结果表明：遗传算法的性能更好；鲁棒解与确定性模型最优值相差不大（最大差距≤1.08%），可降低不确定性导致的风险。实践中，可对本文所建模型稍作改进，应用于具有类似特征的易腐品（药品、粮食等）应急物资储备库选址-库存决策。     

Constraining the number of positive responses in adaptive,non-adaptive,and two-stage group testing

Group testing is a well known search problem that consists in detecting the defective members of a set of objects O by performing tests on properly chosen subsets (pools) of the given set O. In classical group testing the goal is to find all defectives by using as few tests as possible. We consider a variant of classical group testing in which one is concerned not only with minimizing the total number of tests but aims also at reducing the number of tests involving defective elements. The rationale behind this search model is that in many practical applications the devices used for the tests are subject to deterioration due to exposure to or interaction with the defective elements. In this paper we consider adaptive, non-adaptive and two-stage group testing. For all three considered scenarios, we derive upper and lower bounds on the number of “yes” responses that must be admitted by any strategy performing at most a certain number t of tests. In particular, for the adaptive case we provide an algorithm that uses a number of “yes” responses that exceeds the given lower bound by a small constant. Interestingly, this bound can be asymptotically attained also by our two-stage algorithm, which is a phenomenon analogous to the one occurring in classical group testing. For the non-adaptive scenario we give almost matching upper and lower bounds on the number of “yes” responses. In particular, we give two constructions both achieving the same asymptotic bound. An interesting feature of one of these constructions is that it is an explicit construction. The bounds for the non-adaptive and the two-stage cases follow from the bounds on the optimal sizes of new variants of d-cover free families and (p, d)-cover free families introduced in this paper, which we believe may be of interest also in other contexts.     

On the number of local minima for the multidimensional assignment problem

The Multidimensional Assignment Problem (MAP) is an NP-hard combinatorial optimization problem occurring in many applications, such as data association, target tracking, and resource planning. As many solution approaches to this problem rely, at least partly, on local neighborhood search algorithms, the number of local minima affects solution difficulty for these algorithms. This paper investigates the expected number of local minima in randomly generated instances of the MAP. Lower and upper bounds are developed for the expected number of local minima, E[M], in an MAP with iid standard normal coefficients. In a special case of the MAP, a closed-form expression for E[M] is obtained when costs are iid continuous random variables. These results imply that the expected number of local minima is exponential in the number of dimensions of the MAP. Our numerical experiments indicate that larger numbers of local minima have a statistically significant negative effect on the quality of solutions produced by several heuristic algorithms that involve local neighborhood search.Partially supported by the NSF grant DMI-0457473.     

带货物权重的车辆路径问题及遗传算法

考虑一个分销中心、多个零售商组成的分销网络系统中具有柔性车辆能力的带货物权重的车辆路径问题.并根据车辆的满载情况采用了不同的运输策略,即单点运输和多点运输方式.在多点运输方式下,与以往诸多研究不同的是,文章建立了一种基于货物权重的VRP模型——WVRP,即在安排车辆线路时每个零售商的货物需求量也作为一个因素考虑,尽可能使车辆优先供货需求量较大的零售商.最后,针对问题的性质,开发了一种基于划分的遗传算法PB-GA对问题进行求解,并与一般遗传算法及常用的启发式算法进行了分析比较.     

Bounding Optimal Expected Revenues for Assortment Optimization under Mixtures of Multinomial Logits

We consider assortment problems under a mixture of multinomial logit models. There is a fixed revenue associated with each product. There are multiple customer types. Customers of different types choose according to different multinomial logit models whose parameters depend on the type of the customer. The goal is to find a set of products to offer so as to maximize the expected revenue obtained over all customer types. This assortment problem under the multinomial logit model with multiple customer types is NP‐complete. Although there are heuristics to find good assortments, it is difficult to verify the optimality gap of the heuristics. In this study, motivated by the difficulty of finding optimal solutions and verifying the optimality gap of heuristics, we develop an approach to construct an upper bound on the optimal expected revenue. Our approach can quickly provide upper bounds and these upper bounds can be quite tight. In our computational experiments, over a large set of randomly generated problem instances, the upper bounds provided by our approach deviate from the optimal expected revenues by 0.15% on average and by less than one percent in the worst case. By using our upper bounds, we are able to verify the optimality gaps of a greedy heuristic accurately, even when optimal solutions are not available.     

A refined algorithm for maximum independent set in degree-4 graphs

The maximum independent set problem is one of the most important problems in theoretical analysis on time and space complexities of exact algorithms. Theoretical improvement on upper bounds on time complexity to solve this problem in low-degree graphs can lead to an improvement on that to the problem in general graphs. In this paper, we derive an upper bound \(O^*(1.1376^n)\) on the time complexity of a polynomial-space algorithm that solves the maximum independent set problem in an n-vertex graph with degree bounded by 4, improving all previous upper bounds on the time complexity of exact algorithms to this problem. Our algorithm is a branch-and-reduce algorithm and analyzed by using the measure-and-conquer method. To make an amortized analysis of the running time bound, we use an idea of “shift” to save some decrease of the measure from good branches to bad branches. Our algorithm first deals with small vertex cuts and vertices of degree \({\ge }5\), which may be created in our algorithm even if the input graph has maximum degree 4, then eliminates cycles of length 3 and 4 containing degree-4 vertices, and finally branches on degree-4 vertices. We invoke an exact algorithm for this problem in graphs with maximum degree 3 directly when the graph has no vertices of degree \({\ge }4\). Branching on degree-4 vertices on special local structures will be the bottleneck case, and we carefully design rules of choosing degree-4 vertices to branch on so that the resulting instances after branching decrease the measure effectively in the next step.     

Managing stochastic demand in an Inventory Routing Problem with transportation procurement

We study an Inventory Routing Problem in which the supplier has a limited production capacity and the stochastic demand of the retailers is satisfied with procurement of transportation services. The aim is to minimize the total expected cost over a planning horizon, given by the sum of the inventory cost at the supplier, the inventory cost at the retailers, the penalty cost for stock-out at the retailers and the transportation cost. First, we show that a policy based just on the average demand can have a total expected cost infinitely worse than the one obtained by taking into account the overall probability distribution of the demand in the decision process. Therefore, we introduce a stochastic dynamic programming formulation of the problem that allows us to find an optimal policy in small size instances. Finally, we design and implement a matheuristic approach, integrating a rollout algorithm and an optimal solution of mixed-integer linear programming models, which is able to solve realistic size problem instances. Computational results allow us to provide managerial insights concerning the management of stochastic demand.     

Iterative Converging Algorithms for Computing Bounds on Durations of Activities in Pert and Pert-Like Models

Since its invention in 1958, Program Evaluation and Review Technique (PERT) has been widely used during the planning, design, and implementation of projects. Pert models the activities of a project as a single source-single sink directed acyclic graph where nodes represent events (end or beginning of activities) and arcs activities. The maximum amount by which an activity can be delayed without delaying the overall project is called the slack. Critical tasks have zero slack whereas all noncritical tasks have positive slacks. Pert is a valuable tool in the management of large projects since it allows to compute the slack of each activity of the project. Such information may be crucial in avoiding cost overruns that would be caused by delays to critical activities and/or excessive delays to noncritical activities. What Pert fails to provide is how one should go about distributing remaining slack on noncritical activities while taking into consideration properties of the activities as well as precedence relationships among them, so as to have reasonable upper bounds on duration of all activities, critical or noncritical. In this paper we propose several algorithms for the distribution of slack on non-critical activities. We show that if one desires to distribute the remaining slack proportionally to the initially assigned activity durations then the problem is in P, and propose an algorithm of linear time complexity. However if one desires to use distribution functions other than the initial durations of activities, then the problem of slack distribution becomes NP-complete. Finding the maximal bounds corresponding to zero-slack solution at the sink requires iterative application of exponential algorithm. For that case we introduce an approximation algorithm of linear time complexity on each iteration. The algorithm iteratively increases bounds on durations of activities and converges to the zero-slack solution on all paths from the source node to the sink node in the Pert-like graph. The algorithms described in this paper were successfully applied to solving timing bounds problems in VLSI design.     

突发公共事件应急系统中的模糊多目标定位-路径问题研究

本文从应急系统集成优化的角度出发,以应急系统中各资源需求点的应急救援时间满意度之和最大及系统总成本最小为目标,建立了一个应急资源需求和应急救援时间范围均模糊的多目标定位-路径问题(LRP)模型,并提出了一种混合多目标遗传算法。算例分析结果表明,所提模型和算法可以有效解决应急系统优化中的模糊多目标LRP。     

联合订货区间值EOQ模型及变权Shapley值成本分摊方法

研究多个销售商企业组成联盟向一个供应商订购同种商品的联合订货问题。考虑到实际问题中很难预测到精确的需求，本文用区间表示单位时间需求量，研究允许缺货的销售商企业联合订货区间值EOQ模型，其中缺货完全回补。以联合订货平均成本最小为目标，结合连续有序加权集结算子求解出联合订货的周期、区间值订货量和区间值平均成本。定义变权Shapley值，给出区间值合作博弈的区间值变权Shapley值的求解方法，得出区间值变权Shapley值的表达式可直接利用相关联盟值的左、右端点计算得到。考虑联盟和局中人的相对重要性，结合需求率确定合成权重，提出基于区间值变权Shapley值的联合订货成本分摊方法。利用数值算例验证模型和方法的有效性。本文可为解决联合订货成本分摊问题提供决策参考。     

Reduced costs propagation in an efficient implicit enumeration for the 01 multidimensional knapsack problem

In a previous work we proposed a variable fixing heuristics for the 0-1 Multidimensional knapsack problem (01MDK). This approach uses fractional optima calculated in hyperplanes which contain the binary optimum. This algorithm obtained best lower bounds on the OR-Library benchmarks. Although it is very attractive in terms of results, this method does not prove the optimality of the solutions found and may fix variables to a non-optimal value. In this paper, we propose an implicit enumeration based on a reduced costs analysis which tends to fix non-basic variables to their exact values. The combination of two specific constraint propagations based on reduced costs and an efficient enumeration framework enable us to fix variables on the one hand and to prune significantly the search tree on the other hand. Experimentally, our work provides two main contributions: (1) we obtain several new optimal solutions on hard instances of the OR-Library and (2) we reduce the bounds of the number of items at the optimum on several harder instances.     

Scheduling with machine cost and rejection

In this paper we consider the scheduling problem with machine cost and rejection penalties. For this problem, we are given a sequence of independent jobs, each being characterized by its processing time (size) and its penalty. No machine is initially provided, and when a job is revealed the algorithm has the option to purchase new machines. Right when a new job arrives, we have the following choices: (i) reject it, in which case we pay its penalty; (ii) non-preemptively process it on an existing machine, which contributes to the machine load; (iii) purchase a new machine, and assign it to this machine. The objective is to minimize the sum of the makespan, the cost for purchasing machines, and the total penalty of all rejected jobs. For the small job case, (where all jobs have sizes no greater than the cost for purchasing one machine, and which is the generalization of the Ski-Rental Problem) we present an optimal online algorithm with a competitive ratio of 2.