English (United Kingdom)

https://curated-unify.zendy.io/wp-json/zendy-region/v1/featured_content/oa?rat=en

https://curated-unify.zendy.io/wp-json/zendy-region/v1/highlighted_journal/

Global: Zendy Plus annual

Presents the access of premium content as premium feature

Premium Content

Presents the keyphrase highlighting as premium feature

Keyphrase Highlighting

Presents the summarisation as premium feature

Summarisation

Insights

Presents the pdf analysis as premium feature

PDF Analysis

Presents the zaia usage as premium feature

ZAIA

Global: Zendy Plus monthly

Global: Zendy Tools annual

Global: Zendy Tools monthly

Global: Zendy Free Plan

Inspired by the decomposition in the hybrid quantum-classical optimizationalgorithm we introduced in arXiv:1902.04215, we propose here a new (fullyclassical) approach to solving certain non-convex integer programs using Graverbases. This method is well suited when (a) the constraint matrix $A$ has aspecial structure so that its Graver basis can be computed systematically, (b)several feasible solutions can also be constructed easily and (c) the objectivefunction can be viewed as many convex functions quilted together. Classes ofproblems that satisfy these conditions include Cardinality Boolean QuadraticProblems (CBQP), Quadratic Semi-Assignment Problems (QSAP) and QuadraticAssignment Problems (QAP). Our Graver Augmented Multi-seed Algorithm (GAMA)utilizes augmentation along Graver basis elements (the improvement direction isobtained by comparing objective function values) from these multiple initialfeasible solutions. We compare our approach with a best-in-class commerciallyavailable solver (Gurobi). Sensitivity analysis indicates that the rate atwhich GAMA slows down as the problem size increases is much lower than that ofGurobi. We find that for several instances of practical relevance, GAMA notonly vastly outperforms in terms of time to find the optimal solution (by twoor three orders of magnitude), but also finds optimal solutions within minuteswhen the commercial solver is not able to do so in 4 or 10 hours (depending onthe problem class) in several cases.

GAMA: A Novel Algorithm for Non-Convex Integer Programs