Master problem approximations in Dantzig–Wolfe decomposition of variational inequality problems with applications to two energy market models

In this paper, a modification to Dantzig–Wolfe (DW) decomposition algorithm for variational inequality (VI) problems is considered to alleviate the computational burden and to facilitate model management and maintenance. As proposals from DW subproblems are accumulated in the DW master problem, the solution time and memory requirements are increasing for the master problem. Approximation of the DW master problem solution significantly reduces the computational effort required to find the equilibrium. The approximate DW algorithm is applied to a time of use pricing model with realistic network constraints for the Ontario electricity market and to a two-region energy model for Canada. In addition to empirical analysis, theoretical results for the convergence of the approximate DW algorithm are presented.     

Dantzig–Wolfe and block coordinate-descent decomposition in large-scale integrated refinery-planning

The integrated refinery-planning (IRP), an instrumental problem in the petroleum industry, is made of several subsystems, each of them involving a large number of decisions. Despite the complexity of the overall planning problem, this work presents a mathematical model of the refinery operations characterized by complete horizontal integration of subsystems from crude oil purchase through to product distribution. This is the main contribution from a modelling point of view. The IRP, with a planning horizon ranging from 2 to 300 days, results in a large-scale linear programming (LP) problem of up to one million constraints, 2.5 million variables and 59 millions of nonzeroes in the constraint matrix. Large instances become computationally challenging for generic state-of-the-art LP solvers, such as CPLEX. To avoid this drawback, after the identification of the nonzero structure of the constraints matrix, structure-exploiting techniques such as Dantzig–Wolfe and block coordinate-descent decomposition were applied to IRP. It was also observed that interior-point methods are far more efficient than simplex ones in large IRP instances. These were the main contributions from the optimization viewpoint. A set of realistic instances were dealt with generic algorithms and these two decomposition methods. In particular the block coordinate-descent heuristic, with a reverse order of the subsystems, appeared as a promising approach for very large integrated refinery problems, obtaining either the optimal or an approximate feasible solution in all the instances tested.     

Bus and Buffer Usage in In-Home Digital Networks: Applying the Dantzig–Wolfe Decomposition

In an in-home digital network several data streams (audio, video) may run simultaneously over a shared communication device, e.g. a bus. The burstiness of a data stream can be reduced by buffering data at the sending and receiving side, thereby allowing a lower bus share allocation for the stream. In this paper we present an algorithm that determines how much of the bus capacity and buffer space should be allocated to each stream, in order to have a feasible transmission schedule for each stream. Furthermore, the algorithm determines a transmission schedule for each stream, indicating how much data is transmitted over time. We model the problem as a linear program and apply a Dantzig–Wolfe decomposition such that the multiple-stream problem can be solved by repeatedly solving single-stream problems. For these single-stream problems we briefly describe efficient algorithms to solve them.     

Dantzig—Wolfe Decomposition of Variational Inequalities

The creation and ongoing management of a large economic model can be greatly simplified if the model is managed in separate smaller pieces defined, e.g. by region or commodity. For this purpose, we define an extension of Dantzig–Wolfe decomposition for the variational inequality (VI) problem, a modeling framework that is widely used for models of competitive or oligopolistic markets. The subproblem, a collection of independent smaller models, is a relaxed VI missing some “difficult” constraints. The subproblem is modified at each iteration by information passed from the last solution of the master problem in a manner analogous to Dantzig–Wolfe decomposition for optimization models. The master problem is a VI which forms convex combinations of proposals from the subproblem, and enforces the difficult constraints. A valid stopping condition is derived in which a scalar quantity, called the “convergence gap,” is monitored. The convergence gap is a generalization of the primal-dual gap that is commonly monitored in implementations of Dantzig–Wolfe decomposition for optimization models. Convergence is proved under conditions general enough to be applicable to many models. An illustration is provided for a two-region competitive model of Canadian energy markets.     

The manpower allocation problem with time windows and job-teaming constraints: A branch-and-price approach

In this paper, we consider the manpower allocation problem with time windows, job-teaming constraints and a limited number of teams (m-MAPTWTC). Given a set of teams and a set of tasks, the problem is to assign to each team a sequential order of tasks to maximize the total number of assigned tasks. Both teams and tasks may be restricted by time windows outside which operation is not possible. Some tasks require cooperation between teams, and all teams cooperating must initiate execution simultaneously. We present an integer programming model for the problem, which is decomposed using Dantzig–Wolfe decomposition. The problem is solved by column generation in a branch-and-price framework. Simultaneous execution of tasks is enforced by the branching scheme. To test the efficiency of the proposed algorithm, 12 realistic test instances are introduced. The algorithm is able to find the optimal solution in 11 of the test instances. The main contribution of this article is the addition of synchronization between teams in an exact optimization context.     

