Solution to the quadratic assignment problem usingsemi-Lagrangian relaxation

The semi-Lagrangian relaxation （SLR）, a new exactmethod for combinatorial optimization problems with equality constraints,is applied to the quadratic assignment problem （QAP）.A dual ascent algorithm with finite convergence is developed forsolving the semi-Lagrangian dual problem associated to the QAP.We perform computational experiments on 30 moderately difficultQAP instances by using the mixed integer programming solvers,Cplex, and SLR＋Cplex, respectively. The numerical results notonly further illustrate that the SLR and the developed dual ascentalgorithm can be used to solve the QAP reasonably, but also disclosean interesting fact： comparing with solving the unreducedproblem, the reduced oracle problem cannot be always effectivelysolved by using Cplex in terms of the CPU time.

基于代理拉格朗日松弛的电-氢耦合网络优化调度

针对电-氢耦合网络的调度问题,将电网与氢供应网协调优化,决定氢运输拖车的路径,并考虑氢运输的时效性,提出基于代理拉格朗日松弛的分布式求解方法。首先,考虑氢运输中拖车的行程和到达加氢站的时间等因素,以电网和氢供应网的运行成本最小为目标函数,建立电-氢耦合网络的混合整数线性规划调度模型;其次,根据代理拉格朗日松弛法将该调度问题分解成电制氢与氢供应子问题,并进行同步协调;最后,通过算例验证了所提模型及求解方法的有效性。

交互能源机制下多区域综合能源系统能源共享协同调度

能源共享需求下多区域综合能源系统存在集中调度决策变量多、约束复杂、区域主体信息隐私难以保护,以及传统分布式算法收敛不光滑、收敛速度慢等问题。为此,设计了交互能源机制下地区系统运营商进行多区域能源管理的框架,建立了考虑新能源不确定性的能源共享日前调度随机优化模型,并构建了基于绝对值函数线性化的代理增广拉格朗日松弛算法进行求解。基于所提模型和算法,地区系统运营商根据各区域提交的初始供求信息制定区域间的交易价格,各区域以运行成本、碳排放成本、弃光成本最小为目标优化设备出力和能源交互量,并进行迭代出清。算例结果表明所提模型能够有效提升区域运行效益,提高新能源消纳,且所提算法较常用分布式算法在求解速度和求解质量方面更具优越性。

具有相同机组水火电调度问题的新算法

对Lagrangian松弛法求解水火电调度问题时由相同机组引起解震荡现象进行了研究。通过一个例子分析了震荡产生的根本原因。对此 ,在松弛函数中引入了惩罚项并采用了伪次梯度法来修正乘子。新算法在求解低层子问题时并不同时求解 ,使震荡现象在很大程度上得以克服 ,同时可大幅度地降低偶解对约束的违反程度。通过简单的例子和对一个包含两组相同机组的短期发电调度问题的计算表明 ,对偶解的约束违反程度明显地降低 ,解震荡明显地减弱且最后可行解的质量有显著的改善。

HFS多处理器任务调度的改进拉格朗日松弛

针对带多处理器任务的混合流水车间调度问题,以总加权完成时间为目标函数,考虑加工阶段间运输时间和工件动态到达的生产特征,提出了一种基于代理次梯度法的改进拉格朗日松弛算法。算法采用每次迭代只最优求解几个拉格朗日子问题的异步迭代策略,利用代理次梯度获得合适的乘子更新方向。分别应用所提出的改进算法和常规的基于次梯度法的拉格朗日松弛算法对多达150个工件的问题进行仿真测试,结果表明,所提出的改进算法比常规拉格朗日松弛算法表现出更好的求解能力,尤其是求解大规模问题。

A branch-and-bound algorithm for multi-dimensional quadratic 0-1 knapsack problems

In this paper, a branch-and-bound method for solving multi-dimensional quadratic 0-1 knapsack problems was studied. The method was based on the Lagrangian relaxation and the surrogate constraint technique for finding feasible solutions. The Lagrangian relaxations were solved with the maximum-flow algorithm and the Lagrangian bounds was determined with the outer approximation method. Computational results show the efficiency of the proposed method for multi-dimensional quadratic 0-1 knapsack problems.

Grid Integration of Wind Generation Considering Remote Wind Farms:Hybrid Markovian and Interval Unit Commitment

Grid integration of wind power is essential to reduce fossil fuel usage but challenging in view of the intermittent nature of wind.Recently,we developed a hybrid Markovian and interval approach for the unit commitment and economic dispatch problem where power generation of conventional units is linked to local wind states to dampen the effects of wind uncertainties.Also,to reduce complexity,extreme and expected states are considered as interval modeling.Although this approach is effective,the fact that major wind farms are often located in remote locations and not accompanied by conventional units leads to conservative results.Furthermore,weights of extreme and expected states in the objective function are difficult to tune,resulting in significant differences between optimization and simulation costs.In this paper,each remote wind farm is paired with a conventional unit to dampen the effects of wind uncertainties without using expensive utility-scaled battery storage,and extra constraints are innovatively established to model pairing.Additionally,proper weights are derived through a novel quadratic fit of cost functions.The problem is solved by using a creative integration of our recent surrogate Lagrangian relaxation and branch-and-cut.Results demonstrate modeling accuracy,computational efficiency,and significant reduction of conservativeness of the previous approach.

零等待混合流水车间问题优化研究

研究了带零等待的混合流水车间调度问题,考虑工件动态到达的实际生产特征,以最小化总加权完成时间为目标,建立整数规划模型,然后设计一种基于代理次梯度法的改进拉格朗日松弛算法。基于工件分解策略将拉格朗日松弛问题分解为多个工件级子问题,不同于每次迭代要求最优求解所有子问题的次梯度法,所设计的代理次梯度法通过每次迭代最优求解几个子问题得到松弛问题的近似解,进而获得搜索拉格朗日乘子的代理次梯度方向,最后设计启发式构造可行时间表。通过仿真实验,证明了所设计的算法在解的质量和收敛性方面均优于传统的使用次梯度法的拉格朗日松弛算法。

An efficient approach for solving mixed-integer programming problems under the monotonic condition

Many important integer and mixed-integer programming problems are difficult to solve.A representative example is unit commitment with combined cycle units and transmission capacity constraints.Complicated transitions within combined cycle units are difficult to follow,and system-wide coupling transmission capacity constraints are difficult to handle.Another example is the quadratic assignment problem.The presence of cross-products in the objective function leads to nonlinearity.In this study,building upon the novel integration of surrogate Lagrangian relaxation and branch-and-cut,such problems will be solved by relaxing selected coupling constraints.Monotonicity of the relaxed problem will be assumed and exploited and nonlinear terms will be dynamically linearised.The linearity of the resulting problem will be exploited using branch-and-cut.To achieve fast convergence,guidelines for selecting stepsizing parameters will be developed.The method opens up directions for solving nonlinear mixed-integer problems,and numerical results indicate that the new method is efficient.