Parameterisation algorithms for the integer linear programs in binary variables

In this paper we consider the integer programmiing problem: minimize z(x) = c · x subject to Ax?b,x binary.Roodman appended the objective function z(x) to the body of the constraints and presented a modified version of the Balas additive algorithm by which each fathomed partial solution is attributed to the constraint which caused the fathoming. Exploiting this information, he conducted (a) ranging analysis, i.e. calculating bounds on the values of the parameters which leave the original optimal solution unchanged, and (b) parameter change analysis, i.e. determining new optimal solutions (if any) for revised values of the parameters outside the ranging bounds.We extend Roodman's results and construct parametric functions of the following form. Let Σ be any parameter of c or b or A, and replace Σ by Σ(λ) = Σ + λ. Then, holding every other parameter of the program fixed, and varying λ in the set of real numbers we construct the parametric function $\text{z}{}^1\text{(Σ(λ))}$ which matches non-overlapping intervals of λ with optimal solutions. This replaces by exact bounds in the linear programming sense, the bounds underestimated by Roodman's ranging analysis. It also determines optimal solutions for any values of λ, rather than for a revised set of values. Finally some results of computational experience are presented.     

Modern factorization methods

In this expository paper the progress in factorization of large integers since the introduction of computers is reported. Thanks to theoretical advances and refinements, as well as to more powerful computers, the practical limit of integers possible to factor has been raised considerably during the past 20 years. The present practical limit is around 10⁷⁵ if supercomputers are used and if much computer time is available.     

Sequential pairing of mixed integer inequalities

We investigate a scheme, called pairing, for generating new valid inequalities for mixed integer programs by taking pairwise combinations of existing valid inequalities. The pairing scheme essentially produces a split cut corresponding to a specific disjunction, and can also be derived through the mixed integer rounding procedure. The scheme is in general sequence-dependent and therefore leads to an exponential number of inequalities. For some important cases, we identify combination sequences that lead to a manageable set of non-dominated inequalities. We illustrate the framework for some deterministic and stochastic integer programs and we present computational results showing the efficiency of adding the new generated inequalities as cuts.     

Assignment problems: A golden anniversary survey

Having reached the 50th (golden) anniversary of the publication of Kuhn’s seminal article on the solution of the classic assignment problem, it seems useful to take a look at the variety of models to which it has given birth. This paper is a limited survey of what appear to be the most useful of the variations of the assignment problem that have appeared in the literature over the past 50 years. The intention here is not to identify every such paper (of which there have been hundreds) nor to identify the best solution procedure for each variation. Rather, the intention is to identify what these variations are and what they are called so as to make it easier for a researcher trying to develop some variation of the assignment problem for a particular application to find the relevant literature.     

Computing robust basestock levels

This paper considers how to optimally set the basestock level for a single buffer when demand is uncertain, in a robust framework. We present a family of algorithms based on decomposition that scale well to problems with hundreds of time periods, and theoretical results on more general models.     

Lattice based extended formulations for integer linear equality systems

We study different extended formulations for the set with in order to tackle the feasibility problem for the set Pursuing the work of Aardal, Lenstra et al. using the reformulation , our aim is to derive reformulations of the form with 0  ≤  s ≤ n − m where preferably all the coefficients of P are small compared to the coefficients of A and T. In such cases the new variables μ appear to be good branching directions, and in certain circumstances permit one to deduce rapidly that the instance is infeasible. We give a polynomial time algorithm for identifying such P, T if possible, and for the case that A has one row a we analyze the reformulation when s = 1, that is, one μ-variable is introduced. In particular, we determine the integer width of the extended formulations in the direction of the μ-variable, and derive a lower bound on the Frobenius number of a. We conclude with some preliminary tests to see if the reformulations are effective when the number s of additional constraints and variables is limited. This work was partly carried out within the framework of ADONET, a European network in Algorithmic Discrete Optimization, contract no. MRTN-CT-2003-504438. The first author is financed in part by the Dutch BSIK/BRICKS project. The research was carried out in part while the second author visited CWI, Amsterdam with the support of the NWO visitor grant number B 61-556.     

A polynomial algorithm for integer programming covering problems satisfying the integer round-up property

LetA be a non-negative matrix with integer entries and no zero column. The integer round-up property holds forA if for every integral vectorw the optimum objective value of the generalized covering problem min{1y: yA w, y 0 integer} is obtained by rounding up to the nearest integer the optimum objective value of the corresponding linear program. A polynomial time algorithm is presented that does the following: given any generalized covering problem with constraint matrixA and right hand side vectorw, the algorithm either finds an optimum solution vector for the covering problem or else it reveals that matrixA does not have the integer round-up property.     

