Using the analytic center in the feasibility pump

The feasibility pump (FP) has proved to be a successful heuristic for finding feasible solutions of mixed integer linear problems. Briefly, FP alternates between two sequences of points: one of feasible solutions for the relaxed problem, and another of integer points. This short paper extends FP, such that the integer point is obtained by rounding a point on the (feasible) segment between the computed feasible point and the analytic center for the relaxed linear problem.     

Feasibility pump 2.0

Finding a feasible solution of a given mixed-integer programming (MIP) model is a very important ${\mathcal{NP}}$ -complete problem that can be extremely hard in practice. Feasibility Pump (FP) is a heuristic scheme for finding a feasible solution to general MIPs that can be viewed as a clever way to round a sequence of fractional solutions of the LP relaxation, until a feasible one is eventually found. In this paper we study the effect of replacing the original rounding function (which is fast and simple, but somehow blind) with more clever rounding heuristics. In particular, we investigate the use of a diving-like procedure based on rounding and constraint propagation—a basic tool in Constraint Programming. Extensive computational results on binary and general integer MIPs from the literature show that the new approach produces a substantial improvement of the FP success rate, without slowing-down the method and with a significantly better quality of the feasible solutions found.     

Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants

Lift-and-project cuts for mixed integer programs (MIP), derived from a disjunction on an integer-constrained fractional variable, were originally (Balas et al. in Math program 58:295–324, 1993) generated by solving a higher-dimensional cut generating linear program (CGLP). Later, a correspondence established (Balas and Perregaard in Math program 94:221–245, 2003) between basic feasible solutions to the CGLP and basic (not necessarily feasible) solutions to the linear programming relaxation LP of the MIP, has made it possible to mimic the process of solving the CGLP through certain pivots in the LP tableau guaranteed to improve the CGLP objective function. This has also led to an alternative interpretation of lift-and-project (L&P) cuts, as mixed integer Gomory cuts from various (in general neither primal nor dual feasible) LP tableaus, guaranteed to be stronger than the one from the optimal tableau. In this paper we analyze the relationship between a pivot in the LP tableau and the (unique) corresponding block pivot (sequence of pivots) in the CGLP tableau. Namely, we show how a single pivot in the LP defines a sequence (potentially as long as the number of variables) of pivots in the CGLP, and we identify this sequence. Also, we give a new procedure for finding in a given LP tableau a pivot that produces the maximum improvement in the CGLP objective (which measures the amount of violation of the resulting cut by the current LP solution). Further, we introduce a procedure called iterative disjunctive modularization. In the standard procedure, pivoting in the LP tableau optimizes the multipliers with which the inequalities on each side of the disjunction are weighted in the resulting cut. Once this solution has been obtained, a strengthening step is applied that uses the integrality constraints (if any) on the variables on each side of the disjunction to improve the cut coefficients by choosing optimal values for the elements of a certain monoid. Iterative disjunctive modularization is a procedure for approximating the simultaneous optimization of both the continuous multipliers and the integer elements of the monoid. All this is discussed in the context of a CGLP with a more general normalization constraint than the standard one used in (Balas and Perregaard in Math program 94:221–245, 2003), and the expressions that describe the above mentioned correspondence are accordingly generalized. Finally, we summarize our extensive computational experience with the above procedures.     

A branch and bound algorithm for locating input and output points of departments on the block layout

We consider the problem of locating input and output (I/O) points of each department for a given layout. The objective of the problem is to minimise the total distance of material flows between the I/O points. Here, distances between the I/O points are computed as the lengths of the shortest path (not the rectilinear distances) between the I/O points. We developed a procedure to eliminate dominated candidate positions of I/O points that do not need to be considered. With this procedure, a large number of dominated candidate positions can be eliminated. A linear programming (LP) model for minimising the total rectilinear distance of flows is used to obtain a lower bound. Using the elimination procedure and the LP model, a branch and bound algorithm is developed to find an optimal location of the I/O points. Results from computational experiments show that the suggested algorithm finds optimal solutions in a very short time even for large-sized problems.     

An interior point algorithm to solve computationally difficult set covering problems

We present an interior point approach to the zero–one integer programming feasibility problem based on the minimization of a nonconvex potential function. Given a polytope defined by a set of linear inequalities, this procedure generates a sequence of strict interior points of this polytope, such that each consecutive point reduces the value of the potential function. An integer solution (not necessarily feasible) is generated at each iteration by a rounding scheme. The direction used to determine the new iterate is computed by solving a nonconvex quadratic program on an ellipsoid. We illustrate the approach by considering a class of difficult set covering problems that arise from computing the 1-width of the incidence matrix of Steiner triple systems.     

ZI round,a MIP rounding heuristic

