求解整数规划问题的一个搜索方法

本文整数规划问题给出一种搜索方法,它类似于求解连续变量优化问题的迭代方法,从一个好的初始可行解出发,寻找一个搜索方向,沿着这个方向求出改进的可行解,然后又开始下一次迭代。此方法简单易行,可以求出问题的最优解或近似最优解,对于整数线性规划问题和整数非线性规划问题的求解都适用,并且容易推广到求解大规校整数线性规划问题。文中附有计算例子,说明方法是有效的。     

A heuristic routine for solving large loading problems

The loading problem involves the optimal allocation of n objects, each having a specified weight and value, to m boxes, each of specified capacity. While special cases of these problems can be solved with relative ease, the general problem having variable item weights and box sizes can become very difficult to solve. This paper presents a heuristic procedure for solving large loading problems of the more general type. The procedure uses a surrogate procedure for reducing the original problem to a simpler knapsack problem, the solution of which is then employed in searching for feasible solutions to the original problem. The procedure is easy to apply, and is capable of identifying optimal solutions if they are found.     

Coordinated replenishments from multiple suppliers with price discounts

In this study we present an integer programming model for determining an optimal inbound consolidation strategy for a purchasing manager who receives items from several suppliers. The model considers multiple suppliers with limited capacity, transportation economies, and quantity discounts. We propose an integrated branch and bound procedure for solving the model. This procedure, applied to a Lagrangean dual at every node of the search tree, combines the subgradient method with a primal heuristic that interact to change the Lagrangean multipliers and tighten the upper and lower bounds. An enhancement to the branch and bound procedure is developed using surrogate constraints, which is found to be beneficial for solving large problems. We report computational results for a variety of problems, with as many as 70,200 variables and 3665 constraints. Computational testing indicates that our procedure is significantly faster than the general purpose integer programming code OSL. A regression analysis is performed to determine the most significant parameters of our model. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 579–598, 1998     

Surrogate duality in a branch-and-bound procedure

Recent research has led to several surrogate multiplier search procedures for use in a primal branch-and-bound procedure. As single constrained integer programming problems, the surrogate subproblems are also solved via branch-and-bound. This paper develops the inner play between the surrogate subproblem and the primal branch-and-bound trees which can be exploited to produce a number of computational efficiencies. Most important is a restarting procedure which precludes the need to solve numerous surrogate subproblems at each node of a primal branch-and-bound tree. Empirical evidence suggests that this procedure greatly reduces total computation time.     

Successive approximation in separable programming: An improved procedure for convex separable programs

We implement a solution procedure for general convex separable programs where a series of relatively small piecewise linear programs are solved as opposed to a single large one, and where, based on bound calculations developed in [13] and [14], the ranges of linearization are systematically reduced for successive programs. The procedure inherits ε-convergence to the global optimum in a finite number of steps, but perhaps its most distinct feature is the rigorous way in which ranges containing an optimal solution are reduced from iteration to iteration. This paper describes the procedure, called successive approximation, discusses its convergence, tightness of the bounds, bound-calculation overhead, and its robustness. It presents a computer implementation to demonstrate its effectiveness for general problems and compares it (1) with the more standard separable programming approach and (2) with one of the recent augmented Lagrangian methods [10] included in a comprehensive study of nonlinear programming codes [12]. It seems clear from over 130 cases resulting from 80 distinct problems studied here that significant savings in terms of computational effort can be realized by a judicious use of the procedure, and the ease with which it can be used is appreciably increased by the robustness it shows. Moreover, for most of these problems, the advantage increases as the size, nonlinearity, and the degree of desired accuracy increase. Other important benefits include significantly smaller storage requirements, the ability to estimate the error in the current solution, and to terminate the algorithm as soon as the acceptable level of accuracy has been achieved. Problems requiring up to about 10,000 nonzero elements in their specification and about 45,000 nonzero elements in the generated separable programs resulting from up to 70 original nonlinear variables and 70 nonlinear constraints are included in the computations.     

Order-preserving allocation of jobs to two machines

In this paper, we consider the problem of minimizing the mean flow time of jobs to be processed on two machines. The jobs have a predetermined order, perhaps reflecting the order of arrival, and each job has a known processing time. We wish to assign the jobs to machines so as to minimize the mean flow time, with the constraint that the original order must be preserved within the subset of jobs assigned to each machine. An efficient algorithm based on dynamic programming is developed.     

