Parametric Integer Programming Analysis: A Contraction Approach

An algorithm is presented for solving families of integer linear programming problems in which the problems are "related" by having identical objective coefficients and constraint matrix coefficients. The righthand-side constants have the form b + θd where b and d are conformable vectors and θ varies from zero to one.The approach consists primarily of solving the most relaxed problem (θ = 1) using cutting planes and then contracting the region of feasible integer solutions in such a manner that the current optimal integer solution is eliminated.The algorithm was applied to 1800 integer linear programming problems with reasonable success. Integer programming problems which have proved to be unsolvable using cutting planes have been solved by expanding the region of feasible integer solutions (θ = 1) and then contracting to the original region.     

Verbal width in anabelian groups

The class A of anabelian groups is defined as the collection of finite groups without abelian composition factors. We prove that the commutator word [x₁, x₂] and the power word x₁^p have bounded width in A when p is an odd integer. By contrast, the word x³⁰ does not have bounded width in A. On the other hand, any given word w has bounded width for those groups G ∈ A whose composition factors are sufficiently large as a function of w. In the course of the proof we establish that sufficiently large almost simple groups cannot satisfy w as a coset identity.     

On the Number of Irreducible Points in Polyhedra

An integer point in a polyhedron is called irreducible iff it is not the midpoint of two other integer points in the polyhedron. We prove that the number of irreducible integer points in n-dimensional polytope P is at most \(O(m^{\lfloor \frac{n}{2}\rfloor }\log ^{n-1}\gamma )\), where n is fixed and P is given by a system of m linear inequalities with integer coefficients not exceeding (by absolute value) \(\gamma \). This bound is tight. Using this result we prove the conjecture asserting that the teaching dimension in the class of threshold functions of k-valued logic in n variables is \(\varTheta (\log ^{n-2} k)\) for any fixed \(n\ge 2\).     

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 number of conjugacy classes of zeros of characters

Letm be a fixed non-negative integer. In this work we try to answer the following question: What can be said about a (finite) groupG if all of its irreducible (complex) characters vanish on at mostm conjugacy classes? The classical result of Burnside about zeros of characters says thatG is abelian ifm=0, so it is reasonable to expect that the structure ofG will somehow reflect the fact that the irreducible characters vanish on a bounded number of classes. The same question can also be posed under the weaker hypothesis thatsome irreducible character ofG hasm classes of zeros. For nilpotent groups we shall prove that the order is bounded by a function ofm in the first case but only the derived length can be bounded in general under the weaker condition. For solvable groups the situation is not so well understood although we shall prove that the Fitting height can be bounded by a double logarithmic function ofm, improving a recent result by G. Qian.     

Detecting fixed points of nonexpansive maps by illuminating the unit ball

We give necessary and sufficient conditions for a nonexpansive map on a finite-dimensional normed space to have a nonempty, bounded set of fixed points. Among other results we show that if f: V → V is a nonexpansive map on a finite-dimensional normed space V, then the fixed point set of f is nonempty and bounded if and only if there exist w₁,..., w _m in V such that {f(w _i ) ? w _i : i = 1,..., m} illuminates the unit ball. This yields a numerical procedure for detecting fixed points of nonexpansive maps on finite-dimensional spaces. We also discuss applications of this procedure to certain nonlinear eigenvalue problems arising in game theory and mathematical biology.     

Numerical optimization method for packing regular convex polygons

An algorithm is presented for the approximate solution of the problem of packing regular convex polygons in a given closed bounded domain G so as to maximize the total area of the packed figures. On G a grid is constructed whose nodes generate a finite set W on G, and the centers of the figures to be packed can be placed only at some points of W. The problem of packing these figures with centers in W is reduced to a 0-1 linear programming problem. A two-stage algorithm for solving the resulting problems is proposed. The algorithm finds packings of the indicated figures in an arbitrary closed bounded domain on the plane. Numerical results are presented that demonstrate the effectiveness of the method.     

Rational maps as Schwarzian primitives

We examine when a meromorphic quadratic differential φ with prescribed poles is the Schwarzian derivative of a rational map. We give a necessary and sufficient condition: In the Laurent series of φ around each pole c, the most singular term should take the form(1- d2)/(2(z- c)2), where d is an integer, and then a certain determinant in the next d coefficients should vanish. This condition can be optimized by neglecting some information on one of the poles(i.e., by only requiring it to be a double pole). The case d = 2 was treated by Eremenko(2012). We show that a geometric interpretation of our condition is that the complex projective structure induced by φ outside the poles has a trivial holonomy group. This statement was suggested to us by Thurston in a private communication. Our work is related to the problem of finding a rational map f with a prescribed set of critical points, since the critical points of f are precisely the poles of its Schwarzian derivative.Finally, we study the pole-dependency of these Schwarzian derivatives. We show that, in the cubic case with simple critical points, an analytic dependency fails precisely when the poles are displaced at the vertices of a regular ideal tetrahedron of the hyperbolic 3-ball.     

