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

We consider a parametric convex quadratic programming, CQP, relaxation forthe quadratic knapsack problem, QKP. This relaxation maintains partialquadratic information from the original QKP by perturbing the objectivefunction to obtain a concave quadratic term. The nonconcave part generated bythe perturbation is then linearized by a standard approach that lifts theproblem to the matrix space. We present a primal-dual interior point method tooptimize the perturbation of the quadratic function, in a search for thetightest upper bound for the \QKPp. We prove that the same perturbationapproach, when applied in the context of semidefinite programming, SDP,relaxations of the QKP, cannot improve the upper bound given by thecorresponding linear \SDP relaxation. The result also applies to more generalinteger quadratic problems. Finally, we propose new valid inequalities on thelifted matrix variable, derived from cover and knapsack inequalities for theQKP, and present the separation problems to generate cuts for the currentsolution of the CQP relaxation. Our best bounds are obtained from alternatingbetween optimizing the parametric quadratic relaxation over the perturbationand adding cutting planes generated by the valid inequalities proposed.

Parametric Convex Quadratic Relaxation of the Quadratic Knapsac Problem