The length-constrained cycle partition problem (LCCP) is a graph optimization problem in which a set of nodes must be partitioned into a minimum number of cycles. Every node is associated with a critical time and the length of every cycle must not exceed the critical time of any node in the cycle. We formulate LCCP as a set partitioning model and solve it using an exact branch-and-price approach. We use a dynamic programming-based pricing algorithm to generate improving cycles, exploiting the particular structure of the pricing problem for efficient bidirectional search and symmetry breaking. Computational results show that the LP relaxation of the set partitioning model produces strong dual bounds and our branch-and-price method improves significantly over the state of the art. It is able to solve closed instances in a fraction of the previously needed time and closes 13 previously unsolved instances, one of which has 76 nodes, a notable improvement over the previous limit of 52 nodes.

The Maximum k-Vertex Cover (Max k-VC) problem involves finding a subset of at most k vertices in an undirected graph G to maximize the number of covered edges. The need for the Max k-VC problems arises in various fields, such as system risk management, network robustness measurement, and airplane seating assignment. In this research, we focus on developing cutting plane strategies for solving this problem exactly. We begin by studying the polytope associated with the integer programming formulation of the Max k-VC problem. In particular, we prove that certain facet-defining inequalities for the polytope can be derived from those for the projected and low-dimensional polytopes obtained by restricting G to its subgraphs. Based on this insight, we propose three families of strong valid inequalities for the Max k-VC problem, utilizing different structured subgraphs including odd cycles, cliques, and generalized stars. We also provide necessary and sufficient conditions for these inequalities to be facet-defining, and discuss the corresponding separation problems. Finally, we integrate the proposed valid inequalities as cutting planes into the branch-and-bound algorithm of CPLEX, a widely used state-of-the-art integer programming solver. Extensive computational results demonstrate the effectiveness of incorporating these cutting planes for solving the Max k-VC problems, in terms of strengthening the linear programming relaxation and improving the solution efficiency.

In this talk, we present an approach for the integrated layout and cable routing problem of onshore wind farm planning using the Quota Steiner tree problem (QSTP). We present a transformation of the QSTP that significantly outperforms standard out-of-the-box MIP solvers in the context of regional wind farm planning. Secondly, we show that solving integrated layout and cable routing problem can lead to up to 20\% cost reduction compared to a sequential approach. Finally, we explore the possibilities of extending the QSTP formulation by relevant technical constraints such that our approach becomes applicable to the design of a single wind farm.

This paper introduces a novel compact mixed integer linear programming (MILP) formulation and a discretization discovery-based solution approach for the Vehicle Routing Problem with Time Windows (VRPTW). We aim to solve the optimization problem efficiently by constraining the linear programming (LP) solutions to use only flows corresponding to time and capacity-feasible routes that are locally elementary (prohibiting cycles of customers localized in space).

We employ a discretization discovery algorithm to refine the LP relaxation iteratively. This iterative process alternates between two steps: (1) increasing time/capacity/elementarity enforcement to increase the LP objective, albeit at the expense of increased complexity (more variables and constraints), and (2) decreasing enforcement without decreasing the LP objective to reduce complexity. This iterative approach ensures we produce an LP relaxation that closely approximates the optimal MILP objective with minimal complexity, facilitating an efficient solution via an off-the-shelf MILP solver.

The effectiveness of our method is demonstrated through empirical evaluations on classical VRPTW instances. We showcase the efficiency of solving the final MILP and multiple iterations of LP relaxations, highlighting the decreased integrality gap of the final LP relaxation. We believe that our approach holds promise for addressing a wide range of routing problems within and beyond the VRPTW domain.