Almost Empty Monochromatic Quadrilaterals in Planar Point Sets

For positive integers c, s ≥ 1, r ≥ 3, let W _r (c, s) be the least integer such that if a set of at least W _r (c, s) points in the plane, no three of which are collinear, is colored with c colors, then this set contains a monochromatic r-gon with at most s interior points. As is known, if r = 3, then W _r (c, s)=W _r (c, s). In this paper, we extend these results to the case r = 4. We prove that W4(2, 1) = 11, W4(3, 2) ≤ 120, and the least integer μ4(c) such that W4(c, μ4(c)) < ∞ is bounded by \(\left\lfloor {\frac{{c - 1}}{2}} \right\rfloor \cdot 2 \leqslant \mu 4\left( c \right) \leqslant 2c - 3\),where c ≥ 2.     

Operator inclusions and quasi-variational inequalities

The operator inclusion 0 ∈ A(x) + N(x) is studied. Themain results are concerned with the case where A is a bounded monotone-type operator from a reflexive space to its dual and N is a cone-valued operator. A criterion for this inclusion to have no solutions is obtained. Additive and homotopy-invariant integer characteristics of set-valued maps are introduced. Applications to the theory of quasi-variational inequalities with set-valued operators are given.     

A unified solving approach for two and three dimensional coverage problems in sensor networks

The problem of designing a wired or a wireless sensor network to cover, monitor and/or control a region of interest has been widely treated in literature. This problem is referred to in literature as the sensor placement problem (SPP) and in the most general case it consists in determining the number and the location of one or more kind of sensors with the aim of covering all the region of interest or a significant part of it. In this paper we propose a unified and stepwise solving approach for two and three dimensional coverage problems to be used in omni-directional and directional sensor networks. The proposed approach is based on schematizing the region of interest and the sensor potential locations by a grid of points and representing the sensor coverage area by a circle or by a circular sector. On this basis, the SPP is reduced to an optimal coverage problem and can be formulated by integer linear programming (ILP) models. We will resume the main ILP models used in our approach, highlighting, for each of them, the specific target to be achieved and the design constraints taken into account. The paper concludes with an application of the proposed approach to a real test case and a discussion of the obtained results.     

Unbounded disjointness preserving linear functionals and operators

Let E and F be Banach lattices. We show first that the disjointness preserving linear functionals separate the points of any infinite dimensional Banach lattice E, which shows that in this case the unbounded disjointness preserving operators from \({E\to F}\) separate the points of E. Then we show that every disjointness preserving operator \({T:E\to F}\) is norm bounded on an order dense ideal. In case E has order continuous norm, this implies that every unbounded disjointness preserving map \({T:E\to F}\) has a unique decomposition T = R + S, where R is a bounded disjointness preserving operator and S is an unbounded disjointness preserving operator, which is zero on a norm dense ideal. For the case that E = C(X), with X a compact Hausdorff space, we show that every disjointness preserving operator \({T:C(X)\to F}\) is norm bounded on a norm dense sublattice algebra of C(X), which leads then to a decomposition of T into a bounded disjointness preserving operator and a finite sum of unbounded disjointness preserving operators, which are zero on order dense ideals.     

Coloring Geometric Range Spaces

We study several coloring problems for geometric range-spaces. In addition to their theoretical interest, some of these problems arise in sensor networks. Given a set of points in ?² or ?³, we want to color them so that every region of a certain family (e.g., every disk containing at least a certain number of points) contains points of many (say, k) different colors. In this paper, we think of the number of colors and the number of points as functions of k. Obviously, for a fixed k using k colors, it is not always possible to ensure that every region containing k points has all colors present. Thus, we introduce two types of relaxations: either we allow the number of colors used to increase to c(k), or we require that the number of points in each region increases to p(k).Symmetrically, given a finite set of regions in ?² or ?³, we want to color them so that every point covered by a sufficiently large number of regions is contained in regions of k different colors. This requires the number of covering regions or the number of allowed colors to be greater than k.The goal of this paper is to bound these two functions for several types of region families, such as halfplanes, halfspaces, disks, and pseudo-disks. This is related to previous results of Pach, Tardos, and Tóth on decompositions of coverings.     

Sums of products of Ramanujan sums

