具有离散性的连续性模型映射

为了实现在连续性空间中的离散分段问题,采用解决离散性问题的方法虚拟构造连续性集合,将连续性问题映射为分段的离散问题,根据集合中元素的离散特性实现连续性模型的分段求解.通过数据结构的设计与压缩路径的算法证实,模型的映射能够解决实际问题的分段求解.     

具有多级选择的离散网络平衡设计模型与算法

本文提出了一种新的离散网络平衡设计二层规划模型,模型同时考虑了新增路段及已有路段的扩容,而且允许不同等级的扩容选择.模型求解中,上层采用粒子群算法,而下层则采用本文作者提出的仿射尺度内点算法.数值计算结果显示,本文构建的算法能够快速有效地求解这类新的网络平衡设计二层规划模型.     

交通网络建设序列的动态规划方法

交通网络建设序列优化是交通规划中一个重要问题。文章对交通网络设计及其建设序列问题的研究现状进行了分析。按照网络建设中规划者和用户间的关系,以交通网络建设序列下的各阶段系统总费用作为上层规划,以各阶段的交通流用户平衡模型作为下层规划,建立了双层规划模型。并依照问题的特点,采用动态规划的求解方法进行探讨,而下层模型则采用了基于路径搜索的GP算法进行求解。并针对网络规划算例进行了计算,针对固定和变动客流OD两种情况下的结果进行了分析。计算的结果表明,问题的双层规划模型和动态规划求解算法能够为路网规划决策提供支持。     

离散花朵授粉算法求解混合流水线调度问题

提出一种改进的离散花朵授粉算法求解以最小化任务完成时间为目标的混合流水线调度问题.算法采用一种基于排列的编码和解码的方法,根据混合流水线调度问题具有离散性的特点,对花朵授粉算法的相关操作重新进行定义,建立了离散的花朵授粉模型.为了加快算法的局部搜索能力,构建了一种基于动态自适应变化工件块的变领域搜索策略.实验仿真表明,改进的离散花朵授粉算法在求解混合流水线调度问题具有较好的性能,是一种有效的方法.     

离散变量结构优化设计的组合算法*

本文首先给出了离散变量优化设计局部最优解的定义,然后提出了一种综合的组合算法.该算法采用分级优化的方法,第一级优化首先采用计算效率很高且经过随机抽样性能实验表明性能较高的启发式算法─—相对差商法,求解离散变量结构优化设计问题近似最优解 X ;第二级采用组合算法,在 X 的离散邻集内建立离散变量结构优化设计问题的(-1,0.1)规划模型,再进一步将其化为(0,1)规划模型,应用定界组合算法或相对差商法求解该(0,1)规划模型,求得局部最优解.解决了采用启发式算法无法判断近似最优解是否为局部最优解这一长期未得到解决的问题,提高了计算精度,同时,由于相对差商法的高效率与高精度,以上综合的组合算法的计算效率也还是较高的.     

求解车辆路径问题的离散蝙蝠算法

根据车辆路径问题的数学模型,分析了它的具体特征,从而对BA的操作算子又进行了重新定义,设计了求解VRP问题的离散蝙蝠算法,并通过实例测试将离散蝙蝠算法与其他算法进行比较,验证了该算法求解VRP问题的有效性与可行性.     

基于离散群居蜘蛛算法的WSNs分簇路由优化

对无线传感器网络(WSNs)路由优化问题进行研究,提出一种基于离散群居蜘蛛算法的WSNs分簇路由优化方案.首先定量分析节点覆盖冗余度期望值与网络覆盖率的关系,筛选出能够保证网络覆盖率要求的最少网络工作节点,其次研究分簇大小与网络节点密度的关系,动态地确定最佳的分簇个数.基于此,以簇间距离和簇首能量为评价指标构建簇间通信模型,重新定义蜘蛛个体编码方式和更新策略,采用离散群居蜘蛛算法对模型进行求解,最终实现WSNs分簇路由优化.仿真结果表明,方案能够满足网络覆盖要求,而且与其它路由优化算法相比,延长了网络生命周期,降低了网络能耗.     

