A branch and bound algorithm with constraint partitioning for integer goal programming problems

Using constraint partitioning and variable elimination, the authors have recently developed an efficient algorithm for solving linear goal programming problems. However, many goal programs require some or all of the decision variables to be integer valued. This paper shows how the new partitioning algorithm can be extended with a modified branch and bound strategy to solve both pure and mixed type integer goal programming problems. A potential problem in combining the partitioning algorithm and the branch and bound search scheme is presented and resolved.     

Using a Hybrid Genetic-Algorithm/Branch and Bound Approach to Solve Feasibility and Optimization Integer Programming Problems

The satisfiability problem in forms such as maximum satisfiability (MAX-SAT) remains a hard problem. The most successful approaches for solving such problems use a form of systematic tree search. This paper describes the use of a hybrid algorithm, combining genetic algorithms and integer programming branch and bound approaches, to solve MAX-SAT problems. Such problems are formulated as integer programs and solved by a hybrid algorithm implemented within standard mathematical programming software. Computational testing of the algorithm, which mixes heuristic and exact approaches, is described.     

Zero-one integer programs with few constraints —Efficient branch and bound algorithms

The 0–1 integer programming problem and its special case, the 0–1 knapsack problem are frequently encountered in modeling various design and decision making processes. This paper is a follow-up paper to [4] and deals with the development of an effective solution procedure for 0–1 integer programs with few constraints. Detailed computational experiments are carried out and different separation, branching and bounding rules are compared using an experimental branch and bound code. An efficient branch and bound procedure is developed, tested and compared with previously developed optimal algorithms. It is suggested that this procedure may also be used as a heuristic method for large problems by early termination of the tree search. This scheme is tested and found to be very effective.     

Bus driver duty optimization using an integer programming and evolutionary hybrid algorithm

This paper describes the details of a successful application where an integer programming and evolutionary hybrid algorithm was used to solve a bus driver duty optimization problem. The task is NP-hard, therefore theoretically optimal solutions can only be calculated for very small problem instances. Our aim is to obtain solutions of good quality within reasonable time limits. We first applied an integer programming approach to a set partitioning problem. The model was solved with a column generation algorithm in a branch and bound scheme. In order to solve larger real-life problems, we have combined the integer programming method with a greedy 1+1 steady state evolutionary algorithm. The resulting hybrid algorithm was capable of providing near-optimal solutions within reasonable timescales to larger instances of the bus driver scheduling problem. We present the results and running times of our algorithm in detail, as well as possible directions of future improvements.     

Polyhedral annexation in mixed integer and combinatorial programming

Polyhedral annexation is a new approach for generating all valid inequalities in mixed integer and combinatorial programming. These include the facets of the convex hull of feasible integer solutions. The approach is capable of exploiting the characteristics of the feasible solution space in regions both “adjacent to” and “distant from” the linear programming vertex without resorting to specialized notions of group theory, convex analysis or projective geometry. The approach also provides new ways for exploiting the “branching inequalities” of branch and bound.     

A parallel integer linear programming algorithm

The solution of large scale integer linear programming models is generally dependent, in some way, upon the branch and bound technique, which can be quite time consuming. This paper describes a parallel branch and bound algorithm which achieves super linear efficiency in solving integer linear programming models on a multiprocessor computer. The algorithm is used to solve the Haldi and IBM test problems as well as a system design model.     

Multicriteria integer programming: A (hybrid) dynamic programming recursive approach

Dynamic programming recursive equations are used to develop a procedure to obtain the set of efficient solutions to the multicriteria integer linear programming problem. An alternate method is produced by combining this procedure with branch and bound rules. Computational results are reported.     

A problem expanding parametric programming method for solving the job shop scheduling problem

A new zero-one integer programming model for the job shop scheduling problem with minimum makespan criterion is presented. The algorithm consists of two parts: (a) a branch and bound parametric linear programming code for solving the job shop problem with fixed completion time; (b) a problem expanding algorithm for finding the optimal completion time. Computational experience for problems having up to thirty-six operations is presented. The largest problem solved was limited by memory space, not computation time. Efforts are under way to improve the efficiency of the algorithm and to reduce its memory requirements.This report was prepared as part of the activities of the Management Sciences Research Group, Carnegie-Mellon University, under Contract No. N00014-82-K-0329 NR 047-048 with the U.S. Office of Naval Research. Reproduction in whole or in part is permitted for any purpose of the U.S. Government.     

DC programming approaches for discrete portfolio optimization under concave transaction costs

The paper investigates DC programming and DCA for both modeling discrete portfolio optimization under concave transaction costs as DC programs, and their solution. DC reformulations are established by using penalty techniques in DC programming. A suitable global optimization branch and bound technique is also developed where a DC relaxation technique is used for lower bounding. Numerical simulations are reported that show the efficiency of DCA and the globality of its computed solutions, compared to standard algorithms for nonconvex nonlinear integer programs.     

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.     

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 simple,all primal branch and bound approach to pure and mixed integer binary programs

Many branch and bound procedures for integer programming employ linear programming to obtain bound information. Nodes in the tree structure are defined by explicitly changing bounds on certain variables and/or adding one or more constraints to the parent LP; thus, primal feasibility is destroyed. The design and analysis of the resulting tree structure requires that basis information be stored for each node and that feasibility restoring pivots be used to obtain the node bound. In turn, this may require the introduction of artificial variables and/or dual simplex pivots.This paper describes a simple procedure for branch and bound that does not destroy primal feasibility. Moreover, the information required to be stored to define the node problems is minimal.     