On a constraint qualification in a nondifferentiable programming problem

A mathematical programming problem with an objective function containing the square root of a positive semidefinite quadratic form has been considered by Mond. In order to use a transposition theorem of Eisenberg, Mond introduces a complicated constraint qualification. In this note we give a simple geometric characterization to this constraint qualification and show that it is implied by the generalized Slater constraint qualification.     

A branch-bound algorithm for the capacitated facilities location problem

This paper discusses a mixed integer programming method for solving the Facilities Location Problem with capacities on the facilities. The algorithm uses a Decomposition technique to solve the dual of the associated continuous problem in each branch-bound iteration. The method was designed to produce the global optimum solution for problems with up to 100 facilities and 1,000 customers. Computational experience and a complete example are also presented in the appendix.     

A finite algorithm for concave minimization over a polyhedron

We present a new algorithm for solving the problem of minimizing a nonseparable concave function over a polyhedron. The algorithm is of the branch-and-bound type. It finds a globally optimal extreme point solution for this problem in a finite number of steps. One of the major advantages of the algorithm is that the linear programming subproblems solved during the branch-and-bound search each have the same feasible region. We discuss this and other advantages and disadvantages of the algorithm. We also discuss some preliminary computational experience we have had with our computer code for implementing the algorithm. This computational experience involved solving several bilinear programming problems with the code.     

A bounded dual (all-integer) integer programming algorithm with an objective cut

In this article, we describe a new algorithm for solving all-integer, integer programming problems. We generate upper bounds on the decision variables, and use these bounds to create an advanced starting point for a dual all-integer cutting plane algorithm. In addition, we use a constraint derived from the objective function to speed progress toward the optimal solution. Our basic vehicle is the dual all-integer algorithm of Gomory, but we incorporate certain row- and column-selection criteria which partially avoid the problem of dual-degenerate iterations. We present the results of computational testing.     

An algorithm for 0-1 multiple-knapsack problems

The 0-1 multiple-knapsack problem is an extension of the well-known 0-1 knapsack problem. It is a problem of assigning m objects, each having a value and a weight, to n knapsacks in such a way that the total weight in each knapsack is less than its capacity limit and the total value in the knapsacks is maximized. A branch-and-bound algorithm for solving the problem is developed and tested. Branching rules that avoid the search of redundant partial solutions are used in the algorithm. Various bounding techniques, including Lagrangean and surrogate relaxations, are investigated and compared.     

强约束条件下外弹道方程实时解算通用化设计技术

根据基于弹道方程的实时解算算法,解决了强约束条件下非低伸弹种弹道综合系数的统一计算问题,找出低伸弹种弹道综合系数的估计方法,进行了弹道实时解算模型的通用化设计,给出了程序流程并进行了测试.测试结果表明,弹道综合系数的估计比较准确,而解算模型在精度与实时性上均达到满意的程度,具有高度通用化的特点,并且使弹道问题的解算可以完全脱离射表进行.     

Mathematical control theory solution of an interactive accounting flows model

In this paper we have applied the mathematical control theory to the accounting network flows, where the flow rates are constrained by linear inequalities. The optimal control policy is of the “generalized bang-bang” variety which is obtained by solving at each instant in time a linear programming problem whose objective function parameters are determined by the “switching function” which is derived from the Hamiltonian function. The interpretation of the adjoint variables of the control problem and the dual evaluators of the linear programming problem demonstrates an interesting interaction of the cross section phase of the problem, which is characterized by linear programming, and the dynamic phase of the problem, which is characterized by control theory.     

AN ALGORITHM FOR THE SEGREGATED STORAGE PROBLEM

The segregated storage problem involves the optimal distribution of products among compartments with the restriction that only one product may be stored in each compartment. The storage capacity of each compartment, the storage demand for each product, and the linear cost of storing one unit of a product in a given compartment are specified. The problem is reformulated as a large set-packing problem, and a column generation scheme is devised to solve the associated linear programming problem. In case of fractional solutions, a branch and bound procedure is utilized. Computational results are presented.     

