Minimal infeasible constraint sets in convex integer programs

In this paper we investigate certain aspects of infeasibility in convex integer programs, where the constraint functions are defined either as a composition of a convex increasing function with a convex integer valued function of n variables or the sum of similar functions. In particular we are concerned with the problem of an upper bound for the minimal cardinality of the irreducible infeasible subset of constraints defining the model. We prove that for the considered class of functions, every infeasible system of inequality constraints in the convex integer program contains an inconsistent subsystem of cardinality not greater than 2 ⁿ , this way generalizing the well known theorem of Scarf and Bell for linear systems. The latter result allows us to demonstrate that if the considered convex integer problem is bounded below, then there exists a subset of at most 2 ⁿ −1 constraints in the system, such that the minimum of the objective function subject to the inequalities in the reduced subsystem, equals to the minimum of the objective function over the entire system of constraints.     

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.     

Tight bounds and 2-approximation algorithms for integer programs with two variables per inequality

The problem of integer programming in bounded variables, over constraints with no more than two variables in each constraint is NP-complete, even when all variables are binary. This paper deals with integer linear minimization problems inn variables subject tom linear constraints with at most two variables per inequality, and with all variables bounded between 0 andU. For such systems, a 2-approximation algorithm is presented that runs in time O(mnU ² log(Un ² m)), so it is polynomial in the input size if the upper boundU is polynomially bounded. The algorithm works by finding first a super-optimal feasible solution that consists of integer multiples of 1/2. That solution gives a tight bound on the value of the minimum. It furthermore has an identifiable subset of integer components that retain their value in an integer optimal solution of the problem. These properties are a generalization of the properties of the vertex cover problem. The algorithm described is, in particular, a 2-approximation algorithm for the problem of minimizing the total weight of true variables, among all truth assignments to the 2-satisfiability problem.This paper is dedicated to Phil Wolfe on the occasion of his 65th birthday.Research supported in part by ONR contracts N00014-88-K-0377 and N00014-91-J-1241.Research supported in part by ONR contract N00014-91-C-0026.Part of this work was done while the author was visiting the International Computer Science Institute in Berkeley, CA and DIMACS, Rutgers University, New Brunswick, NJ.     

Uniqueness of integer solution of linear equations

We consider the system of m linear equations in n integer variables Ax = d and give sufficient conditions for the uniqueness of its integer solution x ∈ {−1, 1} ⁿ by reformulating the problem as a linear program. Necessary and sufficient uniqueness characterizations of ordinary linear programming solutions are utilized to obtain sufficient uniqueness conditions such as the intersection of the kernel of A and the dual cone of a diagonal matrix of ±1’s is the origin in R ⁿ . This generalizes the well known condition that ker(A) = 0 for the uniqueness of a non-integer solution x of Ax = d. A zero maximum of a single linear program ensures the uniqueness of a given integer solution of a linear equation.     

Solving large single allocation p-hub problems with two or three hubs

In this paper we present an efficient approach for solving single allocation p-hub problems with two or three hubs. Two different variants of the problem are considered: the uncapacitated single allocation p-hub median problem and the p-hub allocation problem. We solve these problems using new mixed integer linear programming formulations that require fewer variables than those formerly used in the literature. The problems that we solve here are the largest single allocation problems ever solved. The numerical results presented here will demonstrate the superior performance of our mixed integer linear programs over traditional approaches for large problems. Finally we present the first mixed integer linear program for solving single allocation hub location problems that requires only O(n²) variables and O(n²) constraints that is valid for any number of hubs.     

Linear spaces withn + n + 2lines

It is shown that every non-degenerate linear space withn² + n + 2lines,n ≥ 6, hasv n² + 1 − epoints, whereeis the unique positive real number withn =½e(e + 1). For values ofnfor whicheis an integer, it is shown that the linear spaces withn² + 1 − epoints andn² + n + 2lines are related to symmetric divisible designs.     

Bound reduction using pairs of linear inequalities

We describe a procedure to reduce variable bounds in mixed integer nonlinear programming (MINLP) as well as mixed integer linear programming (MILP) problems. The procedure works by combining pairs of inequalities of a linear programming (LP) relaxation of the problem. This bound reduction procedure extends the feasibility based bound reduction technique on linear functions, used in MINLP and MILP. However, it can also be seen as a special case of optimality based bound reduction, a method to infer variable bounds from an LP relaxation of the problem. For an LP relaxation with m constraints and n variables, there are O(m ²) pairs of constraints, and a naïve implementation of our bound reduction scheme has complexity O(n ³) for each pair. Therefore, its overall complexity O(m ² n ³) can be prohibitive for relatively large problems. We have developed a more efficient procedure that has complexity O(m ² n ²), and embedded it in two Open-Source solvers: one for MINLP and one for MILP. We provide computational results which substantiate the usefulness of this bound reduction technique for several instances.     

