A continuous method for computing bounds in integer quadratic optimization problems

In the graph partitioning problem, as in other NP-hard problems, the problem of proving the existence of a cut of given size is easy and can be accomplished by exhibiting a solution with the correct value. On the other hand proving the non-existence of a cut better than a given value is very difficult. We consider the problem of maximizing a quadratic function x ^T Q x where Q is an n × n real symmetric matrix with x an n-dimensional vector constrained to be an element of {–1, 1} ⁿ . We had proposed a technique for obtaining upper bounds on solutions to the problem using a continuous approach in [4]. In this paper, we extend this method by using techniques of differential geometry.     

Global optimality conditions and optimization methods for quadratic integer programming problems

In this paper, we first establish some sufficient and some necessary global optimality conditions for quadratic integer programming problems. Then we present a new local optimization method for quadratic integer programming problems according to its necessary global optimality conditions. A new global optimization method is proposed by combining its sufficient global optimality conditions, local optimization method and an auxiliary function. The numerical examples are also presented to show that the proposed optimization methods for quadratic integer programming problems are very efficient and stable.     

The spectra of nonnegative integer matrices via formal power series

We characterize the possible nonzero spectra of primitive integer matrices (the integer case of Boyle and Handelman's Spectral Conjecture). Characterizations of nonzero spectra of nonnegative matrices over and follow from this result. For the proof of the main theorem we use polynomial matrices to reduce the problem of realizing a candidate spectrum to factoring the polynomial as a product where the 's are polynomials in satisfying some technical conditions and is a formal power series in . To obtain the factorization, we present a hierarchy of estimates on coefficients of power series of the form to ensure nonpositivity in nonzero degree terms.

     

Corrigendum: Combinatorial properties of integer matrices and integer matrices mod k

We correct an error in our paper “Combinatorial Properties of Integer Matrices and Integer Matrices mod k” that appeared in this journal (66, 1380–1402 (2017)).     

A new local and global optimization method for mixed integer quadratic programming problems

In this paper, a new local optimization method for mixed integer quadratic programming problems with box constraints is presented by using its necessary global optimality conditions. Then a new global optimization method by combining its sufficient global optimality conditions and an auxiliary function is proposed. Some numerical examples are also presented to show that the proposed optimization methods for mixed integer quadratic programming problems with box constraints are very efficient and stable.     

Unit integer quadratic binary programming

This paper presents an efficient method of computing $\text{?′}{}_{\mathrm{<mtext>max</mtext>}}\text{=}\text{max}\text{Y}\text{Y}{}^{\mathrm{<mtext>T</mtext>}}\text{AY}$, where Y is an N-dimensional vector of ±1 entries and A is a real symmetric matrix. The ratio of number of computations required by this method to that by the direct method is approximately ($\text{3}\text{2N}$), where the direct method corresponds to computing Y^TAY for all possible Y and then finding the maximum from these. This problem has important applications in operations research, matrix theory, signal processing, communication theory, control theory, and others. Some of these are discussed in this paper.     

Sums of random symmetric matrices and quadratic optimization under orthogonality constraints

Let B _i be deterministic real symmetric m × m matrices, and ξ _i be independent random scalars with zero mean and “of order of one” (e.g., ). We are interested to know under what conditions “typical norm” of the random matrix is of order of 1. An evident necessary condition is , which, essentially, translates to ; a natural conjecture is that the latter condition is sufficient as well. In the paper, we prove a relaxed version of this conjecture, specifically, that under the above condition the typical norm of S _N is : for all Ω > 0 We outline some applications of this result, primarily in investigating the quality of semidefinite relaxations of a general quadratic optimization problem with orthogonality constraints , where F is quadratic in X = (X ₁,... ,X _k ). We show that when F is convex in every one of X _j , a natural semidefinite relaxation of the problem is tight within a factor slowly growing with the size m of the matrices . Research was partly supported by the Binational Science Foundation grant #2002038.     

Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods

We present effective linear programming based computational techniques for solving nonconvex quadratic programs with box constraints (BoxQP). We first observe that known cutting planes obtained from the Boolean Quadric Polytope (BQP) are computationally effective at reducing the optimality gap of BoxQP. We next show that the Chvátal–Gomory closure of the BQP is given by the odd-cycle inequalities even when the underlying graph is not complete. By using these cutting planes in a spatial branch-and-cut framework, together with a common integrality-based preprocessing technique and a particular convex quadratic relaxation, we develop a solver that can effectively solve a well-known family of test instances. Our linear programming based solver is competitive with SDP-based state of the art solvers on small instances and sparse instances. Most of our computational techniques have been implemented in the recent version of CPLEX and have led to significant performance improvements on nonconvex quadratic programs with linear constraints.     

Global optimization of a quadratic function subject to a bounded mixed integer consraint set

In this paper we consider the optimization of a quadratic function subject to a linearly bounded mixed integer constraint set. We develop two types of piecewise affine convex underestimating functions for the objective function. These are used in a branch and bound algorithm for solving the original problem. We show finite convergence to a near optimal solution for this algorithm. We illustrate the algorithm with a small numerical example. Finally we discuss some modifications of the algorithm and address the question of extending the problem to include quadratic constraints.Supported by grants from the Danish Natural Science Research Council and the Danish Research Academy.     

Vandermonde matrices on integer nodes

Summary. This paper deals with Vandermonde matrices whose nodes are the first integer numbers. We give an analytic factorization of such matrices and explicit formulas for the entries of their inverses, and explore their computational issues. We also give asymptotic estimates of the Frobenius norm of both and its inverse. Received July 28, 1995 / Revised version received July 4, 1997     

Factorization of singular integer matrices

It is well known that a singular integer matrix can be factorized into a product of integer idempotent matrices. In this paper, we prove that every n  × n (n > 2) singular integer matrix can be written as a product of 3n + 1 integer idempotent matrices. This theorem has some application in the field of synthesizing VLSI arrays and systolic arrays.     

Pseudoprime factorizations of integer matrices

We give a method of factoring integer matrices in into components such that the factorization is not unique unless certain information is known. In Section 2, we introduce this method of factorization and provide theorems which establish its well-definedness. In Section 3, we construct a matrix in as a product of specific types of matrices and establish an algorithm for factoring the result uniquely given an amount of information.     

Analyzing quadratic unconstrained binary optimization problems via multicommodity flows

Quadratic Unconstrained Binary Optimization (QUBO) problems concern the minimization of quadratic polynomials in n{0,1}-valued variables. These problems are NP-complete, but prior work has identified a sequence of polynomial-time computable lower bounds on the minimum value, denoted by C₂,C₃,C₄,…. It is known that C₂ can be computed by solving a maximum flow problem, whereas the only previously known algorithms for computing require solving a linear program. In this paper we prove that C₃ can be computed by solving a maximum multicommodity flow problem in a graph constructed from the quadratic function. In addition to providing a lower bound on the minimum value of the quadratic function on {0,1}ⁿ, this multicommodity flow problem also provides some information about the coordinates of the point where this minimum is achieved. By looking at the edges that are never saturated in any maximum multicommodity flow, we can identify relational persistencies: pairs of variables that must have the same or different values in any minimizing assignment. We furthermore show that all of these persistencies can be detected by solving single-commodity flow problems in the same network.     

On characterization of maximal independent sets via quadratic optimization

This article investigates the local maxima properties of a box-constrained quadratic optimization formulation of the maximum independent set problem in graphs. Theoretical results characterizing binary local maxima in terms of certain induced subgraphs of the given graph are developed. We also consider relations between continuous local maxima of the quadratic formulation and binary local maxima in the Hamming distance-1 and distance-2 neighborhoods. These results are then used to develop an efficient local search algorithm that provides considerable speed-up over a typical local search algorithm for the binary Hamming distance-2 neighborhood.     

Proximity in concave integer quadratic programming

Mathematical Programming - A classic result by Cook, Gerards, Schrijver, and Tardos provides an upper bound of $$n Delta $$ on the proximity of optimal solutions of an Integer Linear Programming...