跳跃扩散下双障碍期权定价的数值解

提出了一种求解带有跳跃的双障碍期权定价模型的数值方法.算法采用了Crank-Nicolson 有限差分格式和复化梯形公式对模型进行离散,对离散后的线性系统采用GMRES迭代法求解,并且构造了一个新的预处理算子以加速迭代法的收敛.数值实验验证了该方法能快速求解模型并达到二阶收敛精度.     

带转向延误的非对称用户平衡模型与算法

为准确刻画交通网络和出行行为的复杂特征,考虑路口的转向延误及路段之间相互作用的非对称性因素,用非线性互补理论建立了带转向延误的非对称用户平衡模型,分析了用户平衡解的存在性.结合列生成算法采用有效路径集来避免枚举路网中所有路径的优点和FBLSA算法求解非线性互补问题的全局收敛性特点,提出了修正FBLSA算法.最后针对一个中等规模的交通网络进行数值实验,结果显示该算法对处理非对称网络是十分有效的.     

基于二进制编码非洲野狗算法的TSP问题研究

针对非洲野狗算法求解优化问题时全局性收敛不强的特点,对该算法进行改进,提出了改进的非洲野狗算法,结合二进制编码设计了求解离散优化问题的二进制编码非洲野狗算法,并将该算法应用于求解TSP问题并与其他算法做对比分析.研究结果显示,求解TSP问题时二进制编码非洲野狗算法求解精度更高,收敛速度更快.     

Formulation and computation of general financial equilibrium

In this paper a model of competitive financial equilibrium is introduced, which yields the optimal composition of assets and liabilities in each sector's portfolio, as well as the market clearing prices for each instrument. The variational inequality formulation of the equilibrium conditions is then utilized to establish existence and uniqueness properties of the solution pattern. Finally, an algorithm is proposed for the computation of the equilibrium pattern; the algorithm resolves the problem into simple network subproblems which can then be solved in closed form. The algorithm is then applied to an example.     

Massively parallel computation of large-scale spatial price equilibrium models with discriminatory ad valorem tariffs

In this paper, we develop a perfectly competitive spatial equilibrium model in price and quantity variables in the presence of discriminatory ad valorem tariffs, a widely used trade policy instrument. We derive the equilibrium conditions and formulate them as a variational inequality problem. An algorithm is then proposed for the computation of the equilibrium pattern and convergence results established. The algorithm resolves the problem into very simple subproblems, each of which can be solved simultaneously and in closed form. Finally, the algorithm is implemented on the massively parallel Thinking Machines CM-2 and CM-5 architectures, known as the Connection Machines, and numerical results presented.     

Numerical solution of the equilibrium problem for a membrane with embedded rigid inclusions

The equilibrium problem for a membrane containing a set of volume and thin rigid inclusions is considered. A solution algorithm reducing the original problem to a system of Dirichlet ones is proposed. Several examples are presented in which the problem is solved numerically by applying the finite element method.     

Primal-dual interior-point method for thermodynamic gas-particle partitioning

A mathematical model for the computation of the phase equilibrium and gas-particle partitioning in atmospheric organic aerosols is presented. The thermodynamic equilibrium is determined by the global minimum of the Gibbs free energy under equality and inequality constraints for a system that involves one gas phase and many liquid phases. A primal-dual interior-point algorithm is presented for the efficient solution of the phase equilibrium problem and the determination of the active constraints. The first order optimality conditions are solved with a Newton iteration. Sequential quadratic programming techniques are incorporated to decouple the different scales of the problem. Decomposition methods that control the inertia of the matrices arising in the resolution of the Newton system are proposed. A least-squares initialization of the algorithm is proposed to favor the convergence to a global minimum of the Gibbs free energy. Numerical results show the efficiency of the approach for the prediction of gas-liquid-liquid equilibrium for atmospheric organic aerosol particles.     

Proximal methods for a class of bilevel monotone equilibrium problems

We consider a bilevel problem involving two monotone equilibrium bifunctions and we show that this problem can be solved by a simple proximal method. Under mild conditions, the weak convergence of the sequences generated by the algorithm is obtained. Using this result we obtain corollaries which improve several corresponding results in this field.     

