对带有盒约束的二次整数规划的一种线性化方法

本文主要讨论了二次整数规划问题的线性化方法.在目标函数为二次函数的情况下,我们讨论了带有二次约束的整数规划问题的线性化方法,并将文献中对二次0-1问题的研究拓展为对带有盒约束的二次整数规划问题的研究.最终将带有盒约束的二次整数规划问题转化为线性混合本文主要讨论了二次整数规划问题的线性化方法.在目标函数为二次函数的情况下,我们讨论了带有二次约束的整数规划问题的线性化方法,并将文献中对二次0-1问题的研究拓展为对带有盒约束的二次整数规划问题的研究.最终将带有盒约束的二次整数规划问题转化为线性混合0-1整数规划问题,然后利用Ilog-cplex或Excel软件中的规划求解工具进行求解,从而解决原二次整数规划.     

Parallel Integer Optimization for Crew Scheduling

Performance aspects of a Lagrangian relaxation based heuristic for solving large 0-1 integer linear programs are discussed. In particular, we look at its application to airline and railway crew scheduling problems. We present a scalable parallelization of the original algorithm used in production at Carmen Systems AB, Göteborg, Sweden, based on distributing the variables. A lazy variant of this approach which decouples communication and computation is even useful on networks of workstations. Furthermore, we develop a new sequential active set strategy which requires less work and is better adapted to the memory hierarchy properties of modern RISC processors. This algorithm is also suited for parallelization on a moderate number of networked workstations.     

基于整数规划的医疗卫生服务中心选址模型

根据农村医疗卫生服务中心的特点,结合卫生服务人数限制、费用限制、距离限制等决定因素建立了卫生服务中心选址模型,分析了层次分析法及隐枚举法求解医疗卫生服务选址模型的差异性.结果显示:所建立的医疗卫生服务中心选址模型在限制条件下能够最大程度的满足人民群众对卫生服务的需求,且隐枚举法求解0-1整数规划比层次分析更具有可行性与有效性.     

邮路规划与邮车调度最优化理论研究

对小规模MTSP问题,建立了可精确求解方案的0-1规划模型,并在满足邮政运输需求的前提下给出了最佳方案.问题一首先以县支局、县局为顶点构建无向赋权图,通过Floyd算法求解各局间的最短距离;然后以Fijk为决策变量,以邮车工作时间、车辆运载能力为主要约束,建立以总空载损失费用最小为目标的0-1非线性规划模型,运用规划软件Lingo求解.问题二考虑到市邮路成本,我们采用分层规划策略,首先以市支局、县局为顶点构建无向赋权图,求解出最短路矩阵,建立以邮路运行成本最小为目标的0-1非线性规划模型IIA求解;然后,建立各县区的最短路矩阵,同样建立规划模型IIB求解各县运输方案.问题三由于县局地理位置不变,对区邮路无影响,故以全市各县支局为中心采用逐步最优方法对所有县区支局重新划分;然后采用模型IIB求解.第四问中考虑县局迁移,我们建立近似的启发式算法完成县局选址,并运用规划模型II求解的到新方案.最后,我们对两种区域划分调整方法还进行了定量的分析.     

Global Optimization Versus Integer Programming in Portfolio Optimization under Nonconvex Transaction Costs

This paper is concerned with a portfolio optimization problem under concave and piecewise constant transaction cost. We formulate the problem as nonconcave maximization problem under linear constraints using absolute deviation as a measure of risk and solve it by a branch and bound algorithm developed in the field of global optimization. Also, we compare it with a more standard 0–1 integer programming approach. We will show that a branch and bound method elaborating the special structure of the problem can solve the problem much faster than the state-of-the integer programming code.     

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.     

Integrating SQP and Branch-and-Bound for Mixed Integer Nonlinear Programming

This paper considers the solution of Mixed Integer Nonlinear Programming (MINLP) problems. Classical methods for the solution of MINLP problems decompose the problem by separating the nonlinear part from the integer part. This approach is largely due to the existence of packaged software for solving Nonlinear Programming (NLP) and Mixed Integer Linear Programming problems.In contrast, an integrated approach to solving MINLP problems is considered here. This new algorithm is based on branch-and-bound, but does not require the NLP problem at each node to be solved to optimality. Instead, branching is allowed after each iteration of the NLP solver. In this way, the nonlinear part of the MINLP problem is solved whilst searching the tree. The nonlinear solver that is considered in this paper is a Sequential Quadratic Programming solver.A numerical comparison of the new method with nonlinear branch-and-bound is presented and a factor of up to 3 improvement over branch-and-bound is observed.     

一般整数规划中有效不等式的同步升维

有效不等式在整数规划的定界研究中具有重要的意义.研究了一般整数规划问题的有效不等式的升维方法,引入超加性函数给出同步升维的条件,并给出有效不等式的同步升维的具体方法,算例表明本文提出的方法是有效的.     

Logic-Based Modeling and Solution of Nonlinear Discrete/Continuous Optimization Problems

