Medial Axis and Optimal Locations for Min-Max Sphere Packing

We study the following min-max sphere packing problem originated from radiosurgical treatment planning using gamma knife (Bourland and Wu, 1996; Wu, 1996). Given an input (R, V), where R is a 3-dimensional (3D) bounded region and V a positive integer, find a packing of R using the minimum number of spheres (spheres may not be identical) such that the covered volume is at least V, and the number of points on the boundary of R touched by spheres is maximized. Bourland and Wu (1996) and Wu (1996), devised a greedy algorithm to solve the problem based on medial axis analysis. In particular, the algorithm places the center of each sphere on the medial axis of each subsequent region starting from R. While this approach has met with certain success, we show that medial axis does not always provide optimal locations for min-max sphere packing.     

自动化立体仓库中的储位分配及存取路径优化

储位分配和存取作业路径优化是仓储管理中的两个重要决策问题。本文研究如何在自动化立体仓库中对这两个问题进行同时决策。提出了一个混合整数规划模型对该问题进行优化建模,设计开发了一个基于有向连接图的两阶段优化算法对问题求初始解,并利用禁忌搜索算法对所求得的解进行改进。算法第一阶段解决储位分配问题,在此基础上第二阶段利用Hungarian算法对堆垛机的存取作业路径优化问题进行求解。最后利用实例对算法效率和精度进行分析评价,计算结果验证了算法的有效性。     

On the fractionality of the path packing problem

Given an undirected graph G=(N,E), a subset T of its nodes and an undirected graph (T,S), G and (T,S) together are often called a network. A?collection of paths in G whose end-pairs lie in S is called an integer multiflow. When these paths are allowed to have fractional weight, under the constraint that the total weight of the paths traversing a single edge does not exceed 1, we have a fractional multiflow in G. The problems of finding the maximum weight of paths with end-pairs in S over all fractional multiflows in G is called the fractional path packing problem. In 1989, A. Karzanov had defined the fractionality of the fractional path packing problem for a class of networks {G,(T,S)} as the smallest natural D such that for any network from the class, the fractional path packing problem has a solution which becomes integer-valued when multiplied by D (see A.?Karzanov in Linear Algebra Appl. 114–115:293–328, 1989). He proved that the fractional path packing problem has infinite fractionality outside a very specific class of networks, and conjectured that within this class, the fractionality does not exceed 4. A.?Karzanov also proved that the fractionality of the path packing problem is at most 8 by studying the fractionality of the dual problem. Special cases of Karzanov’s conjecture were proved in or are implied by the works of L.R.?Ford and D.R.?Fulkerson, Y.?Dinitz, T.C.?Hu, B.V.?Cherkassky, L.?Lov?sz and H.?Hirai. We prove Karzanov’s conjecture by showing that the fractionality of the path packing problem is at most 4. Our proof is stand-alone and does not rely on Karzanov’s results.     

Genetic algorithms for optimization of a mine system under uncertainty

The production planning of a mine system associated with mining, processing and refining stages dictates to determine optimal system parameters such as optimal production rates, location of refining facility and the best reconstruction time of production rates. This paper proposes a combination of the chance constrained programming (CCP) and the genetic algorithms (GA) to find the optimal system parameters simultaneously. In generic form the problem is expressed as the maximization of net present value of future cash flows such that the capacity constraint and predefined specifications are satisfied. The blending requirements expressed in the CCP are transformed into deterministic equivalents. A new form of the problem is solved by the GA. The approach was demonstrated on extraction, processing and refining of four iron ore mines with varying reserves, ore qualities, geological and topographic conditions, four mineral processing units and one refining facility. The results showed that the proposed algorithm could be used to determine optimal production rates, the facility location and the best reconstruction time.     

Models and methods for workforce planning under uncertainty: Optimizing U.S. Army cyber branch readiness and manning

