Power efficient uplink scheduling in SC-FDMA: benchmarking by column generation

We study resource allocation in cellular systems and consider the problem of finding a power efficient scheduling in an uplink single carrier frequency division multiple access system. Due to the discrete nature of this problem and its computational difficulty, particularly in a real-time setting, the use of suboptimal algorithms is common practice. We aim at an effective way of gauging the performance of suboptimal algorithms by finding tight bounds on the global optimum. Toward this end, we first provide a basic integer linear programming formulation. Then we propose a significantly stronger column-oriented formulation and a corresponding column generation method, as well as an enhanced column generation scheme. The latter extends the first scheme through the inclusion of a stabilization technique, an approximate column generation principle, and a tailored heuristic that is embedded in the column generation scheme to find high-quality though not necessarily global optimal solutions. The computational evaluation demonstrates that compared with a poor performance by the integer linear programming formulation, the column generation method can produce near-optimal schedules that enable a sharp bounding interval. The enhanced column generation method significantly sharpens the bounding interval. Hence the column generation approach serves well for the purpose of benchmarking results for large-scale instances.     

Models and algorithms for the heterogeneous dial-a-ride problem with driver-related constraints

This paper introduces models and algorithms for a static dial-a-ride problem arising in the transportation of patients by non-profit organizations such as the Austrian Red Cross. This problem is characterized by the presence of heterogeneous vehicles and patients. In our problem, two types of vehicles are used, each providing a different capacity for four different modes of transportation. Patients may request to be transported either seated, on a stretcher or in a wheelchair. In addition, some may require accompanying persons. The problem is to construct a minimum-cost routing plan satisfying service-related criteria, expressed in terms of time windows, as well as driver-related constraints expressed in terms of maximum route duration limits and mandatory lunch breaks. We introduce both a three-index and a set-partitioning formulation of the problem. The linear programming relaxation of the latter is solved by a column generation algorithm. We also propose a variable neighborhood search heuristic. Finally, we integrate the heuristic and the column generation approach into a collaborative framework. The column generation algorithm and the collaborative framework provide tight lower bounds on the optimal solution values for small-to-medium-sized instances. The variable neighborhood search algorithm yields high-quality solutions for realistic test instances.     

质量体积双约束下车辆装载与配送路径联合优化研究

目的 针对质量与体积共同限制的配送路径问题,综合考虑订单不可拆分、货物的体积等约束,构建包含路径最短和装载率最高双目标的车辆装载与配送路径联合优化模型。方法 在车辆路径优化模型的求解方面,首先利用聚类算法对配送区域进行划分,然后通过车辆的载质量判断是否能进行站点货物的配送,最后利用遗传算法求得最优路径。在三维装载模型的求解上使用贪心算法和基于块的启发式算法,解决了货物的装箱问题。结果 基于某公司具体实例对模型与算法的可行性进行了验证,优化后配送的车辆减少了1辆,配送距离减少了154.247km,平均装载率达到了93.89%,节省了企业的配送成本。结论 所构建的模型以及求解的算法可以提高装载率和配送效率,为解决车辆装载与配送路径联合优化问题提供理论依据。     

Column Generation Based Heuristic Algorithm for Multi-Item Scheduling

The column generation algorithm for the multi-item lot-size scheduling problem under resource constraints is examined and improved upon by augmenting simpler heuristic routines in place of the time-consuming Wagner-Whitin dynamic programming routine. The heuristic algorithms thus developed are tested by controlling problem size, setup time, demand variability, and capacity change costs in test problems. The empirical results indicate that the proposed heuristic algorithms reduce CPU time as well as the number of iterations with only a slight loss in optimality.     

Optimal Operation of Integrated Heat and Electricity Systems: A Tightening McCormick Approach

