Session: Continuous and discreate optimization solving real problems
Chair: Julio C. Góez
Cluster: Interplay Between Continuous and Discrete Optimization
Talk 1: Active constraint indicators in interior point algorithms for conic optimization
Speaker: Alexander Guldemond
Abstract: In conic optimization, determining which constraints are active at a given solution can be crucial information for the user. In this talk, we discuss an approach used by Mosek to predict active conic constraints within the framework of interior point algorithms. It is well known that in the case of the nonnegative orthant, active sets can be predicted by comparing $dx_i / x_i$ to $ds_i / s_i$ for each primal dual variable pair. We extend this technique to generic conic constraints, including non-symmetric cones. At each iteration, we leverage information from both the current iterate and the computed search direction to identify likely active conic constraints. We will present theoretical insights, computational experiments, and discuss the implications for large-scale optimization problems.
Talk 2: A Mixed-Integer Conic Program for the Multi-Pursuer Moving-Target Traveling Salesmen Problem
Speaker: Allen George Philip
Abstract: The Moving-Target Traveling Salesman Problem (MT-TSP) seeks to find a shortest path for a pursuer, that starts at a depot, visits a set of moving targets, and returns to the depot. This problem is motivated by various practical applications such as monitoring and surveillance, intercepting hostile UAVs, and motion planning for industrial robots. We consider the Multi-Pursuer Moving-Target Traveling Salesman Problem (MP-MT-TSP) which generalizes the MT-TSP to include multiple pursuers. We introduce a new Mixed-Integer Conic Program (MICP) for MP-MT-TSP where targets move along piecewise-linear paths. We compare our formulation with the current state-of-the-art MICP for the MP-MT-TSP, and present experimental results demonstrating significant improvements over the state-of-theart in both runtime and optimality ga
Talk 3: Sparse Polynomial Optimization for Water Networks
Speaker: Olga Heijmans-Kuryatnikova
Abstract: In this work we exploit sparsity in polynomial optimization for the valve setting problem in water networks. The valve setting problem consists of many small subproblems involving few variables and monomials and connected with sparse linking constraints. The problem exhibits correlative sparsity (subsets of variables appearing separately in constraints), term sparsity (few monomials present in the problem), and ideal sparsity (size reduction due to equality constraints). We suggest a new simple SDP relaxation that uses all types of sparsity to reach a trade-off between the bound quality and running times. We compare it with the existing sparse SDP relaxations and report numerical results on four water networks ranging in size from 4 to about 2000 nodes. The approach extends to electricity and gas network problems.