This paper presents a review of advances in the mathematical programming approach to discrete/continuous optimization problems. We first present a brief review of MILP and MINLP for the case when these problems are modeled with algebraic equations and inequalities. Since algebraic representations have some limitations such as difficulty of formulation and numerical singularities for the nonlinear case, we consider logic-based modeling as an alternative approach, particularly Generalized Disjunctive Programming (GDP), which the authors have extensively investigated over the last few years. Solution strategies for GDP models are reviewed, including the continuous relaxation of the disjunctive constraints. Also, we briefly review a hybrid model that integrates disjunctive programming and mixed-integer programming. Finally, the global optimization of nonconvex GDP problems is discussed through a two-level branch and bound procedure.     

A lift-and-project cutting plane algorithm for mixed 0–1 programs

We propose a cutting plane algorithm for mixed 0–1 programs based on a family of polyhedra which strengthen the usual LP relaxation. We show how to generate a facet of a polyhedron in this family which is most violated by the current fractional point. This cut is found through the solution of a linear program that has about twice the size of the usual LP relaxation. A lifting step is used to reduce the size of the LP's needed to generate the cuts. An additional strengthening step suggested by Balas and Jeroslow is then applied. We report our computational experience with a preliminary version of the algorithm. This approach is related to the work of Balas on disjunctive programming, the matrix cone relaxations of Lovász and Schrijver and the hierarchy of relaxations of Sherali and Adams.The research underlying this report was supported by National Science Foundation Grant #DDM-8901495 and Office of Naval Research Contract N00014-85-K-0198.     

Using a Mixed Integer Quadratic Programming Solver for the Unconstrained Quadratic 0-1 Problem

In this paper, we consider problem (P) of minimizing a quadratic function q(x)=x ^t Qx+c ^t x of binary variables. Our main idea is to use the recent Mixed Integer Quadratic Programming (MIQP) solvers. But, for this, we have to first convexify the objective function q(x). A classical trick is to raise up the diagonal entries of Q by a vector u until (Q+diag(u)) is positive semidefinite. Then, using the fact that x _i ²=x _i, we can obtain an equivalent convex objective function, which can then be handled by an MIQP solver. Hence, computing a suitable vector u constitutes a preprocessing phase in this exact solution method. We devise two different preprocessing methods. The first one is straightforward and consists in computing the smallest eigenvalue of Q. In the second method, vector u is obtained once a classical SDP relaxation of (P) is solved. We carry out computational tests using the generator of (Pardalos and Rodgers, 1990) and we compare our two solution methods to several other exact solution methods. Furthermore, we report computational results for the max-cut problem.     

人才招聘的优化模型

人力资源是企业最重要的资源,一个企业如果能适时、适质、适量的获得所需要的人才,并使其在合适的岗位上创造良好绩效,就能在竞争激烈的环境中立于不败之地.本文通过建立人才招聘优化模型来为企业更合理、更科学招聘人才提供服务.     

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

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

An Exact Solution Method for Reliability Optimization in Complex Systems

Systems reliability plays an important role in systems design, operation and management. Systems reliability can be improved by adding redundant components or increasing the reliability levels of subsystems. Determination of the optimal amount of redundancy and reliability levels among various subsystems under limited resource constraints leads to a mixed-integer nonlinear programming problem. The continuous relaxation of this problem in a complex system is a nonconvex nonseparable optimization problem with certain monotone properties. In this paper, we propose a convexification method to solve this class of continuous relaxation problems. Combined with a branch-and-bound method, our solution scheme provides an efficient way to find an exact optimal solution to integer reliability optimization in complex systems. This research was partially supported by the Research Grants Council of Hong Kong, grants CUHK4056/98E, CUHK4214/01E and 2050252, and the National Natural Science Foundation of China under Grants 79970107 and 10271073.     

Lifting, tilting and fractional programming revisited

Lifting, tilting and fractional programming, though seemingly different, reduce to a common optimization problem. This connection allows us to revisit key properties of these three problems on mixed integer linear sets. We introduce a simple common framework for these problems, and extend known results from each to the other two.     

Exploiting equalities in polynomial programming

We propose a novel approach for solving polynomial programs over compact domains with equality constraints. By means of a generic transformation, we show that existing solution schemes for the, typically simpler, problem without equalities can be used to address the problem with equalities.     

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

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

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.     

（0,1）矩阵,组合竞赛与Ramsey问题

本文提出用（０，１）矩阵的乘法来研究Ｒａｍｓｅｙ问题，并结合组合竞赛观点给出一大类经典Ｒａｍｓｅｙ数的构造性（算法性）下界。     

公务员招聘的优化模型

对“公务员招聘”问题进行了深入探讨,运用模糊数学和运筹学理论,先建立了招聘人员的模糊多属性综合评价模型,解决了用人单位择优录取公务员的问题;然后建立了0-1整数规划模型解决了人力资源的优化配置问题,从而给出了一种科学有效的公务员招聘的方法.