Istituto di Analisi dei Sistemi ed Informatica

Autore: Claudio Gentile

  • On the Balances Minimum Evolution Problem polytope

    Speaker: Daniele Catanzaro

    Abstract: Recent advances on the polyhedral combinatorics of the Balances Minimum Evolution Problem (BMEP) enabled the characterization of a number of facets of its convex hull (also referred to as the BMEP polytope) as well as the discovery of connections between this polytope and the permutoassociahedron. In this article, we extend these studies, by presenting new results concerning some fundamental characteristics of the BMEP polytope, new facet-defining inequalities in the case of six or more taxa, a number of valid inequalities, and a polynomial time oracle to recognize its vertices. Our aim is to broaden understanding of the polyhedral combinatorics of the BMEP with a view to developing new and more effective exact solution algorithms.

    Aula: Sala Riunioni VI piano
    Data: 26 Febbraio 2020 – ore 11.30

  • New MINLP Formulations for the Unit Commitment Problems with Ramping Cons traints

    A new paper among MINOA Partners: University of Pisa and CNR-IASI

    Abstract. The Unit Commitment (UC) problem in electrical power production requires to optimally operate a set of power generation units over a short time horizon (one day to a week). Operational constraints of each unit depend on its type (e.g., thermal, hydro, nuclear, \ldots), and can be rather complex. For thermal units, typical ones concern minimum and maximum power output, minimum up- and down-time, start-up and shut-down limits, ramp-up and ramp-down limits. Also, the objective function is often nonlinear. Thus, even the Single-Unit Commitment (1UC) problem, in which only one unit is present, has a rich combinatorial structure. In this  work we present the first MINLP formulation that describes the convex hull of the feasible solutions of (1UC) comprising all the above constraints, and convex power generation costs. The new formulation has a polynomial number of both variables and constraints, and it is based on the efficient Frangioni-Gentile Dynamic Programming algorithm  together with the Perspective Reformulation technique. We then analyze the effect of using it to develop tight formulations for the more general (UC). Since the formulation, despite being polynomial-size, is rather large, we also propose two new formulations, based on partial aggregations of variables, with different trade-offs between quality of the obtained bound and cost of the solving the corresponding continuous relaxation. Our results show that navigating these trade-offs may lead to improved performances for the partial enumeration approach used to solve the problem.

    Keywords: Unit Commitment problem, Ramp Constraints, MIP Formulations, Dynamic Programming, Convex Costs

    Cite as: T. Bacci, A. Frangioni, C. Gentile, K. Tavlaridis-Gyparakis, New MINLP Formulation for the Unit Commitment Problems with Ramping Constraints.  Optimization online.

    An additional note. A previous version of the paper for MI-SOCP  formulations was published as IASI Research Report 19-04. Moreover, IASI Research Report 19-03 presents a counterexample to a previous work for an exact MINLP formulation for the single-unit Unit Commitment problem with ramping constraints and convex objective function.

  • EXPEDIS: a new approach for solving binary quadratic problems

    Speaker: Nicolò Gusmeroli
    Location: Roma, Via dei Taurini 19, Sala Riunioni VI Piano
    Date:  November 7, 2019  time 11.30 
    Contact person: Claudio Gentile

  • #CTW2020conference starting submissions!!

    For whom liked the #1stMINOAPhDschool and for whom missed it! #CTW2020conference in Ischia, June 15-27, 2020! Starting submissions on ctw2020.iasi.cnr.it

  • Great success for #1stMINOAPhDSchool

    The school has been a great success: 75 students and researchers attended. See #1stMINOAPhDSchool in twitter @gentileIASICNR @MINOA_ETN to look at pictures of the event. Thanks to all participants and great thanks to all lecturers. 

  • Yoshua Bengio received the Turing Award

    Citation from the ACM website: For conceptual and engineering breakthroughs that have made deep neural networks a critical component of computing. https://amturing.acm.org/award_winners/bengio_3406375.cfm.

    Yosha Bengio will be lecturer at the 1st MINOA PhD school  “Mixed-Integer Nonlinear Optimization meets Data Science” organized by CNR-IASI that will be held on June 25-28 at Ischia (NA), Italy.

  • History and solution of Steinberg’s conjecture

    Speaker: Esteban Salgado – IASI

    YES@IASI – Young Experts Seminars

    Abstract: Steinberg conjectured in 1976 that every planar graph with no cycles of length four or five is 3-colorable. I’ll present a brief summary of the results obtained from the attempts to solve this conjecture as well as a counterexample that disproof it.
    Location: Roma, Via dei Taurini 19, Aula Piano Terra
    Date:  February 27, 2019  time 11.30 
    Contact person: Claudio Gentile

  • PhD school on the theme “Mixed Integer Non Linear Optimization meets Data Science” registrations are now open.

    CNR-IASI, as part of the Marie Sklodowska-Curie ETN MINOA (http://minoa-itn.fau.de), announces the school for PhD students and post-docs on the theme Mixed Integer Non linear Optimization meets Data Science. The school will be held on June 24-28, 2019 in Ischia (Italy) at Hotel Hermitage. See www.iasi.cnr.it/minoa/big-data-school for information and registrations.

  • The Maximum Clique Interdiction Game

    Speaker: Fabio Furini – LAMSADE, Université Paris Dauphine

    Abstract: We study the two player zero-sum Stackelberg game in which the leader interdicts (removes) a limited number of vertices from the graph, and the follower searches for the maximum clique in the interdicted graph. The goal of the leader is to derive an interdiction policy which will result in the worst possible outcome for the follower. This problem has applications in many areas, such as crime detection, prevention of outbreaks of infectious diseases and surveillance of communication networks. We design an exact solution framework basedon a Bilevel Integer Linear Programming model. Thanks to the study of the polytope of the corresponding single-level reformulation, we derive a branch-and-cut algorithm and enhance it by tight combinatorial lower and upper bounds, which also allow for a drastic reduction of the size of the input graph. Our model is based on an exponential family of Clique-Interdiction Cuts whose separation requires solving the maximum clique problem. We derive an effective separation procedure based on a newly developed combinatorial algorithm that is tailored for finding maximum cliques in interdicted graphs. We assess the applicability and the limits of our exact framework on publicly available instances, including large-scale social networks with up to one hundred thousand vertices and three million edges. Most of these instances are solved to provable optimality within short computing times. Our code (which will be also publicly available) allows to analyze the resilience of (social) networks with respect to vertex-interdiction attacks, i.e., the decrease of the size of the maximum clique in function of incremental interdiction budget level.
    Location: Roma, Via dei Taurini 19, Aula Piano Terra
    Date:  December 21, 2018  time 11.30 
    Contact person: Claudio Gentile

  • Strengthening the Sequential Convex MINLP Technique by Perspective Reformulations

    A new paper in collaboration among MINOA partners: CNRS-LIX, University of Pisa, and CNR-IASI.

    Abstract: The Sequential Convex MINLP (SC-MINLP) technique is a solution method for nonconvex Mixed-Integer NonLinear Problems where the nonconvexities are separable. It is based on solving a sequence of convex MINLPs which trade a better and better relaxation of the nonconvex part of the problem with the introduction of more and more piecewise-linear nonconvex terms, and therefore binary variables. The convex MINLPs are obtained by partitioning the domain of each separable nonconvex term in the intervals in which it is convex and those in which it is concave. In the former, the term is left in its original form, while in the latter it is piecewise-linearized. Since each interval corresponds to a semi-continuous variable, we propose to modify the convex terms using the Perspective Reformulation technique to strengthen the bounds. We show by means of experimental results on different classes of instances that doing so significantly decreases the solution time of the convex MINLPs, which is the most time consuming part of the approach, and has therefore the potential to improving the overall effectiveness of the SC-MINLP.

    Keywords: Global Optimization, NonConvex Separable Functions, Sequential Convex MINLP Technique, Perspective Reformulation.

    Cite as: C. D’Ambrosio, A. Frangioni, C. Gentile, Strengthening the Sequential Convex MINLP Technique by Perspective Reformulations, Optimization Letters, to appear, 2018.