Combinatorial Optimization & Network Flows

← Back to Domain-Specific Families

Abstractions about solving discrete and continuous optimization problems over graphs, matrices, flows, cuts, and assignments. They include local and metaheuristic search, relaxations, satisfiability, routing, matching, cutting and packing, Pareto fronts, and submodular structure.

24 abstractions in this family — domain-specific abstractions that sit near one another in structural-signature space (k-means over structural-signature embeddings). Each is shown with its short description.

• 3-dimensional matching — A matching in a tripartite 3-uniform hypergraph: a set of triples no two of which share any coordinate, with optimization and perfect-decision variants.
• Algebraic modeling language — A high-level language for expressing optimization models in index-based algebraic notation while separating mathematical structure from data and solver implementation.
• Ant colony optimization algorithms — A population metaheuristic in which stochastic construction agents reinforce useful graph choices through shared, evaporating pheromone values.
• Balanced matrix — A binary matrix containing no odd-order square submatrix in which every row and column has exactly two ones.
• Bilinear program — A nonlinear optimization problem whose objective or constraints contain products that are linear in either variable block when the other is fixed.
• Circulation problem — A network-flow feasibility or optimization problem assigning edge flows within lower and upper bounds while conserving flow at every vertex.
• Closure problem — The optimization problem of selecting a maximum-weight vertex set in a directed graph subject to the rule that selecting a vertex also selects every vertex reachable along its outgoing dependencies.
• Guillotine cutting — A rectangular stock-cutting constraint in which every cut must pass straight from one edge of the current rectangular piece to the opposite edge, recursively partitioning it into two rectangles.
• Local search (optimization) — A heuristic optimization method that repeatedly moves to neighboring candidate solutions using local objective information.
• Matroid parity problem — The optimization problem of selecting the largest collection of prescribed element pairs whose union is independent in a matroid.
• Maximum satisfiability problem — The optimization problem of assigning Boolean variables to maximize the number or total weight of satisfied clauses in a conjunctive normal form formula.
• Minimum-cost flow problem — The optimization problem of routing a required amount of flow through a capacitated network while satisfying conservation and minimizing total edge cost.
• Multi-commodity flow problem — Route multiple source–sink commodities through one capacitated network while each commodity obeys flow conservation and all commodities jointly share edge capacities, optimizing congestion, cost, or satisfied demand.
• Multifit algorithm — An approximation algorithm for identical-machine makespan scheduling that repeatedly runs first-fit-decreasing bin packing while binary-searching a trial capacity.
• Pareto front — The set of feasible objective vectors or solutions not dominated by any alternative in a multi-objective optimization problem.
• Particle swarm optimization — A population-based optimization method in which candidate positions move through a search space using their own best experience and information from a neighborhood or global best.
• Prune and search — An optimization technique that repeatedly discards a guaranteed constant fraction of candidate input while preserving at least one optimum, then recurses on the remainder.
• Quasi-bipartite graph — A Steiner-tree instance in which the nonterminal vertices form an independent set, so every edge has at least one terminal endpoint.
• Relaxation (approximation) — The replacement of a difficult optimization problem by an easier problem with weakened constraints or simplified structure whose solution bounds or informs the original.
• Semi-infinite programming — Optimization with finitely many decision variables and infinitely many constraints, or dually infinitely many variables and finitely many constraints.
• Set TSP problem — A traveling-salesman generalization seeking a minimum-cost tour that visits at least one vertex from every specified group.
• Shortest path problem — The optimization problem of finding a path between specified graph vertices whose accumulated edge or path weight is minimal among all admissible paths.
• Steiner tree problem — The optimization problem of connecting specified terminal points at minimum total cost while permitting additional intermediate Steiner points or vertices.
• Submodular flow — A combinatorial optimization problem that minimizes linear flow cost subject to edge bounds and submodular constraints on net flow across every vertex subset.