We present column elimination as a general framework for solving (large-scale) integer programming problems. In this framework, solutions are represented compactly as paths in a directed acyclic graph. Column elimination starts with a relaxed representation, that may contain infeasible paths, and solves a constrained network flow over the graph to find a solution. It then … Read more
This tutorial provides an introduction to the use of decision diagrams for solving discrete optimization problems. A decision diagram is a graphical representation of the solution space, representing decisions sequentially as paths from a root node to a target node. By merging isomorphic subgraphs (or equivalent subproblems), decision diagrams can compactly represent an exponential solution … Read more
\(\) In the minimum spanning tree (MST) interdiction problem, we are given a graph \(G=(V,E)\) with edge weights, and want to find some \(X\subseteq E\) satisfying a knapsack constraint such that the MST weight in \((V,E\setminus X)\) is maximized. Since MSTs of \(G\) are the minimum weight bases in the graphic matroid of \(G\), this … Read more
This paper investigates convex quadratic optimization problems involving $n$ indicator variables, each associated with a continuous variable, particularly focusing on scenarios where the matrix $Q$ defining the quadratic term is positive definite and its sparsity pattern corresponds to the adjacency matrix of a tree graph. We introduce a graph-based dynamic programming algorithm that solves this … Read more
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 … Read more
In this paper, a novel approach is presented to address a challenging optimization problem known as Generalized Order Acceptance Scheduling. This problem involves scheduling a set of orders on a single machine with release dates, due dates, deadlines, and sequence-dependent setup times judiciously to maximize revenue. In view of resource constraints, not all orders can … Read more
Recent control algorithms for Markov decision processes (MDPs) have been designed using an implicit analogy with well-established optimization algorithms. In this paper, we make this analogy explicit across four problem classes with a unified solution characterization. This novel framework, in turn, allows for a systematic transformation of algorithms from one domain to the other. In … Read more
Arc routing problems are combinatorial optimization problems that have many real-world applications, such as mail delivery, snow plowing, and waste collection. Various variants of this problem are available, as well as algorithms intended to solve them heuristically or exactly. Presented here is a generic algorithmic framework that can be applied to a variety of arc … Read more
Increasing ocean plastic pollution is irreversibly harming ecosystems and human economic activities. We partner with a non-profit organization and use optimization to help clean up oceans from plastic faster. Specifically, we optimize the route of their plastic collection system in the ocean to maximize the quantity of plastic collected over time. We formulate the problem … Read more
In this paper we introduce a new algorithm for the k-Shortest Simple Paths (k-SSP) problem with an asymptotic running time matching the state of the art from the literature. It is based on a black-box algorithm due to Roddity and Zwick that solves at most 2k instances of the Second Shortest Simple Path (2-SSP) problem … Read more