The Lovasz theta-function is a semidefinite programming (SDP) relaxation for the maximum stable set problem.
In this paper, we develop a novel rounding scheme for the Lovasz theta-function, i.e., a procedure that extracts a stable set from the solution of the SDP. The main idea behind our scheme is to construct a value function approximation from the SDP solution, and then retrieve the stable set by using ideas from dynamic programming. We prove that our method recovers an optimal stable set in almost all perfect graphs. To the best of our knowledge, this is the only known rounding strategy for the Lovasz theta function that provably works on a large class of perfect graphs. Our rounding scheme relies on simple linear algebra computations; a single SDP is solved to construct the value function approximation. In contrast, previous methods for finding an optimal stable set in perfect graphs require solving multiple SDPs. Preliminary computational experiments show that our rounding strategy produces very good solutions for the stable set problem, even on non-perfect graphs.

Mixed-integer linear programs (MILPs) find widespread application in modeling practical problems such as planning and scheduling. A prominent method for solving those MILPs is large neighborhood search (LNS), which iteratively searches for improved solutions within particular neighborhoods of interest. Recent advancements have explored the integration of machine learning techniques into LNS for judiciously guiding users to construct neighborhoods. However, a computational bottleneck still exists in the search step, as it relies on off-the-shelf solvers to optimize auxiliary MILPs of relatively large sizes. In this study, we propose a two-layer LNS (TLNS) approach that leverages LNS to effectively address both the original MILP and its auxiliary MILPs, requiring the optimization of only small-sized MILPs via off-the-shelf solvers.Furthermore, we utilize trained graph neural networks to inform the neighborhood design. We conduct extensive computational experiments using public benchmarks. The results indicate that

We present here mathematical optimization based approaches to optimize the size of different types of mediated graphs. On the one hand, mediated graphs have been proven to be a fundamental tool to represent general p-order cones as second order cones. Given the parameters of a weighted geometric cone, minimizing the cardinality of a (continuous) mediated set for those parameters results in the minimal extended representation of the cone. In this case, we provide a novel Integer Linear Optimization formulation for this problem and provide some insights on the advantages of using our approach against the enumerative approaches that have been previously proposed. On the other hand, (discrete) mediated sets are useful in the determination of minimal representations of circuits by sos polynomials. For this problem, we derive a different and more challenging Integer Linear Optimization model for the problem and analyze different strategies to solve it.

We devise constant-factor approximation algorithms for finding as many disjoint cycles as possible from a certain family of cycles in a given planar or bounded-genus graph. The family of cycles under consideration must satisfy two properties: it must be uncrossable and allow for a certain oracle access.
Our setting generalizes many problems that were studied separately in the past. For example, three families that satisfy the above properties are (i) all cycles in a directed or undirected graph, (ii) all odd cycles in an undirected graph, and (iii) all cycles in an undirected graph that contain precisely one demand edge, where the demand edges form a subset of the edge set. The latter family (iii) corresponds to the classical disjoint paths problem in fully planar and bounded-genus instances.
Furthermore, we obtain approximate min-max theorems of the Erdős-Pósa type.