dynamic programming – Optimization Online

A tight 1/3–approximation algorithm and fully polynomial-time approximation schemes for the Colored Knapsack Problem

Published: 2026/09/30

Approximation Algorithms, Combinatorial Optimization, Dynamic Programming approximation algorithms, dynamic programming, fully polynomial-time approximation schemes, knapsack problem

The $\textit{Colored Knapsack Problem}$ (ColKP) generalizes the classical Knapsack Problem by partitioning the items into color classes and requiring the selected items to admit an ordering in which consecutive items have different colors. The problem is weakly $\mathcal{NP}$-hard and admits two pseudo-polynomial dynamic programming (DP) algorithms proposed in the literature. These two DP algorithms have … Read more

Treewidth and the complexity of box-constrained quadratic programs

Published: 2026/09/28

Global Optimization Theory, Quadratic Programming box-constrained quadratic programming, dynamic programming, polynomial-time algorithm, sparsity, treewidth

We consider the problem of minimizing a sparse quadratic function over the unit hypercube. In binary quadratic programming, treewidth of the interaction graph is a central parameter for tractability: bounded treewidth yields polynomial-time solvability. Motivated by this fact, we investigate whether treewidth plays a similar role when the binary domain is replaced by the unit … Read more

A Numerically-safe Branch-Price-and-Cut Algorithm for the Length-Constrained Cycle Partition Problem

Published: 2026/07/20

(Mixed) Integer Linear Programming, Applications - OR and Management Sciences, Dynamic Programming bidirectional search, branch-price-and-cut, cycle partitioning, dynamic programming, Numerical Safety

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

Prophets in Parallel: Dynamic Cut Minimization in Series-Parallel Graphs

Published: 2026/05/24

Combinatorial Optimization, Dynamic Programming approximate linear programming, dynamic programming, optimal stopping, Prophet Inequalities

We introduce a sequential version of the minimum $s$-$t$ cut problem, defined by a directed graph with source $s$ and sink $t$, and nonnegative random variables for each arc representing arc weights. We start with a working set $S = \{s\}$ and observe weight realizations for outgoing arcs from $S$ only. We choose to either … Read more

Solving Convex Quadratic Optimization with Indicators Over Structured Graphs

Published: 2026/03/02

(Mixed) Integer Nonlinear Programming, Dynamic Programming dynamic programming, mixed-integer programming

This paper studies convex quadratic minimization problems in which each continuous variable is coupled with a binary indicator variable. We focus on the structured setting where the Hessian matrix of the quadratic term is positive definite and exhibits sparsity. We develop an exact parametric dynamic programming algorithm whose computational complexity depends explicitly on the treewidth … Read more

The colored knapsack problem: structural properties and exact algorithms

Published: 2026/02/13

(Mixed) Integer Linear Programming, Combinatorial Optimization, Dynamic Programming combinatorial optimization, computational experiments, dynamic programming, integer linear programming, knapsack problem

We introduce and study a novel generalization of the classical Knapsack Problem (KP), called the Colored Knapsack Problem (CKP). In this problem, the items are partitioned into classes of colors and the packed items need to be ordered such that no consecutive items are of the same color. We establish that the problem is weakly … Read more

Isotonic Optimization with Fixed Costs

Published: 2025/08/31

(Mixed) Integer Nonlinear Programming, Dynamic Programming, Supply Chain Management arborescence, dynamic programming, fixed costs, isotonic optimization

This paper introduces a generalized isotonic optimization framework over an arborescence graph, where each node incurs state-dependent convex costs and a fixed cost upon strict increases. We begin with the special case in which the arborescence is a path and develop a dynamic programming (DP) algorithm with an initial complexity of $O(n^3)$, which we improve … Read more

Multi-Stage Selection under Bounded Variation

Published: 2025/03/01, Updated: 2026/01/16

0-1 Programming, Dynamic Programming 0-1 integer programming, bounded variation, dynamic programming, Multi-Stage Optimization, Selection Problem

We investigate a multi-stage version of the selection problem where the variation between solutions in consecutive stages is either penalized in the objective function or bounded by hard constraints. While the former problem turns out to be tractable, the complexity of the latter problem depends on the type of bounds imposed: When bounding the number … Read more

Column Elimination: An Iterative Approach to Solving Integer Programs

Published: 2024/10/15

Branch and Cut Algorithms, Dynamic Programming, Integer Programming column elimination, column generation, decision diagrams, dynamic programming, integer programming, network flows

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

An Introduction to Decision Diagrams for Optimization

Published: 2024/09/23

Willem-Jan van Hoeve

Combinatorial Optimization, Dynamic Programming, Integer Programming Branch-and-Bound, constraint programming, decision diagrams, discrete optimization, dynamic programming, integer programming, network flows

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