Mixed coordination method for long-horizon optimal control problems

We present a new approach to solving long-horizon, discrete-time optimal control problems using the mixed coordination method. The idea is to decompose a long-horizon problem into subproblems along the time axis. The requirement that the initial state of a subproblem equal the terminal state of the preceding subproblem is relaxed by using Lagrange multipliers. The Lagrange multipliers and initial state of each subproblem are then selected as high-level variables. The equivalence of the two-level formulation and the original problem is proved for both convex and non-convex cases. The low-level subproblems are solved in parallel using extended differential dynamic programming (DDP). An efficient way to find the gradient and hessian of a low-level objective function with respect to high-level variables is developed. The high-level problem is solved using the modified Newton method. An effective procedure is developed to select initial values of multipliers based on the initial trajectory. The method can convexify the high-level problem while maintaining the separability of an originally non-convex problem. The method performs better and faster than one-level DDP for both convex and non-convex test problems.     

启发式列生成算法求解带恶化效应的同构并行机调度问题

针对实际生产中广泛存在的一类带恶化效应的同构并行机调度问题,以最小化最大完工时间为优化目标,构建该问题的整数规划模型,并提出一种启发式列生成算法(HCGA)进行求解.在HCGA中,首先,利用Dantzig-Wolfe分解方法,将原问题分解为一个主问题(MP)和多个子问题;然后,设计启发式算法获得初始列,其中每列为一台机器上的一个调度方案,基于初始列构建限制主问题(RMP)模型;接着,设计快速有效的动态规划算法求解子问题,以得到需添加至RMP的列集,同时,考虑传统列生成算法收敛速度较慢,设计一系列方法来加速列生成过程;最后,基于所获取的MP线性松弛解,设计深潜启发式算法确定原问题的整数解.HCGA与商用求解器GUROBI的对比实验结果表明,HCGA可在较短时间内获得更优的解.     

An augmented Lagrangian decomposition method for quasi-separable problems in MDO

Several decomposition methods have been proposed for the distributed optimal design of quasi-separable problems encountered in Multidisciplinary Design Optimization (MDO). Some of these methods are known to have numerical convergence difficulties that can be explained theoretically. We propose a new decomposition algorithm for quasi-separable MDO problems. In particular, we propose a decomposed problem formulation based on the augmented Lagrangian penalty function and the block coordinate descent algorithm. The proposed solution algorithm consists of inner and outer loops. In the outer loop, the augmented Lagrangian penalty parameters are updated. In the inner loop, our method alternates between solving an optimization master problem and solving disciplinary optimization subproblems. The coordinating master problem can be solved analytically; the disciplinary subproblems can be solved using commonly available gradient-based optimization algorithms. The augmented Lagrangian decomposition method is derived such that existing proofs can be used to show convergence of the decomposition algorithm to Karush–Kuhn–Tucker points of the original problem under mild assumptions. We investigate the numerical performance of the proposed method on two example problems.     

Group-scheduling problems in electronics manufacturing

This paper addresses the flowshop group-scheduling problems typically encountered in the assembly of printed circuit boards in electronics manufacturing. A mathematical programming model is formulated to capture the characteristics inherent to group-scheduling problems experienced in electronics manufacturing as well as those common to a wide range of group-scheduling problems encountered in other production environments. Several heuristics, each incorporating different components that underlie the tabu search concept, are developed to solve this strongly NP-hard problem effectively in a timely manner. In order to investigate the quality of the heuristic solutions with respect to tight lower bounds, an effective and efficient decomposition approach is developed. The problem is decomposed into a master problem and single-machine subproblems, and a column generation algorithm is developed to solve the linear programming relaxation of the master problem. Branching schemes, compatible with the column generation subproblems, are employed to partition the solution space when the solution to the linear programming relaxation is not integral. Furthermore, tabu search based fast heuristics are implemented to solve the subproblems, and an effective stabilization method is developed to accelerate the column generation approach. An experimental design with both fixed and random factors accompanied by rigorous statistical analyses of computational tests conducted on randomly generated test problems as well as on a large size real industry problem confirm the high performance of the proposed approach in identifying quality lower bounds and strongly suggest its flexibility and applicability to a wide range of real problems.     

