Subscribe to the gold package and get unlimited access to Shamra Academy
Register a new userPolynomial upper bounds on the number of differing columns of $Delta$-modular integer programs
290
0
0.0
(
0
)
Ask ChatGPT about the research
No Arabic abstract
We consider integer programs (IP) defined by equations and box constraints, where it is known that determinants in the constraint matrix are one measure of complexity. For example, Artmann et al. showed that an IP can be solved in strongly polynomial time if the constraint matrix is bimodular, that is, the determinants are bounded in absolute value by two. Determinants are also used to bound the $ell_1$-distance between IP solutions and solutions of its linear relaxation. One of the first works to quantify the complexity of IPs with bounded determinants was that of Heller, who identified the maximum number of differing columns in a totally unimodular constraint matrix. So far, each extension of Hellers bound to general determinants has been exponential in the determinants or the number of equations. We provide the first column bound that is polynomial in both values. As a corollary, we give the first $ell_1$-distance bound that is polynomial in the determinants and the number of equations. We also show a tight bound on the number of differing columns in a bimodular constraint matrix; this is the first tight bound since Hellers result. Our analysis reveals combinatorial properties of bimodular IPs that may be of independent interest, in particular in recognition algorithms for IPs with bounded determinants.
rate research
Read More
We settle the computational complexity of fundamental questions related to multicriteria integer linear programs, when the dimensions of the strategy space and of the outcome space are considered fixed constants. In particular we construct: 1. polynomial-time algorithms to exactly determine the number of Pareto optima and Pareto strategies; 2. a polynomial-space polynomial-delay prescribed-order enumeration algorithm for arbitrary projections of the Pareto set; 3. an algorithm to minimize the distance of a Pareto optimum from a prescribed comparison point with respect to arbitrary polyhedral norms; 4. a fully polynomial-time approximation scheme for the problem of minimizing the distance of a Pareto optimum from a prescribed comparison point with respect to the Euclidean norm.
We introduce a new class of optimization problems called integer Minkowski programs. The formulation of such problems involves finitely many integer variables and nonlinear constraints involving functionals defined on families of discrete or polyhedral sets. We show that, under certain assumptions, it is possible to reformulate them as integer linear programs, by making use of integral generating sets. We then apply this technique to the network design problem for fractional and integral flows subject to survivability constraints.
Mixed Integer Programming (MIP) solvers rely on an array of sophisticated heuristics developed with decades of research to solve large-scale MIP instances encountered in practice. Machine learning offers to automatically construct better heuristics from data by exploiting shared structure among instances in the data. This paper applies learning to the two key sub-tasks of a MIP solver, generating a high-quality joint variable assignment, and bounding the gap in objective value between that assignment and an optimal one. Our approach constructs two corresponding neural network-based components, Neural Diving and Neural Branching, to use in a base MIP solver such as SCIP. Neural Diving learns a deep neural network to generate multiple partial assignments for its integer variables, and the resulting smaller MIPs for un-assigned variables are solved with SCIP to construct high quality joint assignments. Neural Branching learns a deep neural network to make variable selection decisions in branch-and-bound to bound the objective value gap with a small tree. This is done by imitating a new variant of Full Strong Branching we propose that scales to large instances using GPUs. We evaluate our approach on six diverse real-world datasets, including two Google production datasets and MIPLIB, by training separate neural networks on each. Most instances in all the datasets combined have $10^3-10^6$ variables and constraints after presolve, which is significantly larger than previous learning approaches. Comparing solvers with respect to primal-dual gap averaged over a held-out set of instances, the learning-augmented SCIP is 2x to 10x better on all datasets except one on which it is $10^5$x better, at large time limits. To the best of our knowledge, ours is the first learning approach to demonstrate such large improvements over SCIP on both large-scale real-world application datasets and MIPLIB.
We show that sparsity constrained optimization problems over low dimensional spaces tend to have a small duality gap. We use the Shapley-Folkman theorem to derive both data-driven bounds on the duality gap, and an efficient primalization procedure to recover feasible points satisfying these bounds. These error bounds are proportional to the rate of growth of the objective with the target cardinality, which means in particular that the relaxation is nearly tight as soon as the target cardinality is large enough so that only uninformative features are added.
The paper deals with planar polynomial vector fields. We aim to estimate the number of orbital topological equivalence classes for the fields of degree n. An evident obstacle for this is the second part of Hilberts 16th problem. To circumvent this obstacle we introduce the notion of equivalence modulo limit cycles. This paper is the continuation of the authors paper in [Mosc. Math. J. 1 (2001), no. 4] where the lower bound of the form 2^{cn^2} has been obtained. Here we obtain the upper bound of the same form. We also associate an equipped planar graph to every planar polynomial vector field, this graph is a complete invariant for orbital topological classification of such fields.
Log in to be able to interact and post comments
comments
Fetching comments
Sign in to be able to follow your search criteria
