The discussion below, from Karen Aardal and Arjen K. Lenstra, represents correction of an error made in their paper, Aardal, Karen, Arjen K. Lenstra. 2004. Hard equality constrained integer knapsacks. Math. Oper. Res. 29(3) 724-738.

We consider the following integer feasibility problem: “Given positive integer numbers a 0, a 1,..., a n, with gcd(a 1,..., a n) = 1 and a = (a 1,..., a n), does there exist a nonnegative integer vector x satisfying ax = a 0?” Some instances of this type have been found to be extremely hard to solve by standard methods such as branch-and-bound, even if the number of variables is as small as ten. We observe that not only the sizes of the numbers a 0, a 1,..., a n, but also their structure, have a large impact on the difficulty of the instances. Moreover, we demonstrate that the characteristics that make the instances so difficult to solve by branch-and-bound make the solution of a certain reformulation of the problem almost trivial. We accompany our results by a small computational study.

We develop an algorithm for solving a system of diophantine equations with lower and upper bounds on the variables. The algorithm is based on lattice basis reduction. It first finds a short vector satisfying the system of diophantine equations, and a set of vectors belonging to the null- space of the constraint matrix. Due to basis reduction, all these vectors are relatively short. The next step is to branch on linear combinations of the null-space vectors, which either yields a vector that satisfies the bound constraints or provides a proof that no such vector exists. The research was motivated by the need for solving constrained diophantine equations as subproblems when designing integrated circuits for video signal processing. Our algorithm is tested with good results on real-life data, and on instances from the literature.

This paper reports on the factorization of the 512-bit number RSA-155 by the Number Field Sieve factoring method (NFS) and discusses the implications for RSA.

At the IPCO VI conference Cornuéjols and Dawande proposed a set of 0– 1 linear programming instances that proved to be very hard to solve by traditional methods, and in particular by linear programming based branch-and-bound. They offered these market split instances as a challenge to the integer programming community. The market split problem can be formulated as a system of linear diophantine equations in 0–1 variables.

In our study we use the algorithm of (1998) based on lattice basis reduction. This algorithm is not restricted to deal with market split instances only but is a general method for solving systems of linear diophantine equations with bounds on the variables.

We show computational results from solving both feasibility and optimization versions of the market split instances with up to 7 equations and 60 variables, and discuss various branching strategies and their effect on the number of nodes enumerated. To our knowledge, the largest feasibility and optimization instances solved before have 6 equations and 50 variables, and 4 equations and 30 variables respectively.

We also present a probabilistic analysis describing how to compute the probability of generating infeasible market split instances. The formula used by Cornuéjols and Dawande tends to produce relatively many feasible instances for sizes larger than 5 equations and 40 variables.

We develop an algorithm for solving a linear diophantine equation with lower and upper bounds on the variables. The algorithm is based on lattice basis reduction, and first finds short vectors satisfying the diophantine equation. The next step is to branch on linear combi- nations of these vectors, which either yields a vector that satisfies the bound constraints or provides a proof that no such vector exists. The research was motivated by the need for solving constrained linear dio- phantine equations as subproblems when designing integrated circuits for video signal processing. Our algorithm is tested with good result on real-life data.