We introduce a new pure integer rounding heuristic, ZI Round, and compare this heuristic to recent extremely fast pure integer rounding heuristic Simple Rounding. Simple Rounding was introduced in the non-commercial code SCIP. ZI Round attempts to round each fractional variable while using row slacks to maintain primal feasibility. We use the MIPLIB 2003 library for the test set. The average time in our run per instance for both Simple Rounding and ZI Round was 0.8 milliseconds, but ZI Round found more feasible solutions with a the same or better objective value. Also the average time to solve the lp relaxation per instance was 2.2 seconds, so these two rounding heuristics are several magnitudes faster than other heuristics which must use the lp solver, including diving heuristics. We also show that ZI Round performs well on a set covering class and a railway crew scheduling class.     

Converging upon basic feasible solutions through Dantzig–Wolfe decomposition

We derive an important property for solving large-scale integer programs by examining the master problem in Dantzig–Wolfe decomposition. In particular, we prove that if a linear program can be divided into subproblems with affinely independent corner points, then there is a direct mapping between basic feasible solutions in the master and original problems. This has implications for integer programs where the feasible region has integer corner points, ensuring that integer solutions to the original problem will be found even through the decomposition approach. An application to air traffic flow scheduling, which motivated this result, is highlighted.     

Improved integer programming bounds using intersections of corner polyhedra

Consider the relaxation of an integer programming (IP) problem in which the feasible region is replaced by the intersection of the linear programming (LP) feasible region and the corner polyhedron for a particular LP basis. Recently a primal-dual ascent algorithm has been given for solving this relaxation. Given an optimal solution of this relaxation, we state criteria for selecting a new LP basis for which the associated relaxation is stronger. These criteria may be successively applied to obtain either an optimal IP solution or a lower bound on the cost of such a solution. Conditions are given for equality of the convex hull of feasible IP solutions and the intersection of all corner polyhedra.     

On degeneracy in enumeration

In the case of degeneracy in an LP-formulation, there is not a one-to-one correspondence between extreme points and feasible bases. If the task is to find thek best extreme points in the set of feasible solutions to an LP, this lack of correspondence has a certain importance, since methods based on the Simplex Algorithm are oriented towards feasible bases instead of the relevant extreme points. We therefore present an easily implementable method to avoid this problem.     

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

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

An Algorithm for Selecting Quantity Discounts from Realistic Schedules

Consideration of bounds, discontinuities and the integrality of decision variables is often helpful for responding to many practical requirements. Using the case of quantity discounting as an example, it is shown why the above considerations add realism to a model, and how they may be incorporated in the solution procedure. The bounds on the order quantity are fulfilled by establishing suitable stopping rules, while gaps in order quantities are resolved by modifying the input data. As for integrality, a result is established which shows that the feasible points for the integer optimum can be obtained by suitably rounding those for the continuous optimum. A comprehensive algorithm containing these features is proposed, and analytical proofs of the results are included.     

A Posteriori Error Estimates in Time-Domain Decomposition of Final Value Optimal Control of the Acoustic Wave Equation

We consider a boundary optimal control problem for the acoustic wave equation with a final value cost criterion. A time-domain decomposition procedure for the corresponding optimality system is introduced, which leads to a sequence of uncoupled optimality systems of local-in-time optimal control problems. The process is inherently parallel and is suitable for real-time control applications. Convergence of the local solutions and controls to the global ones was established in an earlier publication. In this paper, a posteriori error estimates of the difference between the local solutions and the global one are obtained in terms of the mismatch of the n th iterates, or of successive iterates, across the time-domain break points.     

When is rounding allowed in integer nonlinear optimization?

In this paper we consider nonlinear integer optimization problems. Nonlinear integer programming has mainly been studied for special classes, such as convex and concave objective functions and polyhedral constraints. In this paper we follow an other approach which is not based on convexity or concavity. Studying geometric properties of the level sets and the feasible region, we identify cases in which an integer minimizer of a nonlinear program can be found by rounding (up or down) the coordinates of a solution to its continuous relaxation. We call this property rounding property. If it is satisfied, it enables us (for fixed dimension) to solve an integer programming problem in the same time complexity as its continuous relaxation. We also investigate the strong rounding property which allows rounding a solution to the continuous relaxation to the next integer solution and in turn yields that the integer version can be solved in the same time complexity as its continuous relaxation for arbitrary dimensions.     

Improved optimization modelling for the closest string and related problems

We present a new integer linear programming model for the closest string problem. This model requires considerably less variables and constraints than the popular binary linear programming model used for this purpose. Due to the reduced size it is easier to handle rounding errors when an LP relaxation technique is used to solve the problem.     

Branching on hyperplane methods for mixed integer linear and convex programming using adjoint lattices

