The Interactive Method: A New Approach to Solving a Kind of Mixed Integer Programming

Porduction planning often comes up in the form of programming problems with continuous variables, where investment project planing usually reduces to zero-one programming. Combination of the choices of investment projects with the existent production capacity, therefore, yields mixed integer programming. With this background, this paper provides a new approach to solving mixed integer programming problems by combining the man-machine interactive method for multiobjective programming with graphics generating techniques.     

Implementation of Presolving and Interior-Point Algorithm for Linear & Mixed Integer Programming: SOFTWARE

Linear and mixed integer programming are very popular and important methods to make efficient scientific management decision. With large size of real application data, the use of linear-mixed integer programming is facing problems with more complexity; therefore, preprocessing techniques become very important. Preprocessing aims to check and delete redundant information from the problem formulation. It is a collection of techniques that reduce the size of the problem and try to strengthen the formulation. Fast and effective preprocessing techniques are very important and essential for solving linear or mixed integer programming instances. In this paper, we demonstrate a set of techniques to presolve linear and mixed integer programming problems. Experiment results showed that when preprocessing is well done, then it becomes easier for the solver; we implemented interior-point algorithm for computational experiment. However, preprocessing is not enough to reduce the size and total nonzero elements from the constraints matrix. Moreover, we also demonstrate the impact of minimum degree reordering on the speed and storage requirements of a matrix operation.All techniques mentioned above are presented in a multifunctional software to facilitate users.     

一类非线性两级混合整数规划问题的全局最优解的近似算法

讨论了一类非线性两级混合整数规划的求解问题 .基于非线性混合整数规划理论和算法 ,探讨了对上级规划问题采用模拟退火求解混合整数规划的算法 ;对下级规划问题采用内罚函数法 .实际运算证明 ,该算法是有效的.     

一种混合整数双层线性规划的全局优化方法

通过求得下层问题的对偶问题可行域上的极点,将上层所有变量为0 1型变量和下层所有变量为连续型变量的双层线性规划转化为有限个混合整数线性规划问题,从而用求解混合整数线性规划的方法获得问题的全局最优解.由于下层问题的对偶问题可行域只有有限个极点,所提出的方法具有全局收敛性.     

混合整数规划问题遗传算法的研究及仿真实现

提出了一种可以处理混合整数规划问题(MIP)的混合遗传算法MIGA。该算法采用二进制映射模式可变长度染色体编码,在进化过程逐渐缩小编码的搜索空间,从而在加快收敛速度的同时改善了迭代的精度,能很好处理离散变量和连续变量的混合整数规划问题。以一纯整数规划问题为例,利用分枝定界算法只能得到唯一的一个最优调度策略,而MIGA算法则可以得到一系列的最优调度策略,对这些最优调度策略进一步的分析,还可以得到调度问题一些灵敏度参数,在实际应用中具有更大的灵活性。     

不确定环境下战斗机采购效能评估模型

为了处理采购战斗机过程中存在的不确定信息, 首次将偏好规划理论引入到采购效能评估中. 先建立战斗机采购效能评估体系, 指标和偏好的不确定性用区间形式表示, 求解采用RICH法; 针对一些属性只有备选方案的序数信息的情况, 采用混合整数规划进行建模. 模型通过线性不等式与偏好规划方法进行集成. 最后, 通过实例验算表明该方法在不确定环境下的有效性.     

基于动态规划的装配线物料搬运节能调度方法

为有效提升混流装配线的生产效率与环境效益,提出了装配线多载量小车物料搬运节能调度方法.以最小化最大线边库存与总能耗为目标,建立了多目标混合整数规划模型.通过问题性质分析,将混合优化问题转为离散优化问题,降低了模型复杂度.针对动态规划算法维数灾问题,提出了基于剪枝规则的多目标规划算法:通过剪枝规则剪除被支配状态,缩减搜索空间以提高计算效率.其中,为满足动态规划的马尔可夫性,定义了新的状态表示方式.最后,仿真实验验证了所提出的调度方法的优越性与算法的有效性.     

电子侦察卫星任务合成探测及混合调度

任务合成探测对于提高电子侦察卫星的侦察效益具有重要意义。分析了电子侦察任务合成探测的条件及性质,建立了多星合成探测调度问题的混合整数规划模型。提出了一种基于模型分解的优化求解算法,将模型分解为任务指派主问题与动态合成子问题,任务指派主问题通过遗传算法生成不同卫星的任务分配方案,动态合成子问题则根据指派的任务进行优化,生成完整的卫星侦察计划。测试案例验证了方法的有效性。     

New approach to determine common weights in DEA efficiency evaluation model

Data envelopment analysis (DEA) is a mathematical programming approach to appraise the relative efficiencies of peer decision-making unit (DMU), which is widely used in ranking DMUs. However, almost all DEA-related ranking approaches are based on the self-evaluation efficiencies. In other words, each DMU chooses the weights it prefers to most, so the resulted efficiencies are not suitable to be used as ranking criteria. Therefore this paper proposes a new approach to determine a bundle of common weights in DEA efficiency evaluation model by introducing a multi-objective integer programming. The paper also gives the solving process of this multi-objective integer programming, and the solution is proven a Pareto efficient solution. The solving process ensures that the obtained common weight bundle is acceptable by a great number of DMUs. Finally a numeral example is given to demonstrate the approach.     

A Lagrangian relaxation-based algorithm for the allocation of yard cranes for yard activities with different priorities