This work examines the problem of optimally resourcing personnel for a new set of U.S. Army cyber-specialty career fields using a combination of personnel accessions and inter-career-field transfers that are limited to occur over a subset of periods early within a 30-year career cycle. This workforce planning problem is bounded by constraints respectively pertaining to organizational needs for personnel, as well as personnel promotion policies. Complicating the problem are stochastic retention rates for every combination of year and promotion level within each career field over the 30-year period. Upon formalizing this Cyber Workforce Planning Problem (CWPP) within the framework of multiple performance goals, this study formulates, tests, and compares three frameworks to seek optimal workforce planning decisions under uncertainty: two stochastic programming (SP) variants and a robust optimization (RO) representation. Upon sampling the stochastic parametric distributions to generate a set of collectively representative, deterministic scenarios, the SP variants respectively leverage a scenario-based Monte Carlo approach and sample average approximation, whereas the RO model examines robust solutions over a range of decision-maker risk attitudes. A sensitivity analysis applied to the first of the SP variants indicates the solutions are relatively insensitive to different prioritizations of goals, and identifies policy insights to help recruit and retain personnel. Comparative testing of the three methodologies yields workforce planning recommendations that are relatively consistent across solution methodologies and identify concerns to inform changes to personnel policies.     

Bin packing under linear constraints

In this paper, we study a bin packing problem in which the sizes of items are determined by k linear constraints, and the goal is to decide the sizes of items and pack them into a minimal number of unit sized bins. We first provide two scenarios that motivate this research. We show that this problem is NP-hard in general, and propose several algorithms in terms of the number of constraints. If the number of constraints is arbitrary, we propose a 2-approximation algorithm, which is based on the analysis of the Next Fit algorithm for the bin packing problem. If the number of linear constraints is a fixed constant, then we obtain a PTAS by combining linear programming and enumeration techniques, and show that it is an optimal algorithm in polynomial time when the number of constraints is one or two. It is well known that the bin packing problem is strongly NP-hard and cannot be approximated within a factor 3 / 2 unless P = NP. This result implies that the bin packing problem with a fixed number of constraints may be simper than the original bin packing problem. Finally, we discuss the case when the sizes of items are bounded.     

基于遗传算法的微电网负荷优化分配

负荷优化分配是电力系统中的一类重要优化问题,即在满足各类系统约束条件下,实现发电总成本最低。为了促进微电网的优化运行,本文研究了包含柴油发电机、微型燃气轮机、光伏发电机和风力发电机组成的微电网的负荷优化分配问题。首先简要分析了各个微电源的发电特征和成本函数,然后分别建立了孤岛模式和并网模式下的微电网负荷优化分配模型,孤岛模式下优化模型的目标函数是包含燃料成本和运行维护成本的总成本,约束条件包括发电能力约束和系统功率平衡约束,并网模式下的优化模型则在此基础上,在目标函数中增加了其与大电网交易的收入和支出,在约束条件中增加了电力交易约束。最后,通过遗传算法分别对两种模式下的优化模型进行仿真求解。结果表明,本文提出的负荷优化分配方法可以有效降低微电网的运行成本,促进微电网的优化运行。     

带学习效应的双渠道供应链库存策略研究

针对具有学习行为的双渠道供应链问题,本文研究了两种分销渠道并存下的最优库存策略。有限计划期内,分销商通过传统销售和在线销售来满足下游顾客的需求。两种分销渠道下的销售单价为时变不减线性函数,当系统中各周期的生产订购固定成本以一定的概率具有学习效应行为时,分别建立了非变质产品生产存贮问题的混合整数约束优化模型以及易变质产品存贮问题的无约束混合整数优化模型,所建立模型的目标为极大化分销商总利润函数。对于这两类模型,通过分析其最优解的性质,利用将生产订购次数松弛为连续变量的技巧证明了最优解存在的唯一性。给出了最优策略的求解方法并比较了两类模型最优利润函数值的大小。最后通过数值算例对上述模型进行了验证,数值结果表明当供应链系统中存在学习效应行为时,该系统能够获得更多的利润。     

期望未来损失约束下的最优投资问题

在标准的Black-Scholes 型金融市场下,建立了期望未来损失( expected future loss;EFL)约束下基于终端财富效用最大化的投资组合选择模型.运用鞅和优化方法,得到了一般效用投资者在投资计划期内任意时刻的最优财富和最优投资组合选择策略.在对数效用函数下,得到了投资者在投资计划期内任意时刻的最优财富和最优投资组合选择策略的显式表达式.     

An efficient approach for searching optimal multi-keywords coverage routes

Journal of Combinatorial Optimization - Keyword-aware optimal route queries are a combinatorial optimization problem with three factors, namely keyword coverage, route budget constraint and route...     

A Case Study of De-randomization Methods for Combinatorial Approximation Algorithms

