求解整数线性规划问题的定界阻止算法的改进*

在现有求解整数线性规划问题的定界阻止算法的基础上提出了一种改进。该算法通过目标函数超平面截线性规划松弛问题的有效约束锥而形成一个单纯形;然后,引入一串平行片来切割该单纯形产生更低维的凸多面体;最后,在片上的这些凸多面体上执行阻止搜寻程序。由于单纯形和片上凸多面体的极顶点可以直接通过公式计算,且变量在片上凸多面体上的取值区间更窄,改进的定界阻止算法既方便又高效,这得到了一些经典算例和随机产生的算例的验证。     

整数线性规划的切割与分支算法

基于整数线性规划问题的分支定界方法,以子问题或根问题的目标最优值作为参数,构造了一种新的切割不等式,能够方便地切割子问题或根问题的非整数最优解.在分支之前进行这种切割,产生了一种新的求解整数线性规划问题的切割与分支算法.将该算法应用于求解一些经典的数值例子,实验结果表明,与经典的分支定界方法相比,该算法大大减少了分支的数量,提高了计算效率.随着问题规模的增大,该算法的计算优越性体现得更加明显.     

求解整数线性规划的一种高效隐数搜寻

提出了一种求解整数线性规划的新的隐数算法。首先,该算法引入了一组线性变换,将线性松弛问题的最优非基变量变换到一组新变量,使新变量有更小的取值范围。然后,在目标函数超平面上对非基变量和新变量进行隐数计算,从而大大提高了隐数搜寻的效率。     

整数线性规划的改进分支定界算法

分支定界(B&B)算法是求解整数线性规划(ILP)问题的一种最常用的方法,如何划分问题(分支)和按何种策略选择子问题进行扩展是影响算法效率的两个重要因素.提出了一种改进的分支定界算法,采用伪费用分支策略划分问题,采用深度优先搜索(DFS)策略选择子问题进行扩展,并在Matlab中编程实现.数值实验表明,改进的算法能够有效提高求解效率,当问题规模较大时,改进效果尤其明显.     

加权约束满足问题的符号ADD求解算法

加权约束满足问题(WCSP)是一类软约束满足问题。给出WCSP的代数决策图(ADD)描述,以及基于ADD的两种符号求解算法。首先,通过对变量和变量域值的二进制编码,给出软约束图的ADD表示。其次,将分支定界搜索算法与桶消元算法及符号ADD技术相结合,在静态变量序下,利用结点一致性预处理技术,对WCSP问题进行符号ADD求解。通过引入有向弧一致性计数技术提高符号ADD算法的搜索下界,对符号ADD求解算法作了改进。最后,对大量随机生成的测试用例进行实验分析。结果表明,文中算法在性能上明显优于带有存在有向弧一致性或结点一致性预处理技术的具有前向检查功能的深度优先分支定界搜索算法。     

非凸二次规划全局极小问题的新型分枝定界算法

针对求解多面集上二次函数的全局近似最优解问题,利用逐步缩小对偶间隙的处理办法,提出了一个新型分枝定界算法。新算法的主要改进之处是利用了Lagrange 对偶性获取下界。最后,用构造和随机产生的问题实例,对提出的新算法和传统的分枝定界算法做了初步的数值比较实验。计算实验表明算法对求解中大规模非凸二次规划问题的有效性。     

复合并行机排序问题的启发式算法研究

为有效解决复合并行机排序的极小化最大完成时间问题,提出了分支定界算法和改进的启发式动态规划算法。利用分支定界算法的3个工具:分支模型、边界和优先规则,构建出分支搜索树。按优先规则进行定界搜索,从而减小了问题求解规模。将原始作业转换为虚拟作业,根据Johnson法则,求解出原问题的最优排序。改进的动态规划算法复杂度分析和计算实验表明,这两个算法可靠性高并且可以解决实际问题。     

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

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

求解混流装配线调度问题的蚁群算法

以最小化总的传送中断时间为目标函数的混流装配线调度问题是丰田生产方式中自动化概念的一个重要问题,而新颖的蚁群算法具有通用性、鲁棒性、并行搜索以及易于与其他启发式算法结合的优点,可以解决多种组合优化问题,对其进行了改进,以便更适于求解混流装配线的调度问题。实验表明：改进的蚁群算法解决了混流装配线的调度问题,得到了优于分支定界法、模拟退火法和遗传算法的可行解。     

最小费用充电站选址问题的分支定界算法

电动汽车的充电站选址问题是当前社会的热点问题,其实质是组合优化中经典的NP-hard问题。基于最小开设费用对充电站选址问题进行研究,首先对该问题进行了数学建模,进而研究了该问题的数学性质并给予相应的证明,利用这些性质减小问题的规模,从而降低问题的求解难度;然后设计了上下界子算法以及降阶子算法,基于这些子算法提出了一种可以快速缩小问题规模同时得到最优解的分支定界算法,降低了时间复杂度,同时可以对解空间进行大量剪枝加快求解速度;最后通过分析和求解一个示例来进一步阐述所提算法的原理和执行过程。     

Parametric tabu-search for mixed integer programs

