Accepted papers

Invited plenary speakers:
Dan Bienstock (Columbia University, USA)
Numerically hard polynomial optimization problems

Marco Sciandrone (Università di Firenze, Italia)
Optimization algorithms for zero-norm minimization

Accepted papers

STANDARD PAPERS (Published in the AIRO-Springer volume “Graphs and Combinatorial Optimization: from Theory to Applications. CTW2020 Proceedings”)

Winfried Hochstaettler and Johanna Wiehe. The Chromatic Polynomial of a Digraph
Josep Diaz, Oznur Yasar Diner, Maria Serna, and Oriol Serra. On List k -Coloring Convex Bipartite Graphs
Ewa Kubicka, Grzegorz Kubicki, Michal Malafiejski, and Krzysztof M. Ocetkiewicz. Total chromatic sum for trees
Subhankar Ghosal and Sasthi Ghosh. An incremental search heuristic for coloring vertices of a graph
Susobhan Bandopadhyay, Sasthi C. Ghosh, and Subhasis Koley. Improved Bounds on the Span of $L(1,2)$-edge Labeling of Some Infinite Regular Grids
Ernst Althaus and Sarah Ziegler. Optimal Tree Decompositions Revisited: A Simpler Linear-Time FPT Algorithm
Hervé Kerivin and Annegret Wagler. On superperfection of edge intersection graphs of paths
Leo Liberti, Gabriele Iommazzo, Carlile Lavor, and Nelson Maculan. A cycle-based formulation for the Distance Geometry Problem
Phillippe Samer and Dag Haugland. The unsuitable neighbourhood inequalities for the fixed cardinality stable set polytope
Lucas Portugal, Renata Del Vecchio, and Simone Dantas. Relating hypergraph parameters of generalized power graphs
Anthony Nixon. Assur decompositions of direction-length frameworks
Michaela Hiller, Arie M.C.A. Koster, and Eberhard Triesch. On the Burning Number of p-Caterpillars
Jan Boeckmann and Clemens Thielen. An Approximation Algorithm for Network Flow Interdiction with Unit Costs and Two Capacities
Tiziano Bacci and Sara Nicoloso. On the benchmark instances for the Bin Packing Problem with Conflicts
Barbara Anthony and Alison Marr. Directed Zagreb Indices
Fernanda Couto, Luis Cunha, and Daniel Posner. Edge Tree Spanners
Sammy Khalife. Sequence graphs: characterization and counting of admissible elements
Lucas Burahem Martins, Manuel Iori, Mayron Cesar O. Moreira, and Giorgio Zucchi. On solving the time window assignment vehicle routing problem via iterated local search
Michele Barbato, Alberto Ceselli, and Nicolas Facchinetti. Synchronized Pickup and Delivery Problems with Connecting FIFO Stack
Aydin Teymourifar, Ana Maria Rodriguesm, and José Soeiro Ferreira. A Comparison Between Simultaneous and Hierarchical Approaches to Solve a Multi-Objective Location-Routing Problem
Manuel Bodirsky, Marcello Mamino, and Caterina Viola. Piecewise Linear Valued Constraint Satisfaction Problems with Fixed Number of Variables
Matteo Cacciola, Antonio Frangioni, Laura Galli, and Giovanni Stea. A Lagrangian approach to Chance Constrained Routing with Local Broadcast
Paolo Detti, Garazi Zabalo Manrique de Lara, and Mario Benini. A metaheuristic apporach for biological sample transportation in healthcare
Diego Maria Pinto and Giuseppe Stecca. Optimal Planning of Waste Sorting Operations through Mixed Integer Linear Programming
Giovanni Micheli, Maria Teresa Vespucci, Marco Stabile, and Alessia Cortazzi. Selecting and Initializing Representative Days for Generation and Transmission Expansion Planning with High Shares of Renewables
Tiziano Bacci, Antonio Frangioni, and Claudio Gentile. Start-up/Shut-down MINLP formulations for the Unit Commitment with Ramp Constraints
Jon Lee, Daphne Skipper, Emily Speakman, and Luze Xu. Gaining or Losing Perspective for Piecewise-Linear Under-Estimators of Convex Univariate Functions
Manuel Aprile, Michele Conforti, Yuri Faenza, Samuel Fiorini, Tony Huynh, and Marco Macchia. Recognizing Cartesian products of matrices and polytopes
Alexander Frank. Special subclass of Generalized Semi-Markov Decision Processes with discrete time
Ruggiero Seccia, Gianmaria Leo, Mehrnoosh Vahdat, Qiannan Gao and Hanadi Wali. Coupling Machine Learning and Integer Programming for Optimal TV Promo Scheduling
Fabricio Mendoza-Granada and Marcos Villagra. A Distributed Algorithm for Spectral Sparsification of Graphs with Applications to Data Clustering