We study three different de-randomization methods that are often applied to approximate combinatorial optimization problems. We analyze the conditional probabilities method in connection with randomized rounding for routing, packing and covering integer linear programming problems. We show extensions of such methods for non-independent randomized rounding for the assignment problem. The second method, the so-called random walks is exemplified with algorithms for dense instances of some NP problems. Another often used method is the bounded independence technique; we explicit this method for the sparsest cut and maximum concurrent flow problems.     

Integrated Order Scheduling and Packing

We consider an integrated production–distribution scheduling model in a make‐to‐order supply chain consisting of one supplier and one customer. The supplier receives a set of orders from the customer at the beginning of a planning horizon. The supplier needs to process all the orders at a single production line, pack the completed orders to form delivery batches, and deliver the batches to the customer. Each order has a weight, and the total weight of the orders packed in a batch must not exceed the capacity of the delivery batch. Each delivery batch incurs a fixed distribution cost. The problem is to find jointly a schedule for order processing and a way of packing completed orders to form delivery batches such that the total distribution cost (or equivalently, the number of delivery batches) is minimized subject to the constraint that a given customer service level is guaranteed. We consider two customer service constraints—meeting the given deadlines of the orders; or requiring the average delivery lead time of the orders to be within a given threshold. Several problems of the model with each of those constraints are considered. We clarify the complexity of each problem and develop fast heuristics for the NP‐hard problems and analyze their worst‐case performance bounds. Our computational results indicate that all the heuristics are capable of generating near optimal solutions quickly for the respective problems.     

Optimization of loss-balanced multicast in all-optical WDM networks

In wavelength-division multiplexing (WDM) optical networks, multicast is implemented by constructing a light-forest, which is a set of light-trees with each light-tree rooted from the multicast source and terminated at a partition subset of the destination nodes. Multicast routing scenario has considerable impact on the quality of optical signal received at each destination. To guarantee the fairness of signal quality at different destinations in a multicast session, it is desirable to construct a loss-balanced light-forest to deliver the multicast traffic. A loss-balanced light-forest is composed of a set of light-trees bounded in size (number of destinations per multicast tree), in size variation (difference in the number of destinations among different multicast trees), and in dimension (maximum source-to-destination distance on each multicast tree). This paper investigates the multicast routing and wavelength assignment (MC-RWA) problem under the loss-balance constraint. The problem is formulated as an optimization model using integer linear programming (ILP). Numerical solutions to the optimization model can supply useful performance benchmarks for loss-balance-constrained optical multicast in WDM networks. This work was supported by the NSF under Grant OCI-0225642 and by the U.S. DoE under Grant DE-FG02–03ER25566.     

Partial degree bounded edge pacing problem for graphs and $$$$-uniform hypergraphs

Given a graph \(G=(V,E)\) and a non-negative integer \(c_u\) for each \(u\in V\), partial degree bounded edge packing problem is to find a subgraph \(G^{\prime }=(V,E^{\prime })\) with maximum \(|E^{\prime }|\) such that for each edge \((u,v)\in E^{\prime }\), either \(deg_{G^{\prime }}(u)\le c_u\) or \(deg_{G^{\prime }}(v)\le c_v\). The problem has been shown to be NP-hard even for uniform degree constraint (i.e., all \(c_u\) being equal). In this work we study the general degree constraint case (arbitrary degree constraint for each vertex) and present two combinatorial approximation algorithms with approximation factors \(4\) and \(2\). Then we give a \(\log _2 n\) approximation algorithm for edge-weighted version of the problem and an efficient exact algorithm for edge-weighted trees with time complexity \(O(n\log n)\). We also consider a generalization of this problem to \(k\)-uniform hypergraphs and present a constant factor approximation algorithm based on linear programming using Lagrangian relaxation.     

An Approximation Scheme for Bin Packing with Conflicts

In this paper we consider the following bin packing problem with conflicts. Given a set of items V = {1,..., n} with sizes s₁,..., s (0,1) and a conflict graph G = (V, E), we consider the problem to find a packing for the items into bins of size one such that adjacent items (j, j) E are assigned to different bins. The goal is to find an assignment with a minimum number of bins. This problem is a natural generalization of the classical bin packing problem.We propose an asymptotic approximation scheme for the bin packing problem with conflicts restricted to d-inductive graphs with constant d. This graph class contains trees, grid graphs, planar graphs and graphs with constant treewidth. The algorithm finds an assignment for the items such that the generated number of bins is within a factor of (1 + ) of optimal provided that the optimum number is sufficiently large. The running time of the algorithm is polynomial both in n and in .     

