• xmlui.mirage2.page-structure.header.title
    • français
    • English
  • Help
  • Login
  • Language 
    • Français
    • English
View Item 
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
  •   BIRD Home
  • LAMSADE (UMR CNRS 7243)
  • LAMSADE : Publications
  • View Item
JavaScript is disabled for your browser. Some features of this site may not work without it.

Browse

BIRDResearch centres & CollectionsBy Issue DateAuthorsTitlesTypeThis CollectionBy Issue DateAuthorsTitlesType

My Account

LoginRegister

Statistics

Most Popular ItemsStatistics by CountryMost Popular Authors
Thumbnail - Request a copy

Approximated perspective relaxations: a project and lift approach

Frangioni, Antonio; Furini, Fabio; Gentile, Claudio (2016), Approximated perspective relaxations: a project and lift approach, Computational Optimization and Applications, 63, 3, p. 705-735. 10.1007/s10589-015-9787-8

Type
Article accepté pour publication ou publié
Date
2016
Journal name
Computational Optimization and Applications
Volume
63
Number
3
Publisher
Kluwer Academic Publishers
Pages
705-735
Publication identifier
10.1007/s10589-015-9787-8
Metadata
Show full item record
Author(s)
Frangioni, Antonio
Department of Computer Science [Pisa]
Furini, Fabio
Laboratoire d'analyse et modélisation de systèmes pour l'aide à la décision [LAMSADE]
Gentile, Claudio
Istituto di Analisi dei Sistemi ed Informatica "A. Ruberti"
Abstract (EN)
The perspective reformulation (PR) of a Mixed-Integer NonLinear Program with semi-continuous variables is obtained by replacing each term in the (separable) objective function with its convex envelope. Solving the corresponding continuous relaxation requires appropriate techniques. Under some rather restrictive assumptions, the Projected PR (P2R) can be defined where the integer variables are eliminated by projecting the solution set onto the space of the continuous variables only. This approach produces a simple piecewise-convex problem with the same structure as the original one; however, this prevents the use of general-purpose solvers, in that some variables are then only implicitly represented in the formulation. We show how to construct an Approximated Projected PR (AP2R) whereby the projected formulation is “lifted” back to the original variable space, with each integer variable expressing one piece of the obtained piecewise-convex function. In some cases, this produces a reformulation of the original problem with exactly the same size and structure as the standard continuous relaxation, but providing substantially improved bounds. In the process we also substantially extend the approach beyond the original P2R development by relaxing the requirement that the objective function be quadratic and the left endpoint of the domain of the variables be non-negative. While the AP2R bound can be weaker than that of the PR, this approach can be applied in many more cases and allows direct use of off-the-shelf MINLP software; this is shown to be competitive with previously proposed approaches in some applications.
Subjects / Keywords
Mixed-integer nonlinear problems; Semi-continuous variables; Perspective reformulation; Projection
JEL
C25 - Discrete Regression and Qualitative Choice Models; Discrete Regressors; Proportions; Probabilities

Related items

Showing items related by title and author.

  • Thumbnail
    Improving the Approximated Projected Perspective Reformulation by dual information 
    Frangioni, Antonio; Furini, Fabio; Gentile, Claudio (2017) Article accepté pour publication ou publié
  • Thumbnail
    QPLIB: a library of quadratic programming instances 
    Furini, Fabio; Traversi, Emiliano; Belotti, Pietro; Frangioni, Antonio; Gleixner, Ambros; Gould, Nick; Liberti, Leo; Lodi, Andrea; Misener, Ruth; Mittelmann, Hans; Sahinidis, Nikolaos V.; Vigerske, Stefan; Wiegele, Angelika (2019) Article accepté pour publication ou publié
  • Thumbnail
    Bone Marrow-Infiltrating Human Neuroblastoma Cells Express High Levels of Calprotectin and HLA-G Proteins 
    Morandi, Fabio; Scaruffi, Paola; Gallo, Fabio; Stigliani, Sara; Moretti, Stefano; Bonassi, Stefano; Gambini, Claudio; Mazzocco, Katia; Fardin, Paolo; Haupt, Riccardo; Pistoia, Vito; Tonini, Gian Paolo; Corrias, Maria Valeria (2012) Article accepté pour publication ou publié
  • Thumbnail
    ACCRA Project: Agile Co-Creation for Robots and Aging 
    Fiorini, Laura; D’Onofrio, Grazia; Limosani, Raffaele; Sancarlo, Daniele; Greco, Antonio; Giuliani, Francesco; Kung, Antonio; Dario, Paolo; Cavallo, Filippo Communication / Conférence
  • Thumbnail
    Agile Co-Creation for Robots and Aging (ACCRA) Project: new technological solutions for older people 
    D’Onofrio, Grazia; Fiorini, Laura; De Mul, Marleen; Guiot, Denis; Sengès, Eloïse; Fabbricotti, Isabelle; Okabe, Yasuo; Hoshino, Hiroshi; Limosani, Raffaele; Vitanza, Alessandra; Greco, Francesca; Giuliani, Francesco; Kung, Antonio; Cavallo, Filippo; Sancarlo, Daniele; Greco, Antonio (2018) Article accepté pour publication ou publié
Dauphine PSL Bibliothèque logo
Place du Maréchal de Lattre de Tassigny 75775 Paris Cedex 16
Phone: 01 44 05 40 94
Contact
Dauphine PSL logoEQUIS logoCreative Commons logo