Minimizing makespan in a two-stage system with flowshop and open shop

This paper studies two models of two-stage processing with flowshop at the first stage followed by open shop at the second stage. The first model involves multiple machines at the first stage and two machines at the second stage, and the other involves multiple machines at both stages. In both models, the objective is to minimize the makespan. This problem is NP-complete, for which an efficient heuristic solution algorithm is constructed and its worst-case performance guarantee is analyzed for both models. An integer programming model and a branch and bound algorithm are proposed for model 1 and a lower bound is developed for model 2 as benchmarks for the heuristic algorithms. Computational experiences show that the heuristic algorithms consistently generate good schedule and the branch and bound algorithm is much efficient than the integer-programming model.     

Branch-and-Bound-Based Local Search Heuristics for Train Timetabling on Single-Track Railway Network

The modified formulation and two branch-and-bound-based local search heuristic algorithms for train timetabling in single-track railway network in the planning application are proposed. The original local search heuristic is modified such that when a neighbor of a currently tested resolved conflict for improvement is evaluated, the depth-first search branch-and-bound algorithm is employed with two branching rules: least-lower-bound and least-delay-time. The detailed implementation of the proposed heuristic algorithms are described, including the neighborhood definitions of overtaking and crossing conflicts, the procedure to detect overtaking and crossing conflicts, and a recursive procedure for the depth-first search branch-and-bound algorithm. The proposed heuristic algorithms, the original heuristic, the equivalent manual solution method and the exact solution method are compared using a toy problem and four problems (26-train, 50-train, 76-train and 108-train) in the Thailand Southern line railway network, which consisted of 266 single-track segments, 15 double-track segments, 282 stations/sidings, and total distance of 1577 km. The proposed heuristic algorithm with the least-lower-bound branching rule outperforms the other heuristics in terms of the solution quality with up to 2.827 % improvement over the equivalent manual solution method and less than 8 % optimality gap. The proposed heuristic algorithms require longer time to terminate than the original heuristic. The proposed heuristic algorithm with the least-lower-bound branching rule converges faster than that with the least-delay-time branching rule in all test problems. Based on the empirical results, the proposed heuristic algorithms are solvable in polynomial time. Furthermore, the proposed heuristic algorithm with the least-lower-bound branching rule is enhanced by embedding a uniform sampling strategy, and it is found that the total CPU time can be saved by about 50 % with marginally worse solution quality.     

移动边缘计算中的端到端任务分配算法

为了提高移动应用程序的运行效率,移动边缘计算将部分任务从终端设备迁移到边缘云中计算来缩减应用程序的运行时间和终端设备的能耗。针对应用程序所需的总代价即能耗和时间两个目标进行了研究,提出一个移动边缘计算模型和基于贪心策略的快速算法（HGA）;构造了一个结合贪心策略的粒子群（HPSO）算法,进一步优化HGA的解。实验结果表明,与传统所有任务只在一个设备上执行和尽可能上传云端执行两种策略相比,提出的HGA总代价分别优化28.5%和9.1%;与HGA相比,HPSO算法总代价减少12.3%;即所提算法能有效减少系统的总代价,更加满足用户需求。     

A branch-and-price algorithm to solve the molten iron allocation problem in iron and steel industry

The molten iron allocation problem (MIAP) is to allocate molten iron from blast furnaces to steel-making furnaces. The allocation needs to observe the release times of the molten iron defined by the draining plan of the blast furnaces and the transport time between the iron-making and steel-making stages. Time window constraints for processing the molten iron must be satisfied to avoid freezing. The objective is to find a schedule with minimum total weighted completion time. This objective reflects the practical consideration of improving steel-making efficiency and reducing operation cost caused by the need for reheating. Such a problem can be viewed as a parallel machine scheduling problem with time windows which is known to be NP-hard. In this paper, we first formulate the molten iron allocation problem as an integer programming model and then reformulate it as a set partitioning model by applying the Dantzig–Wolfe decomposition. We solve the problem using a column generation-based branch-and-price algorithm. Since the subproblem of column generation is still NP-hard, we propose a state-space relaxation-based dynamic programming algorithm for the subproblem. Computational experiments demonstrate that the proposed algorithm is capable of solving problems with up to 100 jobs to optimality within a reasonable computation time.     