基于持续运营机会约束的竞争设施点选址研究——一种有效的实数编码遗传求解算法

竞争设施点选址是空间经济、区域发展、组合优化和系统工程的重要课题之一。本文以市场份额最大化为目标,研究了基于持续运营机会约束的竞争设施点选址问题,并给出了一种有效的实数编码遗传求解算法。在求解模型方面,首先假定运营成本是竞争设施点规模大小的函数,并对设施点持续运营概率进行机会约束,借鉴引力模型建立竞争设施点选址-设计问题的非线性混合整数规划模型。其次,考虑到选址变量和规模变量的数值类型,以及编码变换问题,设计了一种实数编码遗传求解算法。通过数值实验表明,对不同规模问题的实际计算结果,该算法可以在较短时间内获得最优解,可行解和精确解之间误差小于0.5%,相关比较分析也讨论了该算法的优越性和实用性,为竞争设施点选址问题的研究提供了不同的视角和实用求解算法。     

Distribution Planning to Optimize Profits in the Motion Picture Industry

We consider the distribution planning problem in the motion picture industry. This problem involves forecasting theater‐level box office revenues for a given movie and using these forecasts to choose the best locations to screen a movie. We first develop a method that predicts theater‐level box office revenues over time for a given movie as a function of movie attributes and theater characteristics. These estimates are then used by the distributor to choose where to screen the movie. The distributor's location selection problem is modeled as an integer programming‐based optimization model that chooses the location of theaters in order to optimize profits. We tested our methods on realistic box office data and show that it has the potential to significantly improve the distributor's profits. We also develop some insights into why our methods outperform existing practice, which are crucial to their successful practical implementation.     

A multistage approach for production and workforce planning in long-cycle product environments

Aggregate production planning (APP) has been studied extensively for the past two decades. The APP problem, also called production and workforce scheduling, is to determine the optimal workforce and production level in each period of the planning horizon in order to satisfy demand forecasts for these periods. The advantages of the APP are low cost of data collection and computational cost of the running model; the accuracy of data; and, effective managerial understanding of the results. If the product of concern takes longer than one period, it is called a long-cycle product. Examples of long-cycle products are aircraft, ships, buildings and special machines. A detailed model incorporating dynamic productivity and long-cycle products considerations is presented to solve the problem of production and workforce planning. Using a multistage production system approach, a search technique is developed to solve this class of problems where the objective function is linear and some of the constraint coefficients are dynamically nonlinear. The model provides a better solution than an aggregate production planning model, often used to solve these problems.     

基于双层规划的反恐应急设施选址模型及算法

恐怖袭击常以人流密集地区的平民作为袭击目标，并存在突发性和随机性等特点，极易造成严重的袭击后果。通过反恐应急设施的合理布局可以缩短救援人员和物资的到达时间，从而减轻袭击后果。首先，对反恐应急设施选址问题进行描述，并将其构造为一类离散双层规划模型。其中，上层规划是关于政府选址的0-1规划问题，下层规划则是关于恐怖分子袭击目标选择的0-1规划问题。其次，结合模型和问题的特征设计算法，利用分支定界算法实现上层选址变量的隐枚举，同时通过下层问题的求解来确定上下界并判断是否满足分枝或剪枝的条件。最后，结合南疆地区的交通拓扑网络进行算例分析，结果证明有效的选址方案可以大大降低袭击损失。     

考虑路径可行性与仓储集货模式下的回收车辆路径问题研究

逆向物流回收车辆调度过程中,往往出现由于需求节点位置及需求量信息的不确定性导致难以合理决策完成回收任务所需派出回收车辆的数目,此时,第三方物流逐渐被应用于回收产品的运输服务中。然而在实际的回收过程中,通常各物流需求节点的需求量较小,需要对多个物流节点的产品集中后统一进行处理;同时由于外界因素的限制,不能保证任意两个节点间均存在可行路径,需要通过中转运输的方式寻找替代路线。针对以上问题,本文提出一种基于路径可行性与仓储集货运输模式的回收车辆路径设计方案,并根据问题的特点对传统蚁群算法（ACO）中编码方式以及概率选择操作方式进行改进,提出一种逆选择操作蚁群算法（ACO-nso）。最后通过算例证明提出模型与算法的有效性。