The b-hull of an integer program

Given a linear integer program: max{cx:Ax=b, x≥0 and integer},A rational, it is known that it can be solved in theory for all values of c, either by testing a finite number of solutions for optimality, or by adding a finite number of valid inequalities, each generated from a superadditive function, and solving the resulting linear program.The main result of this paper is to show that (analogously) the integer program can be solved for all values of b, either by testing a finite number of solutions for feasibility and optimality, or by adding a finite number of valid inequalities, each generated from a superadditive function, and solving the resulting linear program.     

A remark on condensing mappings

Greenberg [4] described an interesting procedure based on dynamic programming for generating the knapsack function Φ(s) = max{cx: ax ? s, x ? 0, integer} for all arguments s ? b, where c, a, and x are vectors with nonnegative integer components and b is a positive integer. The principle search effort can be associated with finding the minimum of a string D of k elements. It is shown here that a rank ordering of the components of a yields sequences D such that a search for the minimum in D over the first m elements is sufficient. In general, m is smaller than k and the calculation of Φ is accelerated. Extensions of the basic procedure to the case where the components of x have upper-bounds is also described.     

An FPTAS for minimizing the product of two non-negative linear cost functions

We consider a quadratic programming (QP) problem (Π) of the form min x ^T C x subject to Ax ≥ b, x ≥ 0 where \({C\in {\mathbb R}^{n \times n}_+, {\rm rank}(C)=1}\) and \({A\in {\mathbb R}^{m \times n}, b\in {\mathbb R}^m}\) . We present an fully polynomial time approximation scheme (FPTAS) for this problem by reformulating the QP (Π) as a parameterized LP and “rounding” the optimal solution. Furthermore, our algorithm returns an extreme point solution of the polytope. Therefore, our results apply directly to 0–1 problems for which the convex hull of feasible integer solutions is known such as spanning tree, matchings and sub-modular flows. They also apply to problems for which the convex hull of the dominant of the feasible integer solutions is known such as s, t-shortest paths and s, t-min-cuts. For the above discrete problems, the quadratic program Π models the problem of obtaining an integer solution that minimizes the product of two linear non-negative cost functions.     

On the existence of Hadamard matrices

Given any natural number q > 3 we show there exists an integer t ? [2log₂(q ? 3)] such that an Hadamard matrix exists for every order 2^sq where s > t. The Hadamard conjecture is that s = 2.This means that for each q there is a finite number of orders 2^υq for which an Hadamard matrix is not known. This is the first time such a statement could be made for arbitrary q.In particular it is already known that an Hadamard matrix exists for each 2^sq where if q = 2^m ? 1 then s ? m, if q = 2^m + 3 (a prime power) then s ? m, if q = 2^m + 1 (a prime power) then s ? m + 1.It is also shown that all orthogonal designs of types (a, b, m ? a ? b) and (a, b), 0 ? a + b ? m, exist in orders m = 2^t and 2^t+2 · 3, t ? 1 a positive integer.     

The value function of an integer program

We consider integer programs in which the objective function and constraint matrix are fixed while the right-hand side varies. The value function gives, for each feasible right-hand side, the criterion value of the optimal solution. We provide a precise characterization of the closed-form expression for any value function. The class of Gomory functions consists of those functions constructed from linear functions by taking maximums, sums, non-negative multiples, and ceiling (i.e., next highest integer) operations. The class of Gomory functions is identified with the class of all possible value functions by the following results: (1) for any Gomory functiong, there is an integer program which is feasible for all integer vectorsv and hasg as value function; (2) for any integer program, there is a Gomory functiong which is the value function for that program (for all feasible right-hand sides); (3) for any integer program there is a Gomory functionf such thatf(v)≤0 if and only ifv is a feasible right-hand side. Applications of (1)–(3) are also given.     

Total dual integrality and integer polyhedra

A linear system Ax ? b (A, b rational) is said to be totally dual integral (TDI) if for any integer objective function c such that max {cx: Ax ? b} exists, there is an integer optimum dual solution. We show that if P is a polytope all of whose vertices are integer valued, then it is the solution set of a TDI system Ax ? b where b is integer valued. This was shown by Edmonds and Giles [4] to be a sufficient condition for a polytope to have integer vertices.     

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.     