The Ramanujan sum c _n (k) is defined as the sum of k-th powers of the primitive n-th roots of unity. We investigate arithmetic functions of r variables defined as certain sums of the products \({c_{m_1}(g_1(k))\cdots c_{m_r}(g_r(k))}\), where g ₁, . . . , g _r are polynomials with integer coefficients. A modified orthogonality relation of the Ramanujan sums is also derived.     

A Nilpotent Ideal in the Lie Rings with Automorphism of Prime Order

We improve the conclusion in Khukhro's theorem stating that a Lie ring (algebra) L admitting an automorphism of prime order p with finitely many m fixed points (with finite-dimensional fixed-point subalgebra of dimension m) has a subring (subalgebra) H of nilpotency class bounded by a function of p such that the index of the additive subgroup |L: H| (the codimension of H) is bounded by a function of m and p. We prove that there exists an ideal, rather than merely a subring (subalgebra), of nilpotency class bounded in terms of p and of index (codimension) bounded in terms of m and p. The proof is based on the method of generalized, or graded, centralizers which was originally suggested in [E. I. Khukhro, Math. USSR Sbornik 71 (1992) 51–63]. An important precursor is a joint theorem of the author and E. I. Khukhro on almost solubility of Lie rings (algebras) with almost regular automorphisms of finite order.     

NP completeness conditions for verifying the consistency of several kinds of systems of linear Diophantine congruences and equations

Three series of number-theoretic problems with explicitly marked parameters that concerning systems of modulo m congruences and systems of Diophantine equations with solutions from the given segment are proposed. Parameter constraints such that any problem of each series is NP complete when they are met are proved. For any m₁ and m₂ (m₁ < m₂ and m1 is not a divisor of m₂), the verification problem for the consistency of a system of linear congruences modulo m₁ and m₂ simultaneously, each containing exactly three variables, is proved to be NP complete. In addition, for any m > 2, the verification problem for the consistency on the subset, containing at least two elements, of the set {0, …, m–1} for the system of linear congruences modulo m, each of which contains exactly three variables, is proved to be NP complete. If P ≠ NP, one cannot replace the term 3-discongruence with the term 2-discongruence in the statement of the theorem. For systems of Diophantine linear equations, each of which contains exactly three variables, the verification problem for their consistency on the given segment of integers is proved to be NP complete. If P ≠ NP, one cannot replace the term 3-equation with the term 2-equation in the statement of the theorem. This problem can also have a simple geometrical interpretation concerning the NP completeness of the verification problem on whether there an integer point of intersection of the given hyperplanes exists that cuts off equivalent segments on three axes and are parallel to other axes inside of a multidimensional cube. The problems of the stated series include practically useful problems. Since the range of values for an integer computer variable can be considered integer values from a segment, if P ≠ NP, theorem 5 proves that any algorithm that solves these systems in the set of numbers of the integer type is nonpolynomial [6].     

Number of lattice points in a sphere

A new estimate is obtained for the residue R in the asymptotics of the number of integer points in a ball of radius a. The estimate has the form R ? a ^{17/14 + ?} .     

An Improved Formulation for the Job-Shop Scheduling Problem

This paper presents an extension of an earlier integer programming model developed by other authors to formulate a general n-job, m-machine job-shop problem. The new formulation involves substantially fewer functional constraints at the expense of an increase in the number of upper bound variables. This reduction of functional constraints, together with the imposition of upper and lower bounds on the objective value, significantly reduces the computation time for solving the integer model for the job-shop scheduling problem.     

A polynomial–exponential equation related to the Ramanujan–Nagell equation

For any given odd prime p and a fixed positive integer D prime to p, we study the equation \(x^2+D^m=p^n\) in positive integers x, m and n. We use a classical work of Dem’janenko in 1965 on a certain quadratic Diophantine equation together with some results concerning the existence of primitive divisors of Lucas sequences to examine our equation when D is a product of \(p-1\) and a square.     

Exact augmented Lagrangian duality for mixed integer linear programming

We investigate the augmented Lagrangian dual (ALD) for mixed integer linear programming (MIP) problems. ALD modifies the classical Lagrangian dual by appending a nonlinear penalty function on the violation of the dualized constraints in order to reduce the duality gap. We first provide a primal characterization for ALD for MIPs and prove that ALD is able to asymptotically achieve zero duality gap when the weight on the penalty function is allowed to go to infinity. This provides an alternative characterization and proof of a recent result in Boland and Eberhard (Math Program 150(2):491–509, 2015, Proposition 3). We further show that, under some mild conditions, ALD using any norm as the augmenting function is able to close the duality gap of an MIP with a finite penalty coefficient. This generalizes the result in Boland and Eberhard (2015, Corollary 1) from pure integer programming problems with bounded feasible region to general MIPs. We also present an example where ALD with a quadratic augmenting function is not able to close the duality gap for any finite penalty coefficient.