N车探险问题的一种ε-近似度的近似算法

本文探讨了一类N车探险问题的近似算法,首先通过建模将N车问题转变为一个等价的非线性0-1混合整数规划问题,进而将该非线性0-1混合整数规划问题转化为一个一般的带约束非线性规划问题,并用罚函数的方法将得到的带约束非线性规划问题化为相应的无约束问题.我们证明了可通过求解该无约束非线性规划问题得到原N车问题的ε-近似度的近似解,并设计了-个收敛速度为二阶的迭代箅法,文章最后给出算法实例.     

考虑占位决策的围堵嫌犯模型

研究了2011年中国大学生数学建模竞赛B题的突发事件中交巡警对在逃嫌犯的围堵问题。不同于对该问题的以往的研究,本文考虑了交巡警在包围圈中可以占据某些路口,使得嫌犯不能通过这些被交巡警占据的路口,从而为形成包围圈的交巡警赢得更多时间。利用两篇相关文献的关于点截集判断的结论和考虑占位决策的建模方法,以不同的目标函数建立了考虑占位决策的围堵嫌犯问题的三个混合0-1非线性整数规划模型。通过选取部分线性约束和目标函数一起组合成混合0-1线性整数规划模型,设计了基于混合0-1线性整数规划方法的算法,并给出了算例。     

0-1非线性混合整数规划的罚函数解法

本文中我们对一类0-1非线性混合整数规划的解法进行了探讨,通过罚函数把有约束问题化为相应的无约束问题,我们证明了可通过求解一个无约束非线性规划问题得到原问题的ε近似极小解,数值试验表明算法是有效的.     

整数规划新进展

整数规划是对全部或部分决策变量为整数的最优化问题的模型、算法及应用等的研究, 是运筹学和管理科学中应用最广泛的优化模型之一. 首先简要回顾整数规划的历史和发展进程, 概述线性和非线性整数规划的一些经典方法. 然后着重讨论整数规划若干新进展, 包括0-1二次规划的半定规划~(SDP)~松弛和随机化方法, 带半连续变量和稀疏约束的优化问题的整数规划模型和方法, 以及0-1二次规划的协正锥规划表示和协正锥的层级半定规划~(SDP)~逼近. 最后, 对整数规划未来研究方向进行展望并对一些公开问题进行讨论.     

与0-1二次规划问题等价的连续问题(英)

在较一般的条件下，证明了线性约束0-1二次规划问题等价于一个凹二次规划问题，改进了已有的结果．     

线性等式约束多目标规划的一个降维算法

本文提出具有线性等式约束多目标规划问题的一个降维算法．当目标函数全是二次或线性但至少有一个二次型时，用线性加权法转化原问题为单目标二次规划，再用降维方法转化为求解一个线性方程组．若目标函数非上述情形，首先用线性加权法将原问题转化为具有线性等式约束的非线性规划，然后，对这一非线性规划的目标函数二次逼近，构成线性等式约束二次规划序列，用降维法求解，直到满足精度要求为止．     

一种基于协同信息的团队伙伴选择方法

针对基于协同信息的团队伙伴选择问题,提出了一种决策分析方法。首先,给出了伙伴间的协同关系及基于协同信息的团队伙伴选择问题的描述;然后,构建了基于协同信息的团队伙伴选择的数学模型,该模型属于0-1二次整数规划问题,也是NP-hard问题,为了求解该问题,简要阐述了将0-1二次整数规划问题转化为0-1线性整数规划问题的方法;最后,通过一个实例分析说明了本文提出方法的可行性和有效性。     

线性约束0-1 二次规划的一个定界技术

本文给出确定线性约束0－1二次规划问题最优值下界的方法,该方法结合McBride和Yormark的思想和总体优化中定下界的方法,证明了所定的界较McBride和Yormark的要好．求解线性约束0－1二次规划问题的分支定界算法可以利用本文的定界技术．     

二次规划逆问题的牛顿方法

针对二次规划逆问题,将其表达为带有互补约束的锥约束优化问题.借助于对偶理论,将问题转化为变量更少的线性互补约束非光滑优化问题.通过扰动的方法求解转化后的问题并证明了收敛性.采用非精确牛顿法求解扰动问题,给出了算法的全局收敛性与局部二阶收敛速度.最后通过数值实验验证了该算法的可行性.     