Dmitrii Lozovanu and Stefan Pickl. Optimal Stationary Strategies for Stochastic Control Problems on Networks with Discounted Costs
Michael Souza, Douglas S. Gonçalves, Luiz M. Carvalho, Carlile Lavor, and Leo Liberti. A new algorithm for a class of Distance Geometry problems
Andrei Gagarin and William Kocay. Embedding K5 and K3,3 on orientable surfaces
Deise L. de Oliveira, Simone Dantas, and Atílio G. Luiz. Range-relaxed Graceful Game
Wilder P. Mendes, Simone Dantas, Sylvain Gravier, and Rodrigo Marinho. The monochromatic transversal game on clique-hypergraphs of powers of cycles
Nina Chiarelli, Matjaz Krnc, Martin Milanic, Ulrich Pferschy, Nevena Pivac, and Joachim Schauer. Fair allocation of indivisible goods under conflict constraints
Oliver Bendele and Dieter Rautenbach. Additive Tree $O(\rho\log n)$-Spanners from Tree Breadth $\rho$
Carmen Cecilia Centeno and Lucia Draque Penso. Eventual versus Immediate Spreading: a Full Characterization of Graphs with Coinciding Geodetic and Hull numbers in P_3-convexity
Maurizio Boccia, Adriano Masone, Antonio Sforza, and Claudio Sterle. Exact and heuristic approaches for the optimal welding location problem on the vehicle wiring harness
Maurizio Bruglieri, Daniele Ferone, Paola Festa, and Ornella Pisacane. Efficient solutions for the Green Vehicle Routing Problem with Capacitated Alternative Fuel Stations
Janusz Dybizbański, Hanna Furmańczyk, and Vahan Mkrchyan. Hypergraph aspect in equitable colorings of some block graphs
Grzegorz Kubicki, Ewa Kubicka, Malgorzata Kuchta, and Malgorzata Sulkowska. An Optimal Algorithm for Stopping on the Element Closest to the Center of an Interval
Francesco Carrabs, Raffaele Cerulli, Ciriaco D’Ambrosio, Federico Della Croce, and Monica Gentili. The Interval Transportation Problem with a Cost Matrix Immune against the More-for-Less Paradox
Tobias Oelschlägel and Sigrid Knust. An improved approximation algorithm for storage loading problems with stacking constraints
Juhi Chaudhary and B. S. Panda. On the Complexity of Minimum Maximal Induced Matching
B. S. Panda and Priyamvada Kumar. 1,2,3 conjecture on some subclasses of bipartite graphs
Enrico Bettiol, Lucas Létocart, Francesco Rinaldi, and Emiliano Traversi. A Simplicial Decomposition – Branch and Price for convex quadratic mixed binary problems
Ali Ghezelsoflu, Massimo Di Francesco, Antonio Frangioni, and Paola Zuddas. A multiperiod drayage problem with flexible service periods
Emanuele Tresoldi, Juan José Salazar González, and Roberto Wolfler Calvo. The Multi-color Traveling Salesman Problem
Robert Kozakiewicz, Robert Lewoń, Michał Małafiejski, and Kacper Wereszko. Tight bounds on global edge and complete alliances in trees
Eranda Çela, Vladimir Deineko, and Gerhard J. Woeginger. The Path-TSP: Two solvable cases
Sara Mattia. A graph transformation for the clique interdiction problem with interdicted edges
Mercedes Pelegrín and Claudia D’Ambrosio. Aircraft deconfliction via Mathematical Programming
Alessandro Agnetis, Bo Chen, Gaia Nicosia, and Andrea Pacifici. Fairness-utility trade-off in multi-agent scheduling
Paolo Ventura, Tiziano Bacci, and Sara Mattia. A Robust model for the Restricted Block Relocation Problem
Esteban Salgado and Gustavo Angulo. Forbidden Vertices for some classes of 0-1 polytopes
Mauro Escobar, Claudia D’Ambrosio, Leo Liberti, and Sonia Vanier. Integer Formulation for Computing Transaction Aggregation to Detect Credit Card Fraud
Maurizio Bruglieri, Roberto Cordone, and Leo Liberti. Maximum feasible subsystems of distance geometry constraints
Sonia Haddad Vanier, Céline Gisquel, and Alexandros Papadimitriou. Optimal deployment of security virtual functions in Software-Defined Networks (SDN)
Xavier Ouvrard, Jean-Marie Le Goff, and Stephane Marchand-Maillet. Tuning Ranking With Biased Exchange-Based Diffusion on Hyper-bag-graphs
Wali Mohammad Abdullah, Shahadat Hossain, and Muhammad A. Khan. A Sparse Matrix Approach for Covering Large Complex Networks by Cliques
Renan Spencer Trindade, Claudia D’Ambrosio, Antonio Frangioni, and Claudio Gentile. Comparing Formulations for Piecewise Convex Problems
Esteban Salgado, Claudio Gentile, Giovanni Rinaldi, and Bao Duy Tran. A heuristic for max-cut in toroidal grid graphs