Generation of all integer points for given sets of linear inequalities

We propose to give a computationally feasible procedure for the generation of all the integer points satisfying a given set of inequalities. Five different systems of inequalities will be considered. In order to generate all of these integer points, one requires a particular set of integer points, called fundamental points, and a set of linearly independent vectors with integer components. The number of these fundamental points is given by a simple formula. We show how to generate the fundamental points and the required vectors. We give an application concerning the localization of the integer optimum of a linear objective function subject to constraints which geometrically define a cone or a parallelotope.This paper was presented at the 7th Mathematical Programming Symposium, 1970, The Hague, The Netherlands, under the title Some linear inequalities in Z ⁿ .     

Existence of certain skew room frames with application to weakly 3-chromatic linear spaces

It is shown that for any even integer n ≥ 16 and for some b ≥ 1, there exists a skew Room frame of type 2^a 4^b with n = 2a + 4b. As an application, we show that for any integer v ≡ 1,4 (mod 12), there exists a weakly 3-chromatic linear space with all lines having size 4 iff v > 16. This answers an open problem posed by Colbourn and Rosa. © 1994 John Wiley & Sons, Inc.     

Comparative studies on dynamic programming and integer programming approaches for concave cost production/inventory control problems

This paper is concerned with classical concave cost multi-echelon production/inventory control problems studied by W. Zangwill and others. It is well known that the problem with m production steps and n time periods can be solved by a dynamic programming algorithm in O(n ⁴ m) steps, which is considered as the fastest algorithm for solving this class of problems. In this paper, we will show that an alternative 0–1 integer programming approach can solve the same problem much faster particularly when n is large and the number of 0–1 integer variables is relatively few. This class of problems include, among others problem with set-up cost function and piecewise linear cost function with fewer linear pieces. The new approach can solve problems with mixed concave/convex cost functions, which cannot be solved by dynamic programming algorithms.     

Fast algorithms for determining the linear complexities of sequences over GF(pm) with the period 3n

In this paper, for the the primes p such that 3 is a divisor of p − 1, we prove a result which reduces the computation of the linear complexity of a sequence over GF(p ^m) (any positive integer m) with the period 3n (n and p ^m − 1 are coprime) to the computation of the linear complexities of three sequences with the period n. Combined with some known algorithms such as generalized Games-Chan algorithm, Berlekamp-Massey algorithm and Xiao-Wei-Lam-Imamura algorithm, we can determine the linear complexity of any sequence over GF(p ^m) with the period 3n (n and p ^m − 1 are coprime) more efficiently.     

New integer linear programming formulation for the traveling salesman problem with time windows: minimizing tour duration with waiting times

The travelling salesman problem, being one of the most attractive and well-studied combinatorial optimization problems, has many variants, one of which is called ‘travelling salesman problem with Time Windows (TSPTW)’. In this problem, each city (nodes, customers) must be visited within a time window defined by the earliest and the latest time. In TSPTW, the traveller has to wait at a city if he/she arrives early; thus waiting times directly affect the duration of a tour. It would be useful to develop a new model solvable by any optimizer directly. In this paper, we propose a new integer linear programming formulation having O(n²) binary variables and O(n²) constraints, where (n) equals the number of nodes of the underlying graph. The objective function is stated to minimize the total travel time plus the total waiting time. A computational comparison is made on a suite of test problems with 20 and 40 nodes. The performances of the proposed and existing formulations are analysed with respect to linear programming relaxations and the CPU times. The new formulation considerably outperforms the existing one with respect to both the performance criteria. Adaptation of our formulation to the multi-traveller case and some additional restrictions for special situations are illustrated.     

A geometric perspective on counting non-negative integer solutions and combinatorial identities

We consider the effect of constraints on the number of non-negative integer solutions of x+y+z = n, relating the number of solutions to linear combinations of triangular numbers. Our approach is geometric and may be viewed as an introduction to proofs without words. We use this geometrical perspective to prove identities by counting the number of solutions in two different ways, thereby combining combinatorial proofs and proofs without words.     

On the log-concavity of Hilbert series of Veronese subrings and Ehrhart series