一个解非线性0-1整数规划问题基于罚函数的混合粒子群优化算法

利用罚函数思想把非线性0-1整数规划问题转化为无约束最优化问题,然后把粒子群优化和罚函数方法结合构造出一个基于罚函数的混合粒子群优化算法,数值结果表明所提出的算法是有效的.     

A new linearization technique for multi-quadratic 0-1 programming problems

We consider the reduction of multi-quadratic 0-1 programming problems to linear mixed 0-1 programming problems. In this reduction, the number of additional continuous variables is O(kn) (n is the number of initial 0-1 variables and k is the number of quadratic constraints). The number of 0-1 variables remains the same.     

Decomposition and Linearization for 0-1 Quadratic Programming

This paper presents a general decomposition method to compute bounds for constrained 0-1 quadratic programming. The best decomposition is found by using a Lagrangian decomposition of the problem. Moreover, in its simplest version this method is proved to give at least the bound obtained by the LP-relaxation of a non-trivial linearization. To illustrate this point, some computational results are given for the 0-1 quadratic knapsack problem.     

Tightening concise linear reformulations of 0-1 cubic programs

A common strategy for solving 0-1 cubic programs is to reformulate the non-linear problem into an equivalent linear representation, which can then be submitted directly to a standard mixed-integer programming solver. Both the size and the strength of the continuous relaxation of the reformulation determine the success of this method. One of the most compact linear representations of 0-1 cubic programs is based on a repeated application of the linearization technique for 0-1 quadratic programs introduced by Glover. In this paper, we develop a pre-processing step that serves to strengthen the linear programming bound provided by this concise linear form of a 0-1 cubic program. The proposed scheme involves using optimal dual multipliers of a partial level-2 RLT formulation to rewrite the objective function of the cubic program before applying the linearization. We perform extensive computational tests on the 0-1 cubic multidimensional knapsack problem to show the advantage of our approach.     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

A Tabu Search Algorithm for Quadratic 0—1 Programming Problem

1.IntroductionThemathematicalmodelofaquaduatico-1programmingproblemisasfollows:MinimizesubjecttwhereI,AsfaraspaperL1'2Jcanseemedel(I)(fordu=O)isveryimPOrtantinthemarshallingofsinglegrouptrainbetweenmarshallingstationsinrailwaynetworkandthemarshallingoftraininnetw0rkwiththetw0types0fvehiclefl0w,butproblem(I)isNP-C.C0nsiderarelax-ationproblemasf0llows:MinimizeIngeneral,solvingrelaxati0nproblemiseasierthansolvingcombinatiorial0ptimalpr0b-lem,thesameaslinearpr0grammingproblemissolvableinPOly…     

Parametric global optimisation for bilevel programming

We propose a global optimisation approach for the solution of various classes of bilevel programming problems (BLPP) based on recently developed parametric programming algorithms. We first describe how we can recast and solve the inner (follower’s) problem of the bilevel formulation as a multi-parametric programming problem, with parameters being the (unknown) variables of the outer (leader’s) problem. By inserting the obtained rational reaction sets in the upper level problem the overall problem is transformed into a set of independent quadratic, linear or mixed integer linear programming problems, which can be solved to global optimality. In particular, we solve bilevel quadratic and bilevel mixed integer linear problems, with or without right-hand-side uncertainty. A number of examples are presented to illustrate the steps and details of the proposed global optimisation strategy.     

New convergent heuristics for 0–1 mixed integer programming

Several hybrid methods have recently been proposed for solving 0–1 mixed integer programming problems. Some of these methods are based on the complete exploration of small neighborhoods. In this paper, we present several convergent algorithms that solve a series of small sub-problems generated by exploiting information obtained from a series of relaxations. These algorithms generate a sequence of upper bounds and a sequence of lower bounds around the optimal value. First, the principle of a linear programming-based algorithm is summarized, and several enhancements of this algorithm are presented. Next, new hybrid heuristics that use linear programming and/or mixed integer programming relaxations are proposed. The mixed integer programming (MIP) relaxation diversifies the search process and introduces new constraints in the problem. This MIP relaxation also helps to reduce the gap between the final upper bound and lower bound. Our algorithms improved 14 best-known solutions from a set of 108 available and correlated instances of the 0–1 multidimensional Knapsack problem. Other encouraging results obtained for 0–1 MIP problems are also presented.