This paper proposes a mixed integer programming model for the allocation of rail mounted gantry cranes for four basic yard activities with different priorities.The model pays special attention to the typical features of this kind of gantry cranes,such as a restricted traveling range and a limited number of adjustments during loading and discharging operations.In contrast to most of the literature dealing with these four yard activities individually,this paper models them into an integrated problem,whose computational complexity is proved to be NP-hard.We are therefore motivated to develop a Lagrangian relaxation-based heuristic to solve the problem.We compare the proposed heuristic with the branch-and-bound method that uses commercial software packages.Extensive computational results show that the proposed heuristic achieves competitive solution qualities for solving the tested problems.     

约束规划求解集装箱装卸系统集成调度问题

集装箱码头装卸系统中的岸桥、集卡和场桥的集成调度问题本质上是有阻塞、准备时间可分离并且依赖操作顺序的三阶段混合流水车间调度问题,现有文献多采用启发式算法求解该问题.本文先建立了一个紧凑的混合整数规划模型,然后从约束规划的角度建模求解该问题,提出了一个约束规划模型,以区间变量作为决策变量,并采用"扩展操作任务"的概念来定义区间决策变量以提升求解效率.为了展示约束规划的建模灵活性,还扩展了模型以考虑机器效率不同的因素.数值实验显示约束规划模型能够在很短的时间内对大规模算例求出高质量的解.     

基于拉格朗日松弛的预约调度模型与算法

针对带有爽约的预约调度问题,在假定未爽约病人都在相应预约段的起始点准时到达的情况下,构建了一个以预约人数为优化变量的整数规划模型.目标函数包括服务病人收益、病人等待费用及系统超时费用.通过松弛各时间段剩余人数概率的关联约束,提出了基于拉格朗日松弛的求解算法,其松弛问题通过动态规划求解,对偶问题通过经典的次梯度法求解.数值实验表明,针对小规模的预约段数,该算法都能找到最优解;当预约段数较大时,算法找到的最好解整体上优于文献中已有的算法,从而验证了算法的有效性.     

编队卫星对地观测调度问题模型比较研究

研究了编队卫星对地观测调度问题。分别建立了基于问题自然描述和基于有向图描述的两类整数规划模型，运用整数规划凸包理论比较了两类模型与各自对应的线性松弛模型之间的最优值差异，得出了基于有向图描述的线性松弛模型更接近于原问题凸包的结论，并基于有向图描述模型设计了不完全分支定界算法。最后，在随机生成的仿真算例下，运用ILOG CPLEX实现了该算法，实验结果表明了模型及算法的有效性，并验证了对于两类整数规划模型的边界分析。     

一种求解混合整数非线性规划的新算法

针对混合整数非线性规划求解难的问题,本文给出了一种新的求解策略--混合序列差异演化算法,该算法采取混合编码的形式以便处理连续变量、整数变量以及混合整数变量的优化问题.最后通过数例检验算法的优越性,仿真结果表明该算法求解效率高、收敛速度快、全局搜索能力强.     

两个双目标竞争选址问题模型

研究了多目标竞争选址问题,建立了市场份额最大、费用最小和利润最大、利润率也最大的两类双目标竞争选址模型.探讨了模型的性质与相互关系,并利用多目标优化技术将这两类双目标模型转化为同一类型的单目标参数整数规划问题求解,给出有效解集的精确求解方法和近似求解方法,并通过数值例子说明求解方法.     

MIP formulations and heuristics for solving parallel batching problems

This paper addresses the scheduling problem involving batch processing machines, which is also known as parallel batching in the literature. The presented mixed integer programming formulation first provides an elegant model for the problem under study. Furthermore, it enables solutions to the problem instances beyond the capability of exact methods developed so far. In order to alleviate computational burden, the authors propose MIP-based heuristic approaches which balance solution quality and computing time.     

COMPARISON OF MAX—MIN APPROACH AND NN METHOD FOR RELIABILITY OPTIMIZATION OF SERIES—PARALLEL SYSTEM

Two heuristics, the max-min approach and the Nakagawa and Nakashima method, are consideredfor the redundancy allocation problem with series-parallel structure. The max-min approach canformulate the problem as an integer linear programming problem instead of an integer nonlinearproblem. This paper presents a comparison between those methods from the standpoint of solutionquality and computational complexity. The experimental results show that the max-min approach issuperior to the Nakagawa and Nakashima method in terms of solution quality in small-scale problems,but analysis of computational complexity shows that the max-min approach is inferior to other greedyheuristics.     

实时条件下多车辆路径与调度

研究实时条件下的多车辆路径与调度问题，重点研究了多种费用，包括车辆空驶费用、任务延迟费用和任务拒绝费用下的问题模型及求解。给出了问题的数学描述，并对其静态问题，构造了一个混合整数规划模型。随后提出了两种滚动时域求解策略。最后通过仿真实例，对几种策略的性能进行了对比。     

堆区混贝的堆场场吊调度模型与算法

为提高集装箱码头堆场场吊作业效率,研究了堆场单堆区混贝条件下的场吊调度问题.在单堆区内集装箱混贝堆放的前提下,提出了堆场场吊装卸作业时间窗约束、作业次序依赖的设备调整时间及堆场空间约束等,并在此基础上建立了整数规划模型.针对这一模型设计了改进禁忌搜索算法对问题进行求解.最后通过数值实验表明改进后的算法在对大规模问题求解时具有良好的效果,且算法效率较高.     

基于种族优生的进化规划用于混合非线性整数规划

混合非线性整数规划是在许多工程应用中经常遇到的重要问题。本文提出一种基于种族优生的进化规划算法用于求解混合非线性整数规划。一方面，该算法基于多种群并且每一代都选择各种群的最优秀个体作为下一代的种群祖先。另一方面，该算法的进化步长、种群规模和处理约束条件时所取的参数在进化过程中是动态变化的。实验表明该方法求解混合非线性整数规划问题的仿真结果优于现有的研究成果(GA，ES，SA)。