Combined heat and electricity operation with variable mass flow rates promotes flexibility, economy, and sustainability through synergies between electric power systems (EPSs) and district heating systems (DHSs). Such combined operation presents a highly nonlinear and nonconvex optimization problem, mainly due to the bilinear terms in the heat flow model—that is, the product of the mass flow rate and the nodal temperature. Existing methods, such as nonlinear optimization, generalized Benders decomposition, and convex relaxation, still present challenges in achieving a satisfactory performance in terms of solution quality and computational efficiency. To resolve this problem, we herein first reformulate the district heating network model through an equivalent transformation and variable substitution. The reformulated model has only one set of nonconvex constraints with reduced bilinear terms, and the remaining constraints are linear. Such a reformulation not only ensures optimality, but also accelerates the solving process. To relax the remaining bilinear constraints, we then apply McCormick envelopes and obtain an objective lower bound of the reformulated model. To improve the quality of the McCormick relaxation, we employ a piecewise McCormick technique that partitions the domain of one of the variables of the bilinear terms into several disjoint regions in order to derive strengthened lower and upper bounds of the partitioned variables. We propose a heuristic tightening method to further constrict the strengthened bounds derived from the piecewise McCormick technique and recover a nearby feasible solution. Case studies show that, compared with the interior point method and the method implemented in a global bilinear solver, the proposed tightening McCormick method quickly solves the heat–electricity operation problem with an acceptable feasibility check and optimality.     

A limited-memory, quasi-Newton preconditioner for nonnegatively constrained image reconstruction

Image reconstruction gives rise to some challenging large-scale constrained optimization problems. We consider a convex minimization problem with nonnegativity constraints that arises in astronomical imaging. To solve this problem, we use an efficient hybrid gradient projection-reduced Newton (active-set) method. By "reduced Newton," we mean that we take Newton steps only in the inactive variables. Owing to the large size of our problem, we compute approximate reduced Newton steps by using the conjugate gradient (CG) iteration. We introduce a limited-memory, quasi-Newton preconditioner that speeds up CG convergence. A numerical comparison is presented that demonstrates the effectiveness of this preconditioner.     

车辆战术储备器材包装单元装载优化研究

目的通过对车辆战术储备器材包装单元化装载问题展开研究,为提高部队车辆战术储备器材包装单元装载能力提供技术与方法依据。方法分析装载优化模型的空间、质量、装载平衡和摆放稳定性等主要约束以及约束的处理方法,运用启发式算法对模型求解流程进行合理设计,并提出启发式算法和遗传算法相结合的混合遗传算法,以托盘装载为例说明具体装载过程。结果算例结果表明,托盘空间利用率达到了98.3%以上,装载单元集装稳定性高。结论该算法可减少装载容器数量,提升容器装载能力,优化器材包装单元装载,对提高车辆战术储备器材快速保障能力具有重要意义。     

Integration of vendor selection into production and remanufacturing planning subject to emission constraints

This paper presents a new model formulation that incorporates vendor selection into production and remanufacturing planning subject to emission constraints. The objective is to determine a feasible production and remanufacturing plan at minimal cost. In each period, the given external demand must be satisfied for both new and remanufactured products. Remanufactured products can be substituted by new products, but not vice versa. When a product is (re)manufactured, the appropriate machine must be set up, which entails set-up costs and/or set-up time. The procurement of raw material that is offered by several vendors at different prices is integrated into this planning problem. To solve this integrated production and remanufacturing planning problem, we apply two solution approaches based on mathematical programming: first, a combination of column generation and a period-oriented fix-and-relax heuristic and second, an adapted fix-and-optimise heuristic. The results of our numerical investigation demonstrate the high solution quality of both solution approaches.     

Constraint isomorphism and the generation of stochastic data

We consider the problem of generating random data under constraints that are expressed in terms of different parameter sets. These constraints must be consistent between the parameter sets. However, this requirement of constraint consistency has to date not received much attention in the literature. The major objective of this article is to propose a formal concept called constraint isomorphism to detect and help avoid inconsistencies between the constraints. The method presented here can be used as a verification technique for random-data generation. As a case study, we illustrate our methodology on the total-tardiness problem: a NP-hard job scheduling problem. Since generating random data under constraints is an extremely common problem, especially in the simulation arena, the technique has a wide spectrum of potential applications.     