A parametric form of tabu-search is proposed for solving mixed integer programming (MIP) problems that creates and solves a series of linear programming (LP) problems embodying branching inequalities as weighted terms in the objective function. The approach extends and modifies a parametric branch and bound procedure of Glover [Parametic branch and bound. OMEGA, The International Journal of Management Science 1978;6:1–9], replacing its tree search memory by the adaptive memory framework of tabu-search and introducing new associated strategies that are more flexible than the mechanisms of branch and bound.     

Exact procedures for solving the discrete ordered median problem

The discrete ordered median problem (DOMP) integrates classical discrete location problems, such as the N-median, N-center and Uncapacitated Facility Location problems. It was introduced by Nickel (In: Fleischmann B, Lasch R, Derigs U, Domschke W, Rieder U, editors. Operations Research Proceedings 2000, Berlin: Springer, 2001. p. 71–76), who formulated it as both a nonlinear and a linear integer program. We propose an alternative integer linear programming formulation for the DOMP, discuss relationships between both integer linear programming formulations, and show how properties of optimal solutions can be used to strengthen these formulations. Moreover, we present a specific branch and bound procedure to solve the DOMP more efficiently. We test the integer linear programming formulations and this branch and bound method computationally on randomly generated test problems.     

线性整数规划的分支限界解法及其MATLAB实现

讨论了计算机算法中分支限界法对于线性整数规划问题的解决思想,通过MATLAB中提供的优化函数,实现了快速解决线性整数规划的问题,同时改进了对于此类问题的计算量巨大和编制程序困难的问题,使用了堆栈而不是递归,节约了计算中的资源.编制的MATLAB线性整数规划的程序,可以编译成C/C 实现和COM组件.     

The augmented weighted Tchebychev norm for optimizing a linear function over an integer efficient set of a multicriteria linear program

In this paper, we propose a new exact algorithm, using an augmented weighted Tchebychev norm, for optimizing a linear function on the efficient set of a multiple objective integer linear programming problem. This norm is optimized progressively by improving the value of the linear criteria and going through some efficient solutions. The method produced not only the best efficient solution of the linear objective function but also a subset of nondominated solutions that can help decision makers to select the best decision among a large set of Pareto solutions.     

Lower bounds and exact algorithms for the quadratic minimum spanning tree problem

We address the quadratic minimum spanning tree problem (QMSTP), the problem of finding a spanning tree of a connected and undirected graph such that a quadratic cost function is minimized. We first propose an integer programming formulation based on the reformulation–linearization technique (RLT). We then use the idea of partitioning spanning trees into forests of a given fixed size and obtain a QMSTP reformulation that generalizes the RLT model. The reformulation is such that the larger the size of the forests, the stronger lower bounds provided. Thus, a hierarchy of formulations is obtained. At the lowest hierarchy level, one has precisely the RLT formulation, which is already stronger than previous formulations in the literature. The highest hierarchy level provides the convex hull of integer feasible solutions for the problem. The formulations introduced here are not compact, so the direct evaluation of their linear programming relaxation bounds is not practical. To overcome that, we introduce two lower bounding procedures based on Lagrangian relaxation. These procedures are embedded into two parallel branch-and-bound algorithms. As a result of our study, several instances in the literature were solved to optimality for the first time.     

Exact and heuristic procedures for single machine scheduling with quadratic earliness and tardiness penalties

The present paper studies the single machine, no-idle-time scheduling problem with a weighted quadratic earliness and tardiness objective. We investigate the relationship between this problem and the assignment problem, and we derive two lower bounds and several heuristic procedures based on this relationship. Furthermore, the applicability of the time-indexed integer programming formulation is investigated. The results of a computational experiment on a set of randomly generated instances show (1) the high-quality results of the proposed heuristics, (2) the low optimality gap of one of the proposed lower bounds and (3) the applicability of the integer programming formulation to small and medium size cases of the problem.     

A computational study of parametric tabu search for 0–1 mixed integer programs

We present a computational study of parametric tabu search for solving 0–1 mixed integer programming (MIP) problems, a generic heuristic for general MIP problems proposed by Glover [Glover F. Parametric tabu-search for mixed integer programs. Computers and Operations Research 2006; 33: 2449–94.]. This approach solves a series of linear programming problems by incorporating branching inequalities as weighted terms in the objective function. New strategies are proposed for uncovering feasible and high-quality solutions and extensive computational tests are performed on instances from the literature.     

Scheduling jobs on a single batch processing machine with incompatible job families and weighted number of tardy jobs objective

In this paper, we minimize the weighted and unweighted number of tardy jobs on a single batch processing machine with incompatible job families. We propose two different mixed integer linear programming (MILP) formulations based on positional variables. The second formulation does not contain a big-M coefficient. Two iterative schemes are discussed that are able to provide tighter linear programming bounds by reducing the number of positional variables. Furthermore, we also suggest a random key genetic algorithm (RKGA) to solve this scheduling problem. Results of computational experiments are shown. The second MILP formulation is more efficient with respect to lower bounds, while the first formulation provides better upper bounds. The iterative scheme is effective for the weighted case. The RKGA is able to find high-quality solutions in a reasonable amount of time.