We propose an exact algorithm for the Graph Burning Problem (GBP), an NP-hard optimization problem that models the spread of influence on social networks. Given a graph G with vertex set V, the objective is to find a sequence of k vertices in V, namely, v₁, v₂, … , v_k, such that k is minimum and ⋃_{i=1}^{k} {u∈V: d(u,v_i) ≤ k-i} = V, where d(u,v) denotes the distance between u and v. We formulate the problem as a set covering integer programming model and design a row generation algorithm for the GBP. Our method exploits the fact that a very small number of covering constraints is often sufficient for solving the integer model, allowing the corresponding rows to be generated on demand. To date, the most efficient exact algorithm for the GBP, denoted here by GDCA, is able to obtain optimal solutions for graphs with up to 14,000 vertices within two hours of execution. In comparison, our algorithm finds provably optimal solutions approximately 236 times faster, on average, than GDCA. For larger graphs, memory space becomes a limiting factor for GDCA. Our algorithm, however, solves real-world instances with more than 3 million vertices in less than 19 minutes, increasing the size of graphs for which optimal solutions are known by a factor of 200. Additionally, we conduct tests on the proposed algorithm using a series of challenging instances composed of grid graphs containing up to 5,000 vertices. As a result, we achieve novel optimal solutions and tight optimality gaps that have not been previously reported in the literature.

Recent research in hybrid optimization shows that a combination of technologies that exploits their complementary strengths can significantly speed up computation. The use of high-level metaconstraints in the problem formulation can achieve a substantial share of these computational gains by better communicating problem structure to the solver. During the solution process, however, metaconstraints give rise to reformulations or relaxations that introduce auxiliary variables, and some of the variables in one metaconstraint’s reformulation may be functionally the same as or related to variables in another metaconstraint’s reformulation. These relationships must be recognized to obtain a tight overall relaxation. We propose a modeling scheme based on semantic typing that systematically addresses this problem while providing simpler, self-documenting models. It organizes the model around predicates and declares variables by associating each with a predicate through a keyword that is analogous to a database query. We present a series of examples to illustrate this idea over a wide variety of applications.

Proportional symbol maps are a cartographic tool to assist in the visualization and analysis of quantitative data associated with specific locations, such as earthquake magnitudes, oil well production, and temperature at weather stations. As the name suggests, symbol sizes are proportional to the magnitude of the physical quantities that they represent. We present two novel integer linear programming (ILP) models to solve this computational geometry problem: how to draw opaque disks on a map so as to maximize the total visible border of all disks. We focus on drawings obtained by layering symbols on top of each other, also known as stacking drawings. We introduce decomposition techniques as well as several families of facet-defining inequalities, which are used to strengthen the ILP models that are supplied to a commercial solver. We demonstrate the effectiveness of our approach through a series of computational experiments using hundreds of instances generated from real demographic and geophysical data sets. To the best of our knowledge, we are the first to use ILP to tackle this problem, and the first to provide provably optimal symbol maps for those data sets.