POST-BUCKLING ANALYSIS WITH FRICTIONAL CONTACTS COMBINING COMPLEMENTARITY RELATIONS AND AN ARC-LENGTH METHOD

A linear complementarity problem formulation combined with an arc-length method is presented for post-buckling analysis of geometrically non-linear structures with frictional contact constraints. The arc-length method with updated normal plane constraint is used to trace the equilibrium paths of the structures after limit points. Under the proportional loading assumption, the unknown load scale parameter used in the arc-length method is expressed in terms of contact forces, and eliminated to formulate as a linear complementarity problem. The unknown contact variables such as contact status and contact forces can be directly solved in this formulation without any ad hoc technique. Complicated non-linear buckling behaviours, such as snap-buckling, can be efficiently solved by the developed method, as shown by several buckling and post-buckling problems with frictional contact constraints.     

A Framework For Probabilistic Vehicle Routing

The stochastic vehicle routing problem is a problem of considerable current importance in operations research and industrial engineering. The basic problem is to determine a fixed set of vehicle routes of minimal expected total distance. All vehicles must leave from and eventually return to a central depot, and capacity constraints and probabilistic customer demands must be satisfied. In previous work, we assumed that the demand at each node i could be modeled by a Poisson distribution with mean Λi and that demands at nodes are mutually independent. We then developed an efficient heuristic solution procedure which was quite effective in generating an excellent set of fixed vehicle routes, as evidenced by extensive computational results. With this previous work as a starting point, in this paper we investigate solution procedures for the case where other appropriate probability distributions are assumed. In addition, we present analytical results describing the various relationships between design parameters and provide a framework for performing perturbation analysis. Finally, we focus on a more flexible model in which demands are correlated.     

基于组合的三维集装箱装入启发式算法的研究

集装箱装入属于有多种约束的空间资源优化问题。其求解思路可以推广到飞机、轮船的货舱装载,乃至计算机的内存分配等多种应用领域。笔者提出了通过回溯过程实现的组合装入的启发式算法,设计了有效的装入策略,定义了用于装入过程状态描述的剩余空间表示和小剩余空间的结合原则。通过实例验证,能有效提高集装箱空间的利用率。与现有算法比较,具有适合装入物体种类多,尺寸差别大的情况。     

Optimum design of laminated fibre composite plates

A method is presented for the minimum weight optimum design of laminated fibre composite plates, subject to multiple inplane loading conditions, which includes stiffness, strength and elastic stability constraints. The buckling analysis is based on an equivalent orthotropic plate approach leading to two uncoupled eigenproblems per load condition. Overall computational efficiency is achieved by using constraint deletion techniques in conjunction with Taylor series approximations for the constraints retained. The optimization algorithm used, namely the method of inscribed hyperspheres, is a sequence of linear programs technique which exhibits rapid convergence in this application. Several example problems are given to demonstrate that the method presented offers an efficient and practical optimum design procedure for the fundamental and recurring problem treated.     

汽车维修服务站瓶颈工序的实时调度

在结合优化调度理论和约束理论的基础上,从最小化目标、机器环境、加工特征和约束几方面分析了汽车维修服务站瓶颈工序的实时调度问题的特征,建立了对应的数学模型。根据问题特性,设计了包含复合动态分派规则的启发式调度算法。以实例分析验证了算法的可行性,仿真结果展示了所用算法在优化目标函数值上的优越性和计算时间的可行性。     

Multiple-choice knapsack-based heuristic algorithm for the two-stage two-dimensional cutting stock problem in the paper industry