A local convergence proof for the iterative aggregation method

The iterative aggregation method for the solution of a system of linear algebraic equations x = Ax + b, where A ≥ 0, b ≥ 0, s > 0, and s ′ A < s ′, is proved to be locally convergent. It is shown that the method can be considered a consistent nonstationary iterative method, where the iteration matrix depends on the current iterate, and that some norm of the iteration matrix is less than one in the vicinity of the solution.     

A class of parabolic quasi-variational inequalities,II

We consider a quasi-variational inequality (q.v.i.) introduced by A. Friedman and D. Kinderlehrer. A q.v.i. of this form gives rise, at least formally, to a Stefan problem of melting of water, where the relation ?v_x(x, t) = ?a(x, t)·(t) + b(x, t) holds on the free boundary x = s(t), and a > 0, b ? 0; the water temperature, v(x, t), is not necessarily nonnegative. In the standard Stefan problem a ≡ 1, b ≡ 0, and v ? 0. Friedman and Kinderlehrer proved the existence of a solution of the q.v.i. by a fixed point theorem for monotone mappings. Here we prove the existence of a solution by an entirely different method, based on finite difference approximations. The solution is shown to be smoother than that constructed by Friedman and Kinderlehrer.     

Sensitivity theorems in integer linear programming

We consider integer linear programming problems with a fixed coefficient matrix and varying objective function and right-hand-side vector. Among our results, we show that, for any optimal solution to a linear program max{wx: Axb}, the distance to the nearest optimal solution to the corresponding integer program is at most the dimension of the problem multiplied by the largest subdeterminant of the integral matrixA. Using this, we strengthen several integer programming proximity results of Blair and Jeroslow; Graver; and Wolsey. We also show that the Chvátal rank of a polyhedron {x: Axb} can be bounded above by a function of the matrixA, independent of the vectorb, a result which, as Blair observed, is equivalent to Blair and Jeroslow's theorem that each integer programming value function is a Gomory function.Supported by a grant from the Alexander von Humboldt Stiftung.Since September 1985: Department of Operations Research, Upson Hall, Cornell University, Ithaca, NY 14853, USA.Partially supported by the Sonderforschungbereich 21 (DFG), Institut für Ökonometrie und Operations Research of the University of Bonn, FR Germany.     

Overdetermined linear systems satisfying nonnegativity constraints

Let A be a nonnegative m × n matrix, and let b be a nonnegative vector of dimension m. Also, let S be a subspace of $\text{R}$ⁿ such that if P_S is the orthogonal projector onto S, then P_S ? 0. A necessary condition is given for the matrix A to satisfy the following property: For all b ? 0, if min[boxV]b ? Ax[boxV] is attained at x = x₀, then x₀ ? 0 and x₀ ? S. It is also shown that if a nonnegative matrix A has a nonnegative generalized inverse, then any submatrix of A also possesses a nonnegative generalized inverse.     

Diophantine problems in variables restricted to the values 0 and 1

Let $\text{F}$x₁,…,x_s be a form of degree d with integer coefficients. How large must s be to ensure that the congruence $\text{F}$(x₁,…,x_s) ≡ 0 (mod m) has a nontrivial solution in integers 0 or 1? More generally, if $\text{F}$ has coefficients in a finite additive group G, how large must s be in order that the equation $\text{F}$(x₁,…,x_s) = 0 has a solution of this type? We deal with these questions as well as related problems in the group of integers modulo 1 and in the group of reals.     

A unified approach for finding real and integer solutions to systems of linear inequalities

The variable-elimination method for solving linear inequalities is used for finding integer solutions. Properties of this method enable one to give a simple proof, for a large class of systems of linear inequalities, that if a system in this class has any (real-valued) solution, then it also has an integer solution. This class includes all systems of the form Ax>b where A is any real matrix and b does not contain any negative element. The variable-elimination method has an exponential bound on the storage requirement, and hence on the execution time. These exists a simple strategy aimed at reducing the amount of storage and execution time needed. An experimental implementation was used to explore the effectiveness of this strategy.     

Regular graphs with high edge degree