An Iterative LP Algorithm for Quadratic Spatial Equilibria

This paper describes a partitioning algorithm based on the Benders decomposition to solve net import spatial equilibrium models. The method decomposes the problem into a linear master problem and a quadratic subproblem. It is shown that the quadratic subproblem is trivial, and the associated dual variables can be determined through ordinary calculus. Therefore, the quadratic spatial equilibrium problem is solved iteratively by using linear programming software.     

A new model and hybrid approach for large scale inventory routing problems

This paper studies an inventory routing problem (IRP) with split delivery and vehicle fleet size constraint. Due to the complexity of the IRP, it is very difficult to develop an exact algorithm that can solve large scale problems in a reasonable computation time. As an alternative, an approximate approach that can quickly and near-optimally solve the problem is developed based on an approximate model of the problem and Lagrangian relaxation. In the approach, the model is solved by using a Lagrangian relaxation method in which the relaxed problem is decomposed into an inventory problem and a routing problem that are solved by a linear programming algorithm and a minimum cost flow algorithm, respectively, and the dual problem is solved by using the surrogate subgradient method. The solution of the model obtained by the Lagrangian relaxation method is used to construct a near-optimal solution of the IRP by solving a series of assignment problems. Numerical experiments show that the proposed hybrid approach can find a high quality near-optimal solution for the IRP with up to 200 customers in a reasonable computation time.     

Order and static stability into the strip packing problem

This paper investigates the two-dimensional strip packing problem considering the case in which items should be arranged to form a physically stable packing satisfying a predefined item unloading order from the top of the strip. The packing stability analysis is based on conditions for the static equilibrium of rigid bodies, differing from others strategies which are based on area and percentage of support. We consider an integer linear programming model for the strip packing problem with the order constraint, and a cutting plane algorithm to handle stability, leading to a branch-and-cut approach. We also present two heuristics: the first is based on a stack building algorithm; and, the last is a slight modification of the branch-and-cut approach. The computational experiments show that the branch-and-cut model can handle small and medium-sized instances, whereas the heuristics found almost optimal solutions quickly for several instances. With the combination of heuristics and the branch-and-cut algorithm, many instances are solved to near optimality in a few seconds.     

关于求解随机用户均衡问题的截断拟牛顿型信赖域法研究

信赖域法是一种保证全局收敛性的优化算法,为避免Hessian矩阵的计算,基于拟牛顿校正公式构造了求解带线性等式约束的非线性规划问题的截断拟牛顿型信赖域法.首先给出了截断拟牛顿型信赖域法的构造过程及具体步骤;然后针对随机用户均衡模型中变量和约束的特点对算法进行了修正,并将多种拟牛顿校正公式下所得结果与牛顿型信赖域法的结果进行了比较,结果发现基于对称秩1校正公式的信赖域法更为合适.最后基于数值算例结果得到了一些在算法编程过程中的重要结论,对其它形式信赖域法的编程实现具有一定的参考意义.     

Benders decomposition for a class of variational inequalities

This paper examines Benders decomposition for a useful class of variational inequality (VI) problems that can model, e.g., economic equilibrium, games or traffic equilibrium. The dual of the given VI is defined. Benders decomposition of the original VI is derived by applying a Dantzig–Wolfe decomposition procedure to the dual of the given VI, and converting the dual forms of the Dantzig–Wolfe master and subproblems to their primal forms. The master problem VI includes a new cut at each iteration, with information from the latest subproblem VI, which is solved by fixing the “difficult” variables at values determined by the previous master problem. A scalar parameter called the convergence gap is calculated at each iteration; a negative value is equivalent to the algorithm making progress in that the last master problem solution is made infeasible by the new cut. Under mild conditions, the convergence gap approaches zero in the limit of many iterations. With a more restrictive condition that still admits many useful models, a zero value of the convergence gap implies that the master problem has found a solution of the VI. A small model of competitive equilibrium of three commodities in two regions serves as an illustration.