Decomposition's Dantzig–Wolfe applied to fuzzy multicommodity flow problems

We present, in this paper, a method for solving linear programming problems with fuzzy costs based on the classical method of decomposition's Dantzig–Wolfe. Methods using decomposition techniques address problems that have a special structure in the set of constraints. An example of such a problem that has this structure is the fuzzy multicommodity flow problem. This problem can be modeled by a graph whose nodes represent points of supply, demand and passage of commodities, which travel on the arcs of the network. The objective is to determine the flow of each commodity on the arcs, in order to meet demand at minimal cost while respecting the capacity constraints of the arcs and the flow conservation constraints of the nodes. Using the theory of fuzzy sets, the proposed method aims to find the optimal solution, working with the problem in the fuzzy form during the resolution procedure.     

基于遗传算法的可扩展应用层组播树构建

在应用层组播中,为降低节点的路径延时,通常采用遗传算法和启发式算法来减小组播树直径的方法,但在组播树具有大规模节点数时,遗传算法收敛时间长,而采用启发式算法难以在有约束条件下达到全局最优.本文在具有超节点的双层应用层组播模型基础上,提出了利用遗传算法构建出度受限最小带权路径延时生成树（MWPL-DC-ST）的生成算法GA-MWPL-DC-ST,利用该算法可在超节点上对双层组播树进行分布式构建,从而将求最优解问题的巨大计算量分担到多个超节点上.算法中的初始化、杂交和变异阶段采用启发式算法,对变异参数进行适应性调整,加快了算法的收敛速度.仿真试验表明,本文提出的双层应用层组播模型和GA-MWPL-DC-ST算法能得到比启发式算法更优的解,与采用单层模型的遗传算法相比较,显著降低了算法收敛时间,解决了遗传算法构建有大规模节点数的应用层组播树的可扩展性问题.     

An unequal packet loss resilience scheme for video over the Internet

We present an unequal packet loss resilience scheme for robust transmission of video over the Internet. By jointly exploiting the unequal importance existing in different levels of syntax hierarchy in video coding schemes, GOP-level and Resynchronization-packet-level Integrated Protection (GRIP) is designed for joint unequal loss protection (ULP) in these two levels using forward error correction (FEC) across packets. Two algorithms are developed to achieve efficient FEC assignment for the proposed GRIP framework: a model-based FEC assignment algorithm and a heuristic FEC assignment algorithm. The model-based FEC assignment algorithm is to achieve optimal allocation of FEC codes based on a simple but effective performance metric, namely distortion-weighted expected length of error propagation, which is adopted to quantify the temporal propagation effect of packet loss on video quality degradation. The heuristic FEC assignment algorithm aims at providing a much simpler yet effective FEC assignment with little computational complexity. The proposed GRIP together with any of the two developed FEC assignment algorithms demonstrates strong robustness against burst packet losses with adaptation to different channel status.     

A constraint propagation heuristic for the single-hoist,multiple-products scheduling problem

A heuristic algorithm for solving the single-hoist, multiple-product scheduling problem is presented. The algorithm uses a non-standard Constraint Satisfaction Problem model and employs variable ordering, forward checking and backtracking. Computational results, including comparison with existing algorithms in terms of solution quality and speed, are presented.     

求解二维装箱问题的强化学习启发式算法

二维带形装箱问题是一个经典的NP-hard的组合优化问题,该问题在实际的生活和工业生产中有着广泛的应用.研究该问题,对企业节约成本、节约资源以及提高生产效率有着重要的意义.提出了一个强化学习求解算法.新颖地使用强化学习为启发式算法提供一个初始的装箱序列,有效地改善启发式冷启动的问题.该强化学习模型能进行自我驱动学习,仅使用启发式计算的解决方案的目标值作为奖励信号来优化网络,使网络能学习到更好的装箱序列.使用简化版的指针网络来解码输出装箱序列,该模型由嵌入层、解码器和注意力机制组成.使用Actor-Critic算法对模型进行训练,提高了模型的效率.在714个标准问题实例和随机生成的400个问题实例上测试提出的算法,实验结果显示：提出的算法能有效地改善启发式冷启动的问题,性能超过当前最优秀的启发式求解算法.     

Two-machine flowshop scheduling with bicriteria problem

