Margarita P Castro

Beyond Hand-Derived Inequalities: Decision Diagrams for Cut Generation in Binary Polynomial Optimization

Categories 0-1 Programming, Cutting Plane Approaches, Integer Programming Tags , ,

We study cutting-plane generation for binary polynomial optimization (BPO), whose feasible region is the multilinear set of a hypergraph. Strong inequalities for this set—such as two-links, flowers, and odd $\beta$-cycles—are classically hand-derived for fixed support patterns. Instead, we propose a decision-diagram (DD) approach: for any chosen support, it separates a facet-defining cut in the local … Read more

Exact and approximate formulations for the close-enough TSP

Categories (Mixed) Integer Nonlinear Programming, Branch and Cut Algorithms Tags , ,

This work addresses the Close-Enough Traveling Salesman Problem (CETSP), a variant of the classic traveling salesman problem in which we seek to visit neighborhoods of points in the plane (defined as disks) rather than specific points. We present two exact formulations for this problem based on second-order cone programming (SOCP), along with approximated mixed-integer linear … Read more

A Decision Diagram Approach for the Parallel Machine Scheduling Problem with Chance Constraints

Categories Branch and Cut Algorithms, Scheduling, Stochastic Programming Tags , ,

The Chance-Constrained Parallel Machine Scheduling Problem (CC-PMSP) assigns jobs with uncertain processing times to machines, ensuring that each machine’s availability constraints are met with a certain probability. We present a decomposition approach where the master problem assigns jobs to machines, and the subproblems schedule the jobs on each machine while verifying the solution’s feasibility under … Read more

Incorporating Service Reliability in Multi-depot Vehicle Scheduling: A Chance-Constrained Approach

Categories Cutting Plane Approaches, Stochastic Programming, Transportation Tags , , ,

The multi-depot vehicle scheduling problem (MDVSP) is a critical planning challenge for transit agencies. We introduce a novel approach to MDVSP by incorporating service reliability through chance-constrained programming (CCP), targeting the pivotal issue of travel time uncertainty and its impact on transit service quality. Our model guarantees service reliability measured by on-time performance (OTP), a … Read more

Markov Chain-based Policies for Multi-stage Stochastic Integer Linear Programming with an Application to Disaster Relief Logistics

Categories (Mixed) Integer Linear Programming, Stochastic Programming Tags , , , ,

We introduce an aggregation framework to address multi-stage stochastic programs with mixed-integer state variables and continuous local variables (MSILPs). Our aggregation framework imposes additional structure to the integer state variables by leveraging the information of the underlying stochastic process, which is modeled as a Markov chain (MC). We demonstrate that the aggregated MSILP can be … Read more

Decision Diagrams for Discrete Optimization: A Survey of Recent Advances

Categories Combinatorial Optimization, Integer Programming, Network Optimization Tags ,

In the last decade, decision diagrams (DDs) have been the basis for a large array of novel approaches for modeling and solving optimization problems. Many techniques now use DDs as a key tool to achieve state-of-the-art performance within other optimization paradigms, such as integer programming and constraint programming. This paper provides a survey of the … Read more

A Combinatorial Cut-and-Lift Procedure with an Application to 0-1 Chance Constraints

Categories 0-1 Programming, Cutting Plane Approaches, Second-Order Cone Programming Tags , , ,

Cut generation and lifting are key components for the performance of state-of-the-art mathematical programming solvers. This work proposes a new general cut-and-lift procedure that exploits the combinatorial structure of 0-1 problems via a binary decision diagram (BDD) encoding of their constraints. We present a general framework that can be applied to a large range of … Read more