We present branching-on-hyperplane methods for solving mixed integer linear and mixed integer convex programs. In particular, we formulate the problem of finding a good branching hyperplane using a novel concept of adjoint lattice. We also reformulate the problem of rounding a continuous solution to a mixed integer solution. A worst case complexity of a Lenstra-type algorithm is established using an approximate log-barrier center to obtain an ellipsoidal rounding of the feasible set. The results for the mixed integer convex programming also establish a complexity result for the mixed integer second order cone programming and mixed integer semidefinite programming feasibility problems as a special case. Our results motivate an alternative reformulation technique and a branching heuristic using a generalized (e.g., ellipsoidal) norm reduced basis available at the root node.     

Rounding Procedures for the Discrete Version of the Capacitated Economic Order Quantity Problem

The capacitated Economic Order Quantity problem (capacitated EOQ) is a well-known problem where products have to be shipped between two points with a vehicle of given capacity. Each shipment has a fixed cost, independent of the shipped quantity, and an inventory cost is generated in the two points. The problem consists in finding the optimal time between consecutive shipments, which minimizes the total cost. The problem is a capacitated variant of the EOQ problem and has a closed form solution. Since such solution is often irrational, it is often rounded to an integer value. In this paper we investigate the errors which are generated by rounding procedures to integer and powers-of-two values. We show that, although in the worst case a tight general relative error of 2 is generated by all the considered rounding procedures, the procedure which rounds to the best between the lower and upper values (integer or powers-of-two) has a performance of $\frac{1}{2}$ ( $\sqrt 2 + 1/\sqrt 2 $ )≈1.06 on classes of instances of high practical relevance.     

Computing approximate solutions for convex conic systems of constraints

We propose a way to reformulate a conic system of constraints as an optimization problem. When an appropriate interior-point method (ipm) is applied to the reformulation, the ipm iterates yield backward-approximate solutions, that is, solutions for nearby conic systems. In addition, once the number of ipm iterations passes a certain threshold, the ipm iterates yield forward-approximate solutions, that is, points close to an exact solution of the original conic system. The threshold is proportional to the reciprocal of distance to ill-posedness of the original conic system.?The condition numbers of the linear equations encountered when applying an ipm influence the computational cost at each iteration. We show that for the reformulation, the condition numbers of the linear equations are uniformly bounded both when computing reasonably-accurate backward-approximate solutions to arbitrary conic systems and when computing forward-approximate solutions to well-conditioned conic systems. Received: July 11, 1997 / Accepted: August 18, 1999?Published online March 15, 2000     

A continuous approch for globally solving linearly constrained quadratic

In a continuous approach we propose an efficient method for globally solving linearly constrained quadratic zero-one programming considered as a d.c. (difference of onvex functions) program. A combination of the d.c. optimization algorithm (DCA) which has a finite convergence, and the branch-and-bound scheme was studied. We use rectangular bisection in the branching procedure while the bounding one proceeded by applying d.c.algorithms from a current best feasible point (for the upper bound) and by minimizing a well tightened convex underestimation of the objective function on the current subdivided domain (for the lower bound). DCA generates a sequence of points in the vertex set of a new polytope containing the feasible domain of the problem being considered. Moreover if an iterate is integral then all following iterates are integral too.Our combined algorithm converges so quite often to an integer approximate solution.Finally, we present computational results of several test problems with up to 1800

variables which prove the efficiency of our method, in particular, for linear zero-one programming     

Integer programming approaches to the travelling salesman problem

The availability of an LP routine where we can add constraints and reoptimize, makes it possible to adopt an integer programming approach to the travelling-salesman problem.Starting with some of the constraints that define the problem we use either a branching process or a cutting planes routine to eliminate fractional solutions. We then test the resulting integer solution against feasibility and if necessary we generate the violated constraints and reoptimize until a genuine feasible solution is achieved.Usually only a small number of the omitted constraints is generated.The generality of the method and the modest solution times achieved leads us to believe that such an LP approach to other combinatorial problems deserves further consideration.     

A new rounding procedure for the assignment problem with applications to dense graph arrangement problems

We present a randomized procedure for rounding fractional perfect matchings to (integral) matchings. If the original fractional matching satisfies any linear inequality, then with high probability, the new matching satisfies that linear inequality in an approximate sense. This extends the well-known LP rounding procedure of Raghavan and Thompson, which is usually used to round fractional solutions of linear programs.?We use our rounding procedure to design an additive approximation algorithm to the Quadratic Assignment Problem. The approximation error of the algorithm is εn ² and it runs in n ^{O (log n /ε2)} time.?We also describe Polynomial Time Approximation Schemes (PTASs) for dense subcases of many well-known NP-hard arrangement problems, including MINIMUM LINEAR ARRANGEMENT, MINIMUM CUT LINEAR ARRANGEMENT, MAXIMUM ACYCLIC SUBGRAPH, and BETWEENNESS. Received: December 12, 1999 / Accepted: October 25, 2001?Published online February 14, 2002