线性规划问题新解——改进大M法

借鉴两阶段法的求解思路,在用单纯形法求解线性规划问题时,对大M法进行改进,提出一种新的算法.这种改进后的算法可以有效克服原来两种算法的不足,既能降低理解难度,又能提高算法的效率,保证算法的全局收敛性.     

Dichotomous categorical variable formation in mathematical programming discriminant analysis models

Classification models, whether generated by statistical techniques or mathematical programming (MP) discriminant analysis methods, are often simplified by ad hoc formation of dichotomous categorical variables from the original variables with, for example, a dichotomous variable taking value 1 if the original variable is above a threshold level and 0 otherwise. In this paper an MP discriminant analysis method is developed for forming dichotomous categorical variables in problems with discriminant functions that are monotone in the original variables. For each of the original variables from which dichotomous variables may be formed, a set of possible threshold levels for dichotomous variable formation is defined. An MP model is then used to determine both the threshold level for forming each dichotomous variable and the associated discriminant function coefficient. The proposed MP approach is applied to a published problem and a number of simulated problem sets. It is shown that the discriminant functions in dichotomous categorical variables generated by this new MP approach can in some cases outperform the functions generated by standard MP discriminant analysis models using the original variables. © 2004 Wiley Periodicals, Inc. Naval Research Logistics, 2004.     

The use of dynamic programming methodology for the solution of a class of nonlinear programming problems

This paper presents an application of a method for finding the global solution to a problem in integers with a separable objective function of a very general form. This report shows that there is a relationship between an integer problem with a separable nonlinear objective function and many constraints and a series of nonlinear problems with only a single constraint, each of which can be solved sequentially using dynamic programming. The first solution to any of the individual smaller problems that satisfies the original constraints in addition, will be the optimal solution to the multiply-constrained problem.     

两段探测目标的传感器任务调度问题0-1规划模型及算法

为解决指挥系统控制中的调度困难,研究了一类特殊的传感器资源调度问。主要分析了跟踪目标的探测次数、时间间隔和传感器资源等约束条件。用跟踪目标的重要程度之和作为目标函数,建立了一个0-1规划的数学模型,再利用变换将其转化为0-1线性整数规划模型。利用割平面法求解得出最优调度策略,其能在工作量饱和的情况下合理调度传感器资源。为提高求解速度,提出了对应的模拟退火算法。通过对一些不同规模实例的求解,在资源利用率和算法的求解速度等指标上,与割平面法及遗传算法进行对比分析,验证了模型的有效性和模拟退火算法求解的高效性。     

正则有理Bezier曲线的等距曲线算法

通过利用改进的有理德卡斯特里奥算法求得正则有理ｎ次Ｂｅｚｉｅｒ曲线各点处的切矢,由此得到各点的单位法矢量,应用于求原始曲线的等距曲线,从而巧妙地解决了原始正则有理ｎ次Ｂｅｚｉｅｒ曲线上各点的单位法矢量难求的困难。该方法几何意义明显,算法简洁,实践效果比较好,最后本文给出了两个实例。     

A branch‐and‐bound‐based solution approach for dynamic rerouting of airborne platforms

This article is a sequel to a recent article that appeared in this journal, “An extensible modeling framework for dynamic reassignment and rerouting in cooperative airborne operations” [ 17 ], in which an integer programming formulation to the problem of rescheduling in‐flight assets due to changes in battlespace conditions was presented. The purpose of this article is to present an improved branch‐and‐bound procedure to solve the dynamic resource management problem in a timely fashion, as in‐flight assets must be quickly re‐tasked to respond to the changing environment. To facilitate the rapid generation of attractive updated mission plans, this procedure uses a technique for reducing the solution space, supports branching on multiple decision variables simultaneously, incorporates additional valid cuts to strengthen the minimal network constraints of the original mathematical model, and includes improved objective function bounds. An extensive numerical analysis indicates that the proposed approach significantly outperforms traditional branch‐and‐bound methodologies and is capable of providing improved feasible solutions in a limited time. Although inspired by the dynamic resource management problem in particular, this approach promises to be an effective tool for solving other general types of vehicle routing problems. © 2013 Wiley Periodicals, Inc. Naval Research Logistics, 2013