Dan Bienstock (Columbia University, USA)
Numerically hard polynomial optimization problems

It is a simple matter to generate very small instances of QCQPs that prove difficult for numerical solvers. More precisely we are referring to cases where solvers output a solution that is numerically feasible, though slightly infeasible, but is highly superoptimal.  This phenomenon can be described with a clichéd phrase, a little infeasibility buys you a lot of optimality.  The key observation is that this behavior is mild in linear systems, but nontrivial in nonconvex nonlinear settings. We will present several such examples. 
A principal challenge that is manifested by such examples is that many of our convex relaxations arise as hierarchies, with higher members of a hierarchy being proved as more accurate, and it may (will) be the case in these difficult instances that a slightly infeasible and superoptimal solution produced by the solver will be cut-off by a higher-order relaxation (produced, even, by the same solver).  In other words, a superoptimal upper bound for a minimization problem will be cut-off, by a large amount, by a convex relaxation.  
Rather than being an artificial construct, this phenomenon is due to the expressivity of quadratic algebraic inequalities.  We will discuss some classical algebraic background addressing these issues, and also present some recent negative results from ongoing work with Alberto del Pia and Robert Hildebrand.
For example, it is strongly NP-hard to test whether a feasible system of quadratic inequalities with integer coefficients has a rational solution.  It is also strongly NP-hard to test whether a system of quadratic inequalities with integer coefficients, that has rational solutions, also has a rational solution expressible using a polynomial number of bits.

Marco Sciandrone (Università di Firenze, Italy)
Optimization algorithms for zero-norm minimization

In this talk we consider sparse optimization problems involving
the so-called zero-norm function that counts the number of non-zero components in a vector. The considered optimization problems are central in important fields like, for instance, machine learning and computer vision. We focus on problems where the zero-norm is a part of objective function or constraints. We present continuous optimization algorithms based on smoothing techniques when the objective function
is the zero-norm, and on penalty decomposition approaches for problems where the zero-norm is a part of constraints. Concerning this latter class of problems, we also describe an algorithm based on mixed integer nonlinear programming. We analyze theoretical issues and we discuss computational results.