Computational experience with an algorithm for 0–1 integer programming

In a previous paper in this journal, the authors described an implicit enumeration algorithm for the all integer programming problem. In this paper, a specialization of the aforementioned algorithm for 0–1 integer programming problems is developed. The computational efficiency of this specialization is investigated by solving a set of test problems, using a computer code of the algorithm written for this purpose.     

求解0-1整数规划问题的混沌遗传算法*

针对一类特殊的0-1整数规划求解问题提出一种混沌遗传算法。该算法采用幂函数载波技术提高混沌搜索的充分性与遍历性,以混沌搜索算法得出的优化个体作为遗传算法的新群体进行交叉、变异等操作,提高种群质量,同时增加种群多样性,改善遗传算法的早熟问题。该算法被用于解决片上网络映射A3MAP(architecture-aware analytic mapping) 0-1整数规划问题。实验仿真证明,该算法的收敛速度和解的精度均优于A3MAP-GA。     

求解一类0-1整数规划问题的新方法--混沌搜索算法

首先对Logistic混沌变量的遍历区间[0，1]进行N等分；然后利用M个独立的混沌变量在这N^W个等分区域中搜索最优解，从而将混沌搜索算法推广应用于解决一类0-1整数规划问题。将这一混沌搜索算法应用于靶场效能优化的仿真表明，此方法收敛速度快、精度高、简单、易于实现，而且可以避免传统算法易陷入局部最优的缺点。     

一种求解整数规划与混合整数规划非线性罚函数方法

证明了任何一个变量有界的整数规划问题（IP）和混合整数规划问题（MIP）都可以转化为一个等价的非整数（或连续化）规划问题（NIP），并给出一个用非线性精确罚函数法来求解该等价NIP的方法，从而达到求解IP或MIP的目的，数值实验表明了算法的可行性。该方法可广泛用于各应用领域里IP和MIP的求解，特别是为非线性IP和MIP问题提供了一条通用 的求解途径，对解决许多实际优化问题具有重要意义。     

Algorithms for solving large-scale 0–1 goal programming and its application to reliability optimization problem

Goal programming(GP) is one of the most widely used Operations Research/Management Science/Industrial Engineering techniques for solving multiple criteria decision making (MCD M) problems. In the realistic decision making problems, many GP problems are involved a large number of 0–1 decision variables and a special type of system structures.

Inthis paper, we develop a computational algorithm for solving 0–1 goal programming with a generalized upper bounding (GUB) structures. From the views of the computational experience and storage requirement, we implemented an efficient software package for UN IX workstations in which we called it micro 0–1 GP(GUB). In the micro 0–1 GP(GUB) developed here, the GUB structures would be effectively handled and we designed user-friendly GP data entry subsystem.

As a real-world 0–1 goal programming problem with the GUB structures, we demonstrate an optimization problem of system reliability for allocating redundant units by the micro 0–1 GP(GUB) software package on an UN IX system.     

A method for interval 0–1 nonlinear programming problem using a genetic algorithm

In this paper, we formulate an optimal design problem of system reliability as a nonlinear integer programming problem with interval coefficients, transform it into a bicriteria 0–1 nonlinear programming problem without interval coefficients, and solve it directly using GA with holding nonlinear objective functions. Also, we demonstrate the efficiency of this method with a numerical example.     

整数规划的花授粉算法

整数规划是NP困难(Non-deterministic Polynomial-time hard,NP-hard)的经典问题之一。整数规划的花授粉算法(Integer Flower Pollination Algorithm,IFPA)是采用截断取整的方法,将最近开发的花授粉算法(Flower Pollination Algorithm,FPA)扩展到求解整数规划问题。通过对测试函数集进行仿真实验,结果表明IFPA拥有很好的性能和很强的全局寻优能力,可以作为一种实用方法用于求解无约束整数规划和有约束整数规划问题。     

一种求非线性整数规划最优解的仿生算法

从大自然植物生长中得到启发,提出了一种求解非线性整数规划全局最小解的仿生算法。该算法将植物生长过程及生长模式应用到非线性整数规划问题的求解,能够快速得到最优解。通过对各种不同类型非线性整数规划问题的具体求解,表明了该方法十分有效。     

Improved integer programming models for simple assembly line balancing and related problems

We propose a stronger formulation of the precedence constraints and the station limits for the simple assembly line balancing problem. The linear relaxation of the improved integer program theoretically dominates all previous formulations using impulse variables, and produces solutions of significantly better quality in practice. The improved formulation can be used to strengthen related problems with similar restrictions. We demonstrate their effectiveness on the U‐shaped assembly line balancing problem and on the bin packing problem with precedence constraints.     

Multiobjective 0‐1 integer programming for the use of sugarcane residual biomass in energy cogeneration

It is well known that Brazil is the largest producer of sugarcane in the world. Nevertheless, a great concern exists about the crop system used, because the most common practice is manual harvesting with prior straw burning. The Brazilian authorities have approved a law prohibiting the burning of sugarcane crop residue before harvesting. However, mechanized harvesting creates the new problem of having to deal with the residue. Many studies have indeed proposed the use of this residue as an energy source. A major difficulty in using this residue is how to economically transport sugarcane harvest biomass from a farm to a processing centre. Besides transport costs, another concern is knowing whether the energy generated by the straw offsets the energy used, in terms of fuel, in the process. This study proposes a multiobjective integer linear programming optimization model to choose sugarcane varieties so as to minimize costs in the use of crop residue and simultaneously maximize the energy balance in such a process. Computational results are presented and discussed.     

基于金字塔结构的群智能演化策略求解混合整数规划问题