An exact approach to early/tardy scheduling with release dates

In this paper, we consider the single machine earliness/tardiness scheduling problem with different release dates and no unforced idle time. The problem is decomposed into weighted earliness and weighted tardiness subproblems. Lower bounding procedures are proposed for each of these subproblems, and the lower bound for the original problem is the sum of the lower bounds for the two subproblems. The lower bounds and several versions of a branch-and-bound algorithm are then tested on a set of randomly generated problems, and instances with up to 30 jobs are solved to optimality. To the best of our knowledge, this is the first exact approach for the early/tardy scheduling problem with release dates and no unforced idle time.     

Decomposition algorithm of dynamic programming for large-scale time-delay systems

This paper addresses the development of a dynamic programming decomposition-coordination algorithm for the optimal control of discrete-time large-scale systems with multiple time delays. The systems under study can be converted into the corresponding augmented systems satisfying the Markov processes denning the augmented state vectors. The resulting dynamic programming can then be further decomposed into a series of subproblems which might be solved in parallel by combining the dynamic programming techniques with approaches to matrix partition. The entire system's solution is finally given by the iterative computation between the subproblems being the local control level and the coordinator. The major advantages of the proposed algorithm over others are to avoid two-point boundary-value problems of the systems with multiple time delays and to significantly reduce the computer memory and time required for such large-scale systems optimal control problems.     

钢铁企业全流程物流优化问题的建模及分支——定价算法

研究了钢铁企业的全流程物流优化问题, 该问题在确保全流程各个工序机组产能和库存能力限制以及满足客户需求的前提下, 决策炼钢、连铸、热轧及冷轧工序间的物料流向和流量, 最小化物流成本、产能损失及库存费用. 为该问题建立了混合整数规划(Mixed integer programming, MIP)模型. 在问题求解中, 首先对MIP模型进行了Dantzig-Wolfe分解, 得到一个结构相对简单但列变量数目非常多的主问题和四个描述列向量空间的子问题. 然后, 从一个包含部分列变量的限制主问题出发, 通过子问题和主问题之间的迭代来获取主问题线性松弛的最优解. 最后, 将列生成同分支—定界相结合, 即分支—定价算法, 以获取原问题的整数最优解. 对某钢铁企业的实际生产数据扩展的随机算例进行仿真实验, 结果显示所提出的算法能够在合理计算时间内获得最优解或次优解.     

A parallel pruning technique for highly asymmetric assignmentproblems

