Erratum to: An abstract model for branching and its application to mixed integer programming

Stabilized sequential quadratic programming (sSQP) methods for nonlinear optimization generate a sequence of iterates with fast local convergence regardless of whether or not the active-constraint gradients are linearly dependent. This paper concerns the local convergence analysis of an sSQP method that uses a line search with a primal-dual augmented Lagrangian merit function to enforce global convergence. The method is provably well-defined and is based on solving a strictly convex quadratic programming subproblem at each iteration. It is shown that the method has superlinear local convergence under assumptions that are no stronger than those required by conventional stabilized SQP methods. The fast local convergence is obtained by allowing a small relaxation of the optimality conditions for the quadratic programming subproblem in the neighborhood of a solution. In the limit, the line search selects the unit step length, which implies that the method does not suffer from the Maratos effect. The analysis indicates that the method has the same strong first- and second-order global convergence properties that have been established for augmented Lagrangian methods, yet is able to transition seamlessly to sSQP with fast local convergence in the neighborhood of a solution. Numerical results on some degenerate problems are reported.     

An integer programming approach for linear programs with probabilistic constraints

Linear programs with joint probabilistic constraints (PCLP) are difficult to solve because the feasible region is not convex. We consider a special case of PCLP in which only the right-hand side is random and this random vector has a finite distribution. We give a mixed-integer programming formulation for this special case and study the relaxation corresponding to a single row of the probabilistic constraint. We obtain two strengthened formulations. As a byproduct of this analysis, we obtain new results for the previously studied mixing set, subject to an additional knapsack inequality. We present computational results which indicate that by using our strengthened formulations, instances that are considerably larger than have been considered before can be solved to optimality.     

Information-based branching schemes for binary linear mixed integer problems

Branching variable selection can greatly affect the effectiveness and efficiency of a branch-and-bound algorithm. Traditional approaches to branching variable selection rely on estimating the effect of the candidate variables on the objective function. We propose an approach which is empowered by exploiting the information contained in a family of fathomed subproblems, collected beforehand from an incomplete branch-and-bound tree. In particular, we use this information to define new branching rules that reduce the risk of incurring inappropriate branchings. We provide computational results that demonstrate the effectiveness of the new branching rules on various benchmark instances.     

A branch-and-cut algorithm for nonconvex quadratic programs with box constraints

We present the implementation of a branch-and-cut algorithm for bound constrained nonconvex quadratic programs. We use a class of inequalities developed in [12] as cutting planes. We present various branching strategies and compare the algorithm to several other methods to demonstrate its effectiveness.Mathematics Subject Classification (2000): 90C26, 90C27, 90C20     

George Dantzig’s contributions to integer programming

This paper reviews George Dantzig’s contributions to integer programming, especially his seminal work with Fulkerson and Johnson on the traveling salesman problem.     

Valid inequalities for problems with additive variable upper bounds

We study the facial structure of a polyhedron associated with the single node relaxation of network flow problems with additive variable upper bounds. This type of structure arises, for example, in production planning problems with setup times and in network certain expansion problems. We derive several classes of valid inequalities for this polyhedron and give conditions under which they are facet–defining. Our computational experience with large network expansion problems indicates that these inequalities are very effective in improving the quality of the linear programming relaxations. Received: April 15, 1999 / Accepted: October 10, 2000?Published online May 18, 2001     

Using diversification,communication and parallelism to solve mixed-integer linear programs

Performance variability of modern mixed-integer programming solvers and possible ways of exploiting this phenomenon present an interesting opportunity in the development of algorithms to solve mixed-integer linear programs (MILPs). We propose a framework using multiple branch-and-bound trees to solve MILPs while allowing them to share information in a parallel execution. We present computational results on instances from MIPLIB 2010 illustrating the benefits of this framework.