For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write ${\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}}For every positive integer n, consider the linear operator U _n on polynomials of degree at most d with integer coefficients defined as follows: if we write \frach(t)(1 - t)^{d + 1}=?_{m 3 0} g(m)  t^m{\frac{h(t)}{(1 - t)^{d + 1}}=\sum_{m \geq 0} g(m) \, t^{m}} , for some polynomial g(m) with rational coefficients, then \fracU_nh(t)(1- t)^d+1 = ?_{m 3 0}g(nm)  t^m{\frac{{\rm{U}}_{n}h(t)}{(1- t)^{d+1}} = \sum_{m \geq 0}g(nm) \, t^{m}} . We show that there exists a positive integer n _d , depending only on d, such that if h(t) is a polynomial of degree at most d with nonnegative integer coefficients and h(0) = 1, then for n ≥ n _d , U _n h(t) has simple, real, negative roots and positive, strictly log concave and strictly unimodal coefficients. Applications are given to Ehrhart δ-polynomials and unimodular triangulations of dilations of lattice polytopes, as well as Hilbert series of Veronese subrings of Cohen–Macauley graded rings.     

Model-theory of vector-spaces over unspecified fields

Vector spaces over unspecified fields can be axiomatized as one-sorted structures, namely, abelian groups with the relation of parallelism. Parallelism is binary linear dependence. When equipped with the n-ary relation of linear dependence for some positive integer n, a vector-space is existentially closed if and only if it is n-dimensional over an algebraically closed field. In the signature with an n-ary predicate for linear dependence for each positive integer n, the theory of infinite-dimensional vector spaces over algebraically closed fields is the model-completion of the theory of vector spaces.      

Representation ofL p-norms and isometric embedding inL p-spaces

For fixed 1≦p<∞ theL _p-semi-norms onR ⁿ are identified with positive linear functionals on the closed linear subspace ofC(R ⁿ ) spanned by the functions |<ξ, ·>| ^p , ξ∈R ⁿ . For every positive linear functional σ, on that space, the function Φ_σ:R ⁿ →R given by Φ_σ is anL _p-semi-norm and the mapping σ→Φ_σ is 1-1 and onto. The closed linear span of |<ξ, ·>| ^p , ξ∈R ⁿ is the space of all even continuous functions that are homogeneous of degreep, ifp is not an even integer and is the space of all homogeneous polynomials of degreep whenp is an even integer. This representation is used to prove that there is no finite list of norm inequalities that characterizes linear isometric embeddability, in anyL _p unlessp=2. Supported by the National Science Foundation MCS-79-06634 at U.C. Berkeley.     

A Boundedness Criterion via Atoms for Linear Operators in Hardy Spaces

Let p∈(0,1] and s≥[n(1/p−1)], where [n(1/p−1)] denotes the maximal integer no more than n(1/p−1). In this paper, the authors prove that a linear operator T extends to a bounded linear operator from the Hardy space H ^p (ℝ ⁿ ) to some quasi-Banach space ℬ if and only if T maps all (p,2,s)-atoms into uniformly bounded elements of ℬ.      

Equiangular lines in C (part II)

A subset S of a complex projective space is F-regular provided each two points of S have the same non-zero distance and each subset of three points of S has the same shape invariant. The aim of this paper is the determination for any odd integer r, of the largest integer n(r) such tht CP^r−1 contains an F-regular subset of n(r) points.It is established that n(r) ≤ 2r − 2 for any odd integer r and n(1 + 2^s) = 2^s+1 for any integer s.     

The LIL convergence for stationary linear random field

LetY={Y _n;n N ²} be a stationary linear random field generated by a twodimensional martingale difference. WhereN ² denotes the two dimensional integer lattice. The main purpose of this paper is to obtain the LIL convergence for the partial-sums ofY.Supported by NSFC and FEYUT SEDC CHINA.     

Small Grid Embeddings of 3-Polytopes

We introduce an algorithm that embeds a given 3-connected planar graph as a convex 3-polytope with integer coordinates. The size of the coordinates is bounded by O(2^7.55n )=O(188 ⁿ ). If the graph contains a triangle we can bound the integer coordinates by O(2^4.82n ). If the graph contains a quadrilateral we can bound the integer coordinates by O(2^5.46n ). The crucial part of the algorithm is to find a convex plane embedding whose edges can be weighted such that the sum of the weighted edges, seen as vectors, cancel at every point. It is well known that this can be guaranteed for the interior vertices by applying a technique of Tutte. We show how to extend Tutte’s ideas to construct a plane embedding where the weighted vector sums cancel also on the vertices of the boundary face.