We introduce a new two-phase technique to solve highly asymmetric assignment problems. In the first phase, the assignment problem is decomposed into subproblems which are solved in parallel. The first phase is used to exclude certain suboptimal assignments from consideration in the second phase. In the second phase, the optimal assignment is finalized. We show that the two-phase algorithm can reduce the theoretical time bound for solving an n×k assignment problem (nk/_n     

A method for decomposing mixed-integer linear programs with staircase structure

An algorithm is presented for solving mixed-integer linear programs with a staircase structure. The basic idea of the algorithm is to decompose the original problem into a series form of small-scale mixed-integer problems. For each problem decomposed, the solution is obtained by the conventional branch-and-bound method. In this algorithm the feasibility of the solution is always assured, but in order to save computation time the optimality condition is checked restrictedly for the solution obtained. The difference between the optimal objective value and the objective value obtained can be estimated. By examining numerical results, it is observed that the algorithm is efficient, requiring less computation time than other methods.     

用于间歇化工过程最优设计的遗传算法

间歇化工过程的最优设计问题是一类复杂且难以求解的组合优化问题。通过把这类问题分解为只包含离散变量的主导问题和只含连续变量的子问题,把遗传算法和线性规划法结合起来对其进行求解。并在算法中引入了一类新的算子,显著地提高了收敛概率、算例表明,该方法可以避免直接求解过程的复杂性和困难,并且具有很好的全局收敛性。     

A nonconvex nonsmooth regularization method for compressed sensing and low rank matrix completion

In this paper, a nonconvex and nonsmooth method for compressed sensing and low-rank matrix completion is studied. The proposed model is formulated as nonconvex regularized least square optimization problem. At first, an alternating minimization scheme is developed in which the problem can be decomposed into three subproblems, two of them are convex and the remaining one is smooth. Then, the convergence of the sequence which is generated by the alternating minimization algorithm is proved. In addition, some recovery guarantees are also analyzed. Finally, various numerical simulations are performed to test the efficiency of the method.     

连铸-轧制混流生产模式下轧批调度问题的分支-定价算法

研究了连铸——轧制在热装、温装和冷装混流生产模式下的一类新型轧批调度问题.以最小化温装钢坯（热钢锭）缓冷（等待）导致的热能损失和连轧机架切换带来的产能损失为目标,建立了整数规划模型.由于商业优化软件难以在有限时间内直接求得模型的最优解甚至可行解,提出利用Dantzig-Wolfe分解技术将原模型分解为主问题和子问题,采用列生成算法对主问题和子问题进行迭代求解得到原问题的紧下界,最后以列生成算法作为定界机制嵌入分支——定界框架中形成分支——定价算法,执行分支搜索过程以获得整数最优解.本文还从影响分支——定价算法性能的要素出发提出改进策略.针对主问题,提出列生成和拉格朗日松弛混合求解策略来抑制单一列生成算法的尾效应.针对价格子问题,在动态规划算法中提出了基于占优规则和标号下界计算方法来及早消除无效状态空间,加速求解过程.以钢铁企业的实际生产数据和扩展的随机算例进行了数值实验,结果显示所提出改进策略能够突破求解能力的限制,使分支——定价算法在可接受计算时间内求得工业规模问题的最优解.     

结合聚类分解的增强蚁群算法求解复杂绿色车辆路径问题EI北大核心CSCD

针对带时间窗的低能耗多车场多车型车辆路径问题(Low-energy-consumption multi-depots heterogeneousfleet vehicle routing problem with time windows,LMHFVPR_TW),提出一种结合聚类分解策略的增强蚁群算法(Enhanced ant colony optimization based on clustering decomposition,EACO_CD)进行求解.首先,由于该问题具有强约束、大规模和NP-Hard等复杂性,为有效控制问题的求解规模并合理引导算法在优质解区域搜索,根据问题特点设计两种基于K-means的聚类策略,将LMHFVPR_TW合理分解为一系列带时间窗的低能耗单车场单车型车辆路径子问题(Low-energy-consumption vehicle routing problem with time windows,LVRP_TW);其次,本文提出一种增强蚁群算法(Enhanced ant colony optimization,EACO)求解分解后的各子问题(LVRP_TW),进而获得原问题的解.EACO不仅引入信息素挥发系数控制因子进一步动态调节信息素挥发系数,从而有效控制信息素的挥发以提高算法的全局搜索能力,而且设计基于4种变邻域操作的两阶段变邻域局部搜索(Two-stage variable neighborhood search,TVNS)来增强算法的局部搜索能力.最后,在不同规模问题上的仿真和对比实验验证了所提EACO_CD的有效性.     

Generating subproblems in branch and bound algorithms for parallel machines scheduling problem

A branch and bound algorithm (B&B) has been widely used in various discrete and combinatorial optimization fields. To obtain optimal solutions as soon as possible for scheduling problems, three tools, which are branching, bounding and dominance rules, have been developed in the B&B algorithm. One of these tools, a branching is a method for generating subproblems and directly determines size of solution to be searched in the B&B algorithm. Therefore, it is very important to devise effective branching scheme for the problem.In this note, a survey of branching schemes is performed for parallel machines scheduling (PMS) problems with n independent jobs and m machines and new branching schemes that can be used for identical and unrelated PMS problems, respectively, are suggested. The suggested branching methods show that numbers of generated subproblems are much smaller than that of other methods developed earlier and therefore, it is expected that they help to reduce a lot of CPU time required to obtain optimal solutions in the B&B algorithm.     

Modified augmented Lagrangian coordination and alternating direction method of multipliers with parallelization in non-hierarchical analytical target cascading

Analytical Target Cascading (ATC) is a decomposition-based optimization methodology that partitions a system into subsystems and then coordinates targets and responses among subsystems. Augmented Lagrangian with Alternating Direction method of multipliers (AL-AD), one of efficient ATC coordination methods, has been widely used in both hierarchical and non-hierarchical ATC and theoretically guarantees convergence under the assumption that all subsystem problems are convex and continuous. One of the main advantages of distributed coordination which consists of several non-hierarchical subproblems is that it can solve subsystem problems in parallel and thus reduce computational time. Therefore, previous studies have proposed an augmented Lagrangian coordination strategy for parallelization by eliminating interactions among subproblems. The parallelization is achieved by introducing a master problem and support variables or by approximating a quadratic penalty function to make subproblems separable. However, conventional AL-AD does not guarantee convergence in the case of parallel solving. Our study shows that, in parallel solving using targets and responses of the current iteration, conventional AL-AD causes mismatch of information in updating the Lagrange multiplier. Therefore, the Lagrange multiplier may not reach the optimal point, and as a result, increasing penalty weight causes numerical difficulty in the augmented Lagrangian coordination approach. To solve this problem, we propose a modified AL-AD with parallelization in non-hierarchical ATC. The proposed algorithm uses the subgradient method with adaptive step size in updating the Lagrange multiplier and also maintains penalty weight at an appropriate level not to cause oscillation. Without approximation or introduction of an artificial master problem, the modified AL-AD with parallelization can achieve similar accuracy and convergence with much less computational cost compared with conventional AL-AD with sequential solving.     

A cooperative coevolutionary algorithm for the Multi-Depot Vehicle Routing Problem

The Multi-Depot Vehicle Routing Problem (MDVRP) is an important variant of the classical Vehicle Routing Problem (VRP), where the customers can be served from a number of depots. This paper introduces a cooperative coevolutionary algorithm to minimize the total route cost of the MDVRP. Coevolutionary algorithms are inspired by the simultaneous evolution process involving two or more species. In this approach, the problem is decomposed into smaller subproblems and individuals from different populations are combined to create a complete solution to the original problem. This paper presents a problem decomposition approach for the MDVRP in which each subproblem becomes a single depot VRP and evolves independently in its domain space. Customers are distributed among the depots based on their distance from the depots and their distance from their closest neighbor. A population is associated with each depot where the individuals represent partial solutions to the problem, that is, sets of routes over customers assigned to the corresponding depot. The fitness of a partial solution depends on its ability to cooperate with partial solutions from other populations to form a complete solution to the MDVRP. As the problem is decomposed and each part evolves separately, this approach is strongly suitable to parallel environments. Therefore, a parallel evolution strategy environment with a variable length genotype coupled with local search operators is proposed. A large number of experiments have been conducted to assess the performance of this approach. The results suggest that the proposed coevolutionary algorithm in a parallel environment is able to produce high-quality solutions to the MDVRP in low computational time.     

A parallel scheduling algorithm for reinforcement learning in large state space

The main challenge in the area of reinforcement learning is scaling up to larger and more complex problems. Aiming at the scaling problem of reinforcement learning, a scalable reinforcement learning method, DCS-SRL, is proposed on the basis of divide-and-conquer strategy, and its convergence is proved. In this method, the learning problem in large state space or continuous state space is decomposed into multiple smaller subproblems. Given a specific learning algorithm, each subproblem can be solved independently with limited available resources. In the end, component solutions can be recombined to obtain the desired result. To address the question of prioritizing subproblems in the scheduler, a weighted priority scheduling algorithm is proposed. This scheduling algorithm ensures that computation is focused on regions of the problem space which are expected to be maximally productive. To expedite the learning process, a new parallel method, called DCS-SPRL, is derived from combining DCS-SRL with a parallel scheduling architecture. In the DCS-SPRL method, the subproblems will be distributed among processors that have the capacity to work in parallel. The experimental results show that learning based on DCS-SPRL has fast convergence speed and good scalability.     

A new Lagrangian relaxation algorithm for hybrid flowshop scheduling to minimize total weighted completion time

We investigate the problem of scheduling n jobs in s-stage hybrid flowshops with parallel identical machines at each stage. The objective is to find a schedule that minimizes the sum of weighted completion times of the jobs. This problem has been proven to be NP-hard. In this paper, an integer programming formulation is constructed for the problem. A new Lagrangian relaxation algorithm is presented in which precedence constraints are relaxed to the objective function by introducing Lagrangian multipliers, unlike the commonly used method of relaxing capacity constraints. In this way the relaxed problem can be decomposed into machine type subproblems, each of which corresponds to a specific stage. A dynamic programming algorithm is designed for solving parallel identical machine subproblems where jobs may have negative weights. The multipliers are then iteratively updated along a subgradient direction. The new algorithm is computationally compared with the commonly used Lagrangian relaxation algorithms which, after capacity constraints are relaxed, decompose the relaxed problem into job level subproblems and solve the subproblems by using the regular and speed-up dynamic programming algorithms, respectively. Numerical results show that the new Lagrangian relaxation method produces better schedules in much shorter computation time, especially for large-scale problems.     

Adaptive composite suboptimal control for linear singularly perturbed systems with unknown slow dynamics

In this article, using singular perturbation theory and adaptive dynamic programming (ADP) approach, an adaptive composite suboptimal control method is proposed for linear singularly perturbed systems (SPSs) with unknown slow dynamics. First, the system is decomposed into fast‐ and slow‐subsystems and the original optimal control problem is reduced to two subproblems in different time‐scales. Afterward, the fast subproblem is solved based on the known model of the fast‐subsystem and a fast optimal control law is designed by solving the algebraic Riccati equation corresponding to the fast‐subsystem. Then, the slow subproblem is reformulated by introducing a system transformation for the slow‐subsystem. An online learning algorithm is proposed to design a slow optimal control law by using the information of the original system state in the framework of ADP. As a result, the obtained fast and slow optimal control laws constitute the adaptive composite suboptimal control law for the original SPSs. Furthermore, convergence of the learning algorithm, suboptimality of the adaptive composite suboptimal control law and stability of the whole closed‐loop system are analyzed by singular perturbation theory. Finally, a numerical example is given to show the feasibility and effectiveness of the proposed methods.     

On convex transformability and the solution of nonconvex problems via the dual of Falk

In structural optimization, most successful sequential approximate optimization (SAO) algorithms solve a sequence of strictly convex subproblems using the dual of Falk. Previously, we have shown that, under certain conditions, a nonconvex nonlinear (sub)problem may also be solved using the Falk dual. In particular, we have demonstrated this for two nonconvex examples of approximate subproblems that arise in popular and important structural optimization problems. The first is used in the SAO solution of the weight minimization problem, while the topology optimization problem that results from volumetric penalization gives rise to the other. In both cases, the nonconvex subproblems arise naturally in the consideration of the physical problems, so it seems counter productive to discard them in favor of using standard, but less well-suited, strictly convex approximations. Though we have not required that strictly convex transformations exist for these problems in order that they may be solved via a dual approach, we have noted that both of these examples can indeed be transformed into strictly convex forms. In this paper we present both the nonconvex weight minimization problem and the nonconvex topology optimization problem with volumetric penalization as instructive numerical examples to help motivate the use of nonconvex approximations as subproblems in SAO. We then explore the link between convex transformability and the salient criteria which make nonconvex problems amenable to solution via the Falk dual, and we assess the effect of the transformation on the dual problem. However, we consider only a restricted class of problems, namely separable problems that are at least C ¹ continuous, and a restricted class of transformations: those in which the functions that represent the mapping are each continuous, monotonic and univariate.