混合整数非线性规划问题（mixed-integer nonlinear programming,MINLP） 广泛应用于科学及工程系统设计,传统的群智能算法在求解混合整数规划问题时,未能很好地解决种群内部个体或者种群之间开采与探索、竞争与协作的矛盾。为了解决这两个矛盾及更高效率地寻优,提出一种基于金字塔结构的群智能演化策略（swarm intelligent evolution strategy based on pyramid structure）的PES算法来求解混合整数规划问题。PES算法中明确的分工机制能够平衡全局与局部搜索的能力,晋升机制解决了种群间竞争与协作的矛盾。利用标准测试函数进行仿真,对比改进的粒子群算法（CLSPSO、CLSPSO2）及改进的差分进化算法（ridDE、ridDE2）的结果,发现PES算法在成功率与精度方面具有优势,也体现了PES算法的有效性。     

A Relationship between optimality and efficiency in multicriteria 0–1 programming problems

An efficient or nondominated solution to a multicriteria minimization problem is a feasible solution for which a decrease in the value of any criterion can only be obtained if the value of at least one other criterion is increased. Interest in the conditions under which solutions to multicriteria programming problems can be shown to be efficient has grown enormously in recent years, not least of all due to the awareness that significant planning problems can only be meaningfully modelled if multiple measures of effectiveness are considered. However, the broad class of multicriteria 0–1 programming problems, which are of great practical importance, has received only limited attention in the literature. We establish the identity of the set of efficient solutions with respect to such multicriteria programming problems with any criteria and any constraint set and the set of optimal solutions to a parametrized unicriterion problem incorporating these criteria. Illustrative numerical examples are provided.     

A dynamic attribute reduction algorithm based on 0-1 integer programming

Attribute reduction is an important research concept in rough set theory. Many attribute reduction algorithms were designed for the static information system in the past years. However, many real-world data are generated dynamically. Then a new dynamic attribute reduction algorithm based on a 0-1 integer programming is proposed to deal with the dynamic data in this paper. When multiple objects in the information system evolve over time, instead of treating the changed information table as a new one and finding the reduct again like rough set reduction algorithm does, the proposed algorithm just updates the original reduct. Therefore, its computational speed improves greatly. In addition, an approach of constraint preprocessing is also presented in this paper. Numerical experiments on twelve benchmark datasets testify the feasibility and validity of the proposed algorithm.     

整数规划问题智能求解算法综述*

为了对大规模整数规划问题的求解方法提供参考,对基于智能算法求解整数规划问题的研究进行了分析和评述。鉴于现有算法的缺陷与不足,讨论了应用智能算法求解整数规划问题未来可能的研究方向。     

Nonlinear integer goal programming models for acceptance sampling

Two lexicographic goal programming models are developed for determining the optimal sample size and acceptance number for acceptance sampling plans in quality control. Both models address the conflicting criteria inherent in such sampling problems, namely the average lot inspection cost and the average outgoing quality. The first model assumes a known constant lot fraction defective, while the second relaxes this assumption and instead assumes knowledge of a prior distribution on the fraction of defectives. A three-phase algorithm is developed which exploits the problem structure in order to find optimal solutions after examining a small percentage of the feasible sampling plans. On a set of 64 test problems the algorithm always found the optimal solution, typically after evaluating only 3–5% (and never more than 9%) of the feasible points.     

Software package for large-scale 0–1 linear programming on Unix system: GUB technique

Recently, a multiple criteria decision making (MCDM) has been well established as a practical approach to seek a satisfactory solution to a decision making problem. Linear programming (LP) is one of the most widely used OR/MS/IE techniques for solving MCDM problems. In the realistic decision making problems, many LP problems are involved a large number of 0–1 decision variables and a special type of system structures. So much kind of the large-scale 0–1 LP problems are simply too large fit into a microcomputer/workstation.

In this paper, we develop a software package micro 0–1LP(GUB) for solving LP problems with a generalized upper bounding (GUB) structure as large-scale 0–1LP problems on UNIX systems. From the views of the computational experience and storage requirement, micro 0–1LP(GUB) using the C programming language is implemented an efficient method in which the GUB structure would be effectively handled.

As a real-world large-scale 0–1LP problem with the GUB structures by the micro 0–1LP (GUB) software package developed here, we demonstrate an optimization problem of system reliability for selecting the allocating the components on an UNIX system, Sanyo/Icon MPS 020.     

基于三链DNA结构的0-1整数规划改进研究

为实现DNA计算中对解的有效筛选,防止探针与探针之间的错配、发夹结构等,以及便于检测最终解,提出了改进的三链DNA模型求解0-1规划的设计。该方法编码n个变量的每种组合的所有排列情况。此编码方式不仅使计算所需有效分子量从O((2n)!)下降到O(2nn!),并使对可行解的筛选更加有效。利用寡聚脱氧核苷酸(ODN)在RecA蛋白介导下与同源的双链DNA匹配成三螺旋DNA的特点,可推广到更多以双链DNA分子为计算模型的解的检测中。     

Application of 0-1 integer programming to multitarget tracking problems

This paper presents a new approach to the solution of multi-target tracking problems. 0-1 integer programming methods are used to alleviate the combinatorial computing difficulties that accompany any but the smallest of such problems. Multitarget tracking is approached as an unsupervised pattern recognition problem. A multiple-hypothesis test is performed to determine which particular combination of the many feasible tracks is most likely to represent actual targets. This multiple hypothesis test is shown to have the computational structure of the set packing and set partitioning problems of 0-1 integer programming. Multitarget tracking problems that are translated into this form can be rapidly solved, using well-known discrete optimization techniques such as implicit enumeration.