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.     

基于整数规划的驾驶员调度系统-TRACS II

本阐述一个世界名的成功的公共交通驾驶员调度系统-TRACSⅡ。该系统的核心算法是基于整数规划的“生成与选择”方法。本首先对驾驶员调度同题以及TRACS⒓系统的研发背景和主要功能进行简要介绍;然后,重点阐述该系统的整数规划模型和求解方法;最后,举出几个成功应用的实例,并归纳出该系统存在的局限性,为进一步研究指出方向。     

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

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

提前监考安排的0-1线性规划模型

提前考试的监考安排工作因诸多因素而显得比较繁琐,因此自动排考有相当的实际意义.基于监考安排的公平性和人本原则,根据监考时间和上课时间搭配的紧密程度,给监考时间设定相应的权值,从而建立了0-1线性规划模型.最后编制模型的AMPL程序,并以某高校数学系的教务数据为例进行计算,其求解速度和结果表明了所建模型的合理性.     

Mixed Integer Linear Programming in Process Scheduling: Modeling,Algorithms, and Applications

This paper reviews the advances of mixed-integer linear programming (MILP) based approaches for the scheduling of chemical processing systems. We focus on the short-term scheduling of general network represented processes. First, the various mathematical models that have been proposed in the literature are classified mainly based on the time representation. Discrete-time and continuous-time models are presented along with their strengths and limitations. Several classes of approaches for improving the computational efficiency in the solution of MILP problems are discussed. Furthermore, a summary of computational experiences and applications is provided. The paper concludes with perspectives on future research directions for MILP based process scheduling technologies.     

排序问题的线性规划松弛方法

本文研究排序问题的线性规划松弛方法，对单台机器排序问题1｜prec｜∑wjCj介绍基于三个确定性线性规划松弛的2一近似算法，对平行机排序问题R｜rij｜（wjCj）介绍基于随机线性规划松弛的2-近似算法。这后一个算法对排序问题R｜（wjCj｜是3／2-近似算法．     

Decomposition and Dynamic Cut Generation in Integer Linear Programming

Decomposition algorithms such as Lagrangian relaxation and Dantzig-Wolfe decomposition are well-known methods that can be used to generate bounds for mixed-integer linear programming problems. Traditionally, these methods have been viewed as distinct from polyhedral methods, in which bounds are obtained by dynamically generating valid inequalities to strengthen an initial linear programming relaxation. Recently, a number of authors have proposed methods for integrating dynamic cut generation with various decomposition methods to yield further improvement in computed bounds. In this paper, we describe a framework within which most of these methods can be viewed from a common theoretical perspective. We then discuss how the framework can be extended to obtain a decomposition-based separation technique we call decompose and cut. As a by-product, we describe how these methods can take advantage of the fact that solutions with known structure, such as those to a given relaxation, can frequently be separated much more easily than arbitrary real vectors.     

混合整数规划求解多联票据印刷过程中的生产调度问题

多联票据的印刷过程包括排版、单联印刷和多联配页与装订三个过程。该过程是柔性的流水生产线与装配混合的生产系统。本文研究了该系统中的票据印刷生产调度问题,目标是最小化所有产品的最大完成时间（Makespan）。该问题到目前为止还没有人研究,本文首先建立了该问题的混合整数规划模型,然后提出了该模型的求解方法,并给出了该问题的下界。最后的量化示例和算例试验表明本文的模型是有效的。     

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.     

Stability and Regularization of Vector Problems of Integer Linear Programming

In this article we consider the problem of finding the Pareto set, and also the problem of lexicographic optimization. We study several types of stability, understood as preservation of certain properties of the efficient solution set under "small" changes of input data. The borders of such changes are ascertained. Necessary and sufficient conditions of stability are specified. A regularizing operator is proposed for transferring a probably unstable problem to a series of stable ones.     

序关系与0—1规划问题(下)

§ 9 集 合 组 装 问 题 以下,我们讨论如§5中所给出的准序。对于一个集 合XB_1~n,如果x=(x_1,x_2,…x_n)∈X,存在N={1,2,…,n}上的一个置换π使得 有x_(π(1))x_(π(2))…x_(π(n)),即 对于X是一个线性序,则称X是正则的。 相仿地,对于一个布尔或拟布尔函数f,也可建立准序:     

Practical Application of Linear/Integer Programming in Agriculture

This paper indicates that in the current economic climate, linear programming could well be worth reconsidering as a maximizing technique in farm planning. This particularly applies when it is used in conjunction with integer programming, which allows many of L.P.'s problems to be overcome.ADAS procedures for L.P./integer programming are described. Reference is made to a range of models and more detail given on the new Bedfordshire mixed cropping model.An explanation is given as to how ADAS models are used in advisory and promotional work.     

Media Selection and Fuzzy Linear Programming

Mathematical Programming models have been suggested as a tool for optimal media selection. In order to accommodate several objective functions goal programming models have been put forward. It seems, however, that these models are not yet operational and efficient enough to be used in practice.Based on these approaches a model is suggested which seems to be suited to map appropriately fuzzy and subjective phenomena and which is flexible enough to incorporate several criteria (objective functions) simultaneously.An interactive use is envisaged which would help to adapt the model easily to different real world conditions.     

A Novel Mixed Integer Linear Programming Model for Clustering Relational Networks

Integer programming models for clustering have applications in diverse fields addressing many problems such as market segmentation and location of facilities. Integer programming models are flexible in expressing objectives subject to some special constraints of the clustering problem. They are also important for guiding clustering algorithms that are capable of handling high-dimensional data. Here, we present a novel mixed integer linear programming model especially for clustering relational networks, which have important applications in social sciences and bioinformatics. Our model is applied to several social network data sets to demonstrate its ability to detect natural network structures.     

A Relation between Multiprocessor Scheduling and Linear Programming

The general non preemptive multiprocessor scheduling problem (NPMS) is NP-Complete, while in many specific cases, the same problem is Time-polynomial. A first connection between PMS and linear programming was established by Yannanakis, Sauer and Stone, who associated to any PMS instance some specific linear program. The main result inside this paper consists in a characterization of the partially ordered structures which allow the optimal values of any associated PMS instance to be equal to the optimal values of the corresponding linear programs.     

非线性0-1规划问题的蜂群算法

针对非线性0-1规划,提出采用一种智能优化算法——蜂群算法进行求解.描述了蜂群算法的实现过程,并在计算机上编程予以实现.经大量实例测试,并与其它算法进行比较,获得了满意的结果.说明了蜂群算法在解决非线性0-1规划问题上的可行性与有效性,同时具有良好的优化能力..