We introduce a novel technique to generate Benders’ cuts from a conic relaxation (corner) derived from a basis of a higher-dimensional polyhedron that we aim to outer approximate in a lower-dimensional space. To generate facet-defining inequalities for the epigraph associated with this corner, we develop a computationally-efficient algorithm based on a compact reverse polar formulation and a row generation scheme that handles the redundant inequalities. Via a known connection between arc-flow and path-flow formulations, we show that our method can recover the linear programming bound of a Dantzig-Wolfe formulation using multiple cuts in the projected space. In computational experiments, our generic technique enhances the performance of a problem-specific state-of-the-art algorithm for the vehicle routing problem with stochastic demands (VRPSD), a well-studied variant of the classic capacitated vehicle routing problem that accounts for customer demand uncertainty. This is a joint work with Ricardo Fukasawa, Aleksandr M. Kazachkov. Preprint https://arxiv.org/abs/2509.21758

In this talk, we introduce and analyze the Forest Cover problem, a generalization of the classical Vertex Cover problem. The objective is to find a vertex cover C⊆V and a spanning forest F on C such that the weighted index defined as the sum of edge weights in the forest plus the number of connected components is minimized. We present an exponentially sized integer programming formulation for this problem and show that it can be solved in polynomial time via a separation oracle. We provide two primary algorithmic results first, a deterministic 2-approximation algorithm for instances with binary edge weights (we∈{0,1}) using a graph decomposition technique; and second, a probabilistic (3+ϵ)-approximation algorithm for the general case where weights lie in the interval [0,1]. The latter is achieved through a randomized sampling method, utilizing Chernoff-Hoeffding bounds and dual fitting to show that an average of sampled binary instances provides a high-probability approximation for the continuous weight case. The technique developed here might be of independent interest. This is joint work with Barun Gorain, Shaswati Patra and Rishi Ranjan Singh.

O problema da Cobertura Mínima por Varredura (MSC) escalona as comunicações par-a-par em enxames de satélites usando antenas direcionais. Satélites são pontos no espaço Euclidiano e os custos de alinhamento são proporcionais aos ângulos de rotação. O objetivo é minimizar o tempo total necessário para completar as conexões descritas como arestas de um grafo de entrada. Aproximar o MSC por um fator constante é NP-difícil, mesmo no caso 1D; portanto, recorremos uma parametrização pela largura arbórea. Para instâncias 1D, fornecemos um algoritmo exato de tempo FPT linear. Para 2D, introduzimos o ângulo mínimo não nulo de troca entre vizinhos como segundo parâmetro para projetar uma 2-aproximação de tempo FPT linear.

The generation of graphs and networks with specific characteristics is an important line of research with many potential uses, such as testing optimization algorithms in real-world scenarios and studying dynamic processes in networks. However, existing network models often rely on global knowledge of the network structure or fail to simultaneously capture key characteristics of real networks, such as high local clustering, small-world behavior, and long-tailed degree distributions. The goal of this study is to develop an efficient and flexible network-generation algorithm capable of reproducing the structural properties commonly observed in real-world networks using only local information. We will propose and evaluate a locally driven network-generation mechanism designed to produce realistic network topologies while remaining computationally scalable. The study includes a systematic analysis of existing network-generation algorithms, the development of a novel generation method, and an investigation of its ability to control key structural features, including clustering coefficients, average distances, and degree distributions. The resulting algorithm will be extensively evaluated through simulations and comparative analyses against established models and real-world network data. Finally, the developed method is released as an open-source software package to facilitate its adoption, support reproducibility, and strengthen further research.