For any vertex x of a graph G let Δ(x) denote the set of vertices adjacent to x. We seek to describe the connected graphs G which are regular of valence n and in which for all adjacent vertices x and y |Δ(x) ∩ Δ(y)| = n ? 1 ? s. It is known that the complete graphs are the graphs for which s = 0. For any s, any complete many-partite graph, each part containing s + 1 vertices, is such a graph. We show that these are the only such graphs for which the valence exceeds 2s² ? s + 1. The graphs satisfying these conditions for s = 1 or 2 are characterized (up to the class of trivalent triangle-free graphs.)     

Solving linear programs from sign patterns

This paper is an attempt to provide a connection between qualitative matrix theory and linear programming. A linear program is said to be sign-solvable if the set of sign patterns of the optimal solutions is uniquely determined by the sign patterns of A, b, and c. It turns out to be NP-hard to decide whether a given linear program is sign-solvable or not. We then introduce a class of sign-solvable linear programs in terms of totally sign-nonsingular matrices, which can be recognized in polynomial time. For a linear program in this class, we devise an efficient combinatorial algorithm to obtain the sign pattern of an optimal solution from the sign patterns of A, b, and c. The algorithm runs in O(mγ) time, where m is the number of rows of A and γ is the number of all nonzero entries in A, b, and c.     

An infinite color analogue of Rado's theorem

Let R be a subring of the complex numbers and a be a cardinal. A system L of linear homogeneous equations with coefficients in R is called a-regular over R if, for every a-coloring of the nonzero elements of R, there is a monochromatic solution to L in distinct variables. In 1943, Rado classified those finite systems of linear homogeneous equations that are a-regular over R for all positive integers a. For every infinite cardinal a, we classify those finite systems of linear homogeneous equations that are a-regular over R. As a corollary, for every positive integer s, we have ℵ₀²>ℵs if and only if the equation x₀+sx₁=x₂+?+xs+2 is ℵ₀-regular over R. This generalizes the case s=1 due to Erd?s.     

An Initial-Boundary Value Problem for the Korteweg–de Vries Equation with Dominant Surface Tension

We consider the initial-boundary value problem (IBVP) for the Korteweg–de Vries equation with zero boundary conditions at x=0 and arbitrary smooth decreasing initial data. We prove that the solution of this IBVP can be found by solving two linear inverse scattering problems (SPs) on two different spectral planes. The first SP is associated with the KdV equation. The second SP is self-conjugate and its scattering function is found in terms of entries of the scattering matrix s(k) for the first SP. Knowing the scattering function, we solve the second inverse SP for finding the potential self-conjugate matrix. Consequently, the unknown object entering coefficients in the system of evolution equations for s(k,t) is found. Then, the time-dependent scattering matrix s(k,t) is expressed in terms of s(k)=s(k,0) and of solutions of the self-conjugate SP. Knowing s(k,t), we find the solution of the IBVP in terms of the solution of the Gelfand–Levitan–Marchenko equation in the first inverse SP.     

The fine triangle intersections for maximum kite packings

In this paper, the fine triangle intersection problem for a pair of maximum kite packings is investigated. Let Fin(v) = {(s,t) : a pair of maximum kite packings of order v intersecting in s blocks and s+t triangles}. Let Adm(v) = {(s, t) : s + t ≤ bv , s,t are non-negative integers}, where b v = v(v 1)/8 . It is established that Fin(v) = Adm(v)\{(bv-1, 0), (bv-1,1)} for any integer v ≡ 0, 1 (mod 8) and v ≥ 8; Fin(v) = Adm(v) for any integer v ≡ 2, 3, 4, 5, 6, 7 (mod 8) and v ≥ 4.     

A binary linear recurrence sequence of composite numbers

Let (a,b)∈Z², where b≠0 and (a,b)≠(±2,−1). We prove that then there exist two positive relatively prime composite integers x₁, x₂ such that the sequence given by xn+1=axn+bxn−1, n=2,3,… , consists of composite terms only, i.e., |xn| is a composite integer for each n∈N. In the proof of this result we use certain covering systems, divisibility sequences and, for some special pairs (a,±1), computer calculations. The paper is motivated by a result of Graham who proved this theorem in the special case of the Fibonacci-like sequence, where (a,b)=(1,1).