A conjugate direction based simplicial decomposition framework for solving a specific class of dense convex quadratic programs

Enrico Bettiol (), Lucas Létocart (), Francesco Rinaldi () and Emiliano Traversi ()
Additional contact information
Enrico Bettiol: Université Paris 13, Sorbonne Paris Cité
Lucas Létocart: Université Paris 13, Sorbonne Paris Cité
Francesco Rinaldi: Università di Padova
Emiliano Traversi: Université Paris 13, Sorbonne Paris Cité

Computational Optimization and Applications, 2020, vol. 75, issue 2, No 1, 360 pages

Abstract: Abstract Many real-world applications can usually be modeled as convex quadratic problems. In the present paper, we want to tackle a specific class of quadratic programs having a dense Hessian matrix and a structured feasible set. We hence carefully analyze a simplicial decomposition like algorithmic framework that handles those problems in an effective way. We introduce a new master solver, called Adaptive Conjugate Direction Method, and embed it in our framework. We also analyze the interaction of some techniques for speeding up the solution of the pricing problem. We report extensive numerical experiments based on a benchmark of almost 1400 instances from specific and generic quadratic problems. We show the efficiency and robustness of the method when compared to a commercial solver (Cplex).

Keywords: Simplicial decomposition; Convex quadratic programming; Dense Hessian matrix; Column generation; 65K05; 90C20; 90C25 (search for similar items in EconPapers)
Date: 2020
References: View references in EconPapers View complete reference list from CitEc
Citations: View citations in EconPapers (1)

Downloads: (external link)
http://link.springer.com/10.1007/s10589-019-00151-4 Abstract (text/html)
Access to the full text of the articles in this series is restricted.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:coopap:v:75:y:2020:i:2:d:10.1007_s10589-019-00151-4

Ordering information: This journal article can be ordered from
http://www.springer.com/math/journal/10589

DOI: 10.1007/s10589-019-00151-4

Access Statistics for this article

Computational Optimization and Applications is currently edited by William W. Hager

More articles in Computational Optimization and Applications from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().