This paper attempts to solve a two-machine flowshop bicriteria scheduling problem with release dates for the jobs, in which the objective function is to minimize a weighed sum of total flow time and makespan. To tackle this scheduling problem, an integer programming model with N²+3N variables and 5N constraints where N is the number of jobs, is formulated. Because of the lengthy computing time and high computing complexity of the integer programming model, a heuristic scheduling algorithm is presented. Experimental results show that the proposed heuristic algorithm can solve this problem rapidly and accurately. The average solution quality of the heuristic algorithm is above 99% and is much better than that of the SPT rule as a benchmark. A 15-job case requires only 0.018 s, on average, to obtain an ultimate or even optimal solution. The heuristic scheduling algorithm is a more practical approach to real world applications than the integer programming model.     

Solving very large instances of the scheduling of independent tasks problem on the GPU

In this paper, we present two new parallel algorithms to solve large instances of the scheduling of independent tasks problem. First, we describe a parallel version of the Min–min heuristic. Second, we present GraphCell, an advanced parallel cellular genetic algorithm (CGA) for the GPU. Two new generic recombination operators that take advantage of the massive parallelism of the GPU are proposed for GraphCell. A speedup study shows the high performance of the parallel Min–min algorithm in the GPU versus several CPU versions of the algorithm (both sequential and parallel using multiple threads). GraphCell improves state-of-the-art solutions, especially for larger problems, and it provides an alternative to our GPU Min–min heuristic when more accurate solutions are needed, at the expense of an increased runtime.     

An Electromagnetism-like algorithm for cell formation and layout problem

Implementation of cellular manufacturing systems (CMS) is thriving among manufacturing companies due to many advantages that are attained by applying this system. In this study CMS formation and layout problems are considered. An Electromagnetism like (EM-like) algorithm is developed to solve the mentioned problems. In addition the required modifications to make EM-like algorithm applicable in these problems are mentioned. A heuristic approach is developed as a local search method to improve the quality of solution of EM-like. Beside in order to examine its performance, it is compared with two other methods. The performance of EM-like algorithm with proposed heuristic and GA are compared and it is demonstrated that implementing EM-like algorithm in this problem can improve the results significantly in comparison with GA. In addition some statistical tests are conducted to find the best performance of EM-like algorithm and GA due to their parameters. The convergence diagrams are plotted for two problems to compare the convergence process of the algorithms. For small size problems the performances of the algorithms are compared with an exact algorithm (Branch & Bound).     

A Heuristic Algorithm for Reliability Modeling and Analysis of Grid Systems

Grid computing focuses on large-scale resource sharing. Using a general reliability model for grid computing to relax some impractical assumptions, a heuristic algorithm is presented to evaluate grid program/service reliability. The heuristic algorithm is based on two heuristic criteria that determine the significance of an entity and prune those insignificant ones. Through algorithm analysis, the heuristic algorithm is shown to have a linear complexity. This is much better than the previous algorithms, which are of exponential complexity. Another advantage of the heuristic algorithm is that the running time is controllable by adjusting the parameter of significant level (SL) and significant rate. A regression method is proposed to adjust the SL and predict the running time. Two examples are given     

Bacterial Foraging Optimization Approach to Portfolio Optimization

In this paper we propose a heuristic approach based on bacterial foraging optimization (BFO) in order to find the efficient frontier associated with the portfolio optimization (PO) problem. The PO model with cardinality and bounding constraints is a mixed quadratic and integer programming problem for which no exact algorithms can solve in an efficient way. Consequently, various heuristic algorithms, such as genetic algorithms and particle swarm optimization, have been proposed in the past. This paper aims to examine the potential of a BFO algorithm in solving the PO problem. BFO is a new swarm intelligence technique that has been successfully applied to several real world problems. Through three operations, chemotaxis, reproduction, and elimination-dispersal, the proposed BFO algorithm can effectively solve a PO problem. The performance of the proposed approach was evaluated in computational tests on five benchmark data sets, and the results were compared to those obtained from existing heuristic algorithms. The proposed BFO algorithm is found to be superior to previous heuristic algorithms in terms of solution quality and time.     

Depth-first iterative-deepening: An optimal admissible tree search

The complexities of various search algorithms are considered in terms of time, space, and cost of solution path. It is known that breadth-first search requires too much space and depth-first search can use too much time and doesn't always find a cheapest path. A depth-first iterative-deepening algorithm is shown to be asymptotically optimal along all three dimensions for exponential tree searches. The algorithm has been used successfully in chess programs, has been effectively combined with bi-directional search, and has been applied to best-first heuristic search as well. This heuristic depth-first iterative-deepening algorithm is the only known algorithm that is capable of finding optimal solutions to randomly generated instances of the Fifteen Puzzle within practical resource limits.