Sigma function solution of the initial value problem for Somos 5 sequences

The Somos 5 sequences are a family of sequences defined by a fifth order bilinear recurrence relation with constant coefficients. For particular choices of coefficients and initial data, integer sequences arise. By making the connection with a second order nonlinear mapping with a first integral, we prove that the two subsequences of odd/even index terms each satisfy a Somos 4 (fourth order) recurrence. This leads directly to the explicit solution of the initial value problem for the Somos 5 sequences in terms of the Weierstrass sigma function for an associated elliptic curve.

     

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.     

Smoothed analysis of integer programming

We present a probabilistic analysis of integer linear programs (ILPs). More specifically, we study ILPs in a so-called smoothed analysis in which it is assumed that first an adversary specifies the coefficients of an integer program and then (some of) these coefficients are randomly perturbed, e.g., using a Gaussian or a uniform distribution with small standard deviation. In this probabilistic model, we investigate structural properties of ILPs and apply them to the analysis of algorithms. For example, we prove a lower bound on the slack of the optimal solution. As a result of our analysis, we are able to specify the smoothed complexity of classes of ILPs in terms of their worst case complexity. This way, we obtain polynomial smoothed complexity for packing and covering problems with any fixed number of constraints. Previous results of this kind were restricted to the case of binary programs.      

Cutting-plane proofs in polynomial space

Following Chvátal, cutting planes may be viewed as a proof system for establishing that a given system of linear inequalities has no integral solution. We show that such proofs may be carried out in polynomial workspace.Research supported by Sonderforschungsbereich 303 (DFG), Institut für Operations Research, Universität Bonn, FR Germany and by NSF grant ECS-8611841.     

The nurse rostering problem: A critical appraisal of the problem structure

This paper is concerned with the problem of nurse rostering within hospitals. We analyse a class of four benchmark instances from the nurse rostering literature to provide insight into the nature of the problem. By highlighting the structure of the problem we are able to reduce the relevant solution space. A mixed integer linear programme is then able to find optimal solutions to all four instances of this class of benchmark problems, each within half an hour. Our second contribution is to extend current mathematical approaches to nurse rostering to take better account of the practical considerations. We provide a methodology for handling rostering constraints and preferences arising from the continuity from one scheduling period to the next.     

The splitting of variables and constraints in the formulation of integer programming models

The splitting of variables in an integer programming model into the sum of other variables can allow the constraints to be disaggregated, leading to a more constrained (tighter) linear programming relaxation. Well known examples of such reformulations are quoted from the literature. They can be viewed as instances of some general methods of performing such reformulations, namely disjunctive formulations, partial network reformulations and a method based on the introduction of auxiliary variables.     

Constrained integer linear fractional programming problem

An integer linear fractional programming problem, whose integer solution is required to satisfy any h out of given n sets of constraints has been discussed in this paper. Method for ranking and scanning all integer points has also been developed and a numerical illustration is included in support of theory.     

Square form factorization

We present a detailed analysis of SQUFOF, Daniel Shanks' Square Form Factorization algorithm. We give the average time and space requirements for SQUFOF. We analyze the effect of multipliers, either used for a single factorization or when racing the algorithm in parallel.

     

On a class of extremal problems in statistics

Let m denote the infimum of the Integral of a function q w r t all probability measures with given marginals. The determination of m is of interest for a series of stochastic problems. In the present paper we prove a duality theorem for the determination of m and give some examples for its application. We consider especially the problem of extremal variance of sums of random variables and prove a theorem for the existence of random variables with given marginal distributions, such that their sum has variance zero.     

Solving integer programs with a few important binary gub constraints

During a branch and bound search of an integer program, decisions have to be taken about which subproblem to solve next and which variable or special ordered set to branch on. Both these decisions are usually based on some sort of estimated change in the objective caused by different branching. When the next subproblem is chosen, the estimated change in the objective is often found by summing the change caused by changing all integer variables with non-integer values, as if they were independent. For special ordered sets the estimation is done for each set as a whole. The purpose of this paper is to report some results from trying to do a simultaneous estimation for all the variables in a binary gub constraint. By this, the analysed problems contain one or a few constraints saying that the sum ofn binary variables should be equal tom (<n).I am grateful to Scicon Ltd. for giving me access to the SCICONIC source code.