Zero-one integer programs with few constraints —Lower bounding theory

The zero-one integer programming problem and its special case, the multiconstraint knapsack problem frequently appear as subproblems in many combinatorial optimization problems. We present several methods for computing lower bounds on the optimal solution of the zero-one integer programming problem. They include Lagrangean, surrogate and composite relaxations. New heuristic procedures are suggested for determining good surrogate multipliers. Based on theoretical results and extensive computational testing, it is shown that for zero-one integer problems with few constraints surrogate relaxation is a viable alternative to the commonly used Lagrangean and linear programming relaxations. These results are used in a follow up paper to develop an efficient branch and bound algorithm for solving zero-one integer programming problems.     

整数规划的一类填充函数算法

填充函数算法是求解连续总体优化问题的一类有效算法。本文改造[1]的填充函数算法使之适于直接求解整数规划问题。首先,给出整数规划问题的离散局部极小解的定义,并设计找离散局部极小解的领域搜索算法。其次,构造整数规划问题的填充函数算法。该方法通过寻找填充函数的离散局部极小解以期找到整数规划问题的比当前离散局部极小解好的解。本文的算法是直接法,数值试验表明算法是有效的。     

切割定界与整数分枝结合求解整数线性规划

把一种改进的割平面方法和分枝定界的思想结合起来求解整数线性规划 ( ILP)问题 .它利用目标函数等值面的移动来切去相应 ( LP)的可行域中含其非整数最优解但不含 ( ILP)可行解的“无用部分”,并将对应的目标函数值作为 ( ILP)目标最优值的一个上界 ;最后 ,通过 ( LP)最优解中非整数基变量的整数分枝来获得整数线性规划的最优解 .     

Unboundedness in Integer and Discrete Programming L.P. Relaxations

Commercial branch and bound codes for solving the general mixed integer linear programming problem commence by solving the linear programming relaxation of the submitted problem, terminating if the relaxation is unbounded. It is assumed that the submitted problem is either unbounded or has no feasible solutions. It is shown that the assumption is correct for all integer programming problems which can be submitted to the currently available codes (though counter examples which cannot be so submitted are given), but that the assumption is generally incorrect for discrete linear programming problems (using for example the special ordered set construct). Sufficient conditions on formulations to ensure its correctness are given. One possible formulation approach, applicable to special ordered set situations, is discussed.     

Norm bounds and underestimators for unconstrained polynomial integer minimization

We consider the problem of minimizing a polynomial function over the integer lattice. Though impossible in general, we use a known sufficient condition for the existence of continuous minimizers to guarantee the existence of integer minimizers as well. In case this condition holds, we use sos programming to compute the radius of a p-norm ball which contains all integer minimizers. We prove that this radius is smaller than the radius known from the literature. Our numerical results show that the number of potentially optimal solutions is reduced by several orders of magnitude. Furthermore, we derive a new class of underestimators of the polynomial function. Using a Stellensatz from real algebraic geometry and again sos programming, we optimize over this class to get a strong lower bound on the integer minimum. Also our lower bounds are evaluated experimentally. They show a good performance, in particular within a branch and bound framework.     

整数规划的广义填充函数算法

文[9,10]设计了直接求整数规划问题近似解的填充函数算法,但其所利用的文[2,3]的填充函数均带有参数,需要在算法过程中逐步调节。本文建立整数规划的广义填充函数的定义,说明了文[9,10]所利用的填充函数是整数规划问题的广义填充函数,并构造了一类不带参数的广义填充函数。进而本文设计了整数规划的一类不带参数的广义填充函数算法,数值试验表明算法是有效的。     

An Improved Branch & Bound Method for the Uncapacitated Competitive Location Problem

In this paper, the problem of locating new facilities in a competitive environment is considered. The problem is formulated as the firm expected profit maximization and a set of nodes is selected in a graph representing the geographical zone. Profit depends on fixed and deterministic location costs and, since customers are independent decision-makers, on the expected market share. The problem is an instance of nonlinear integer programming, because the objective function is concave and submodular. Due to this complexity a branch & bound method is developed for solving small size problems (that is, when the number of nodes is less than 50), while a heuristic is necessary for larger problems. The branch & bound is called data-correcting method, while the approximate solutions are obtained using the heuristic-concentration method.     

A Multi-Stage Stochastic Integer Programming Approach for Capacity Expansion under Uncertainty

This paper addresses a multi-period investment model for capacity expansion in an uncertain environment. Using a scenario tree approach to model the evolution of uncertain demand and cost parameters, and fixed-charge cost functions to model the economies of scale in expansion costs, we develop a multi-stage stochastic integer programming formulation for the problem. A reformulation of the problem is proposed using variable disaggregation to exploit the lot-sizing substructure of the problem. The reformulation significantly reduces the LP relaxation gap of this large scale integer program. A heuristic scheme is presented to perturb the LP relaxation solutions to produce good quality integer solutions. Finally, we outline a branch and bound algorithm that makes use of the reformulation strategy as a lower bounding scheme, and the heuristic as an upper bounding scheme, to solve the problem to global optimality. Our preliminary computational results indicate that the proposed strategy has significant advantages over straightforward use of commercial solvers.