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 |
EXTENDED ABSTRACTS
| 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.