This study examines a two-stage two-dimensional cutting stock problem encountered by a paper mill company. The problem includes various machine-related and operational constraints based on real-world situations. Paper products are manufactured using two major cutting processes. Each cutting machine has a specific minimum and maximum width for input and output rolls and is limited by the maximum number of rolls it can cut at the same time. A mathematical model is presented to formally address the problem and an efficient multiple-choice knapsack-based heuristic algorithm is proposed to solve the problem. To demonstrate the efficiency of the proposed heuristic algorithm, computational experiments are conducted on test data-set generated from real-world data provided by a large paper mill company in the Republic of Korea.     

A static empty equipment allocation model for long-haul networks with constrained crew routes

A realistic and efficient tactical model is developed that is able to optimize equipment and crew movements in long-haul trucking networks so that drivers are able to return home within a reasonable amount of time. A unique feature of the model is that driver, tractor, and trailer routes are simultaneously optimized. An underlying assumption is that routes remain in place for extended periods; though the trailers, tractors, and drivers may flow across these routes at variable rates. We formulate a static linear programming model for this tactical problem, and propose a column generation algorithm. The algorithm is tested with real data from a less-than-truckload carrier and randomly generated test data. Networks with up to 40 nodes (including the 30-node real-life example) are successfully optimized. For our sample problems, we found that static routes produced solutions within an average 0.22% of the optimum under dynamic conditions, provided that variable flows are permitted across the static routes.     

求解集装箱装载问题的混合蚁群模拟退火算法

目的 针对物流行业中存在的大规模、复杂、多规格货物的集装箱装载问题,提出一种基于塔装载启发式算法、二维装载点启发式算法、蚁群模拟退火算法的混合算法。方法 首先,采用塔装载启发式算法将三维待装箱装载成塔集,即将三维装箱问题降为二维装箱问题,有效降低集装箱的装载规模;其次,蚁群算法通过融入信息素选择更新策略,并利用自适应信息素挥发系数来提升算法整体的收敛速度,同时结合模拟退火算法对每代优秀路径集进行局部搜索,避免算法因收敛过快而陷入局部最优;最后,将蚁群模拟退火算法与二维装载点启发式算法相结合,优化每座塔的装载顺序和放置姿态,寻找最优的装载方案。结果 实验证明,在250组算例中,采用混合算法后,集装箱的平均空间利用率为90.92%,优于其他3种对比算法。结论 设计的混合蚁群模拟退火算法适用于解决大规模集装箱装载问题。     

Machine-component group formation: an heuristic method for flexible production cells and flexible manufacturing systems

This paper provides an heuristic for the planning and study of machine-component groups in flexible production cells and flexible manufacturing systems. The problem of group formation defined on master-component process routes is undertaken in terms of minimum differences between masters and maximum combinations of masters. Group formation is a ‘hard’ combinatorial problem subject to exponential growth of complexity as the number of decision-making variables increases. The heuristic is designed to search the solution space of the problem in monotone-increasing order of solution costs so as to avoid the enumeration of solutions for cost minimization.     

Tabu search for the redundancy allocation problem of homogenous series–parallel multi-state systems

This paper develops an efficient tabu search (TS) heuristic to solve the redundancy allocation problem for multi-state series–parallel systems. The system has a range of performance levels from perfect functioning to complete failure. Identical redundant elements are included in order to achieve a desirable level of availability. The elements of the system are characterized by their cost, performance and availability. These elements are chosen from a list of products available in the market. System availability is defined as the ability to satisfy consumer demand, which is represented as a piecewise cumulative load curve. A universal generating function technique is applied to evaluate system availability. The proposed TS heuristic determines the minimal cost system configuration under availability constraints. An originality of our approach is that it proceeds by dividing the search space into a set of disjoint subsets, and then by applying TS to each subset. The design problem, solved in this study, has been previously analyzed using genetic algorithms (GAs). Numerical results for the test problems from previous research are reported, and larger test problems are randomly generated. Comparisons show that the proposed TS out-performs GA solutions, in terms of both the solution quality and the execution time.