Total Coloring and Total Matching: Polyhedra and Facets

A total coloring of a graph G = (V, E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive different colors. Any valid total coloring induces a partition of the … Read more

The Stochastic Pseudo-Star Degree Centrality Problem

We introduce the stochastic pseudo-star degree centrality problem, which focuses on a novel probabilistic group-based centrality metric. The goal is to identify a feasible induced pseudo-star, which is defined as a collection of nodes forming a star network with a certain probability, such that it maximizes the sum of the individual probabilities of unique assignments … Read more

Algorithms for the Clique Problem with Multiple-Choice Constraints under a Series-Parallel Dependency Graph

The clique problem with multiple-choice constraints (CPMC), i.e. the problem of finding a k-clique in a k-partite graph with known partition, occurs as a substructure in many real-world applications, in particular scheduling and railway timetabling. Although CPMC is NP-complete in general, it is known to be solvable in polynomial time when the so-called dependency graph … Read more

Total Coloring and Total Matching: Polyhedra and Facets

A total coloring of a graph G = (V, E) is an assignment of colors to vertices and edges such that neither two adjacent vertices nor two incident edges get the same color, and, for each edge, the end-points and the edge itself receive a different color. Any valid total coloring induces a partition of … Read more

Political districting to minimize cut edges

When constructing political districting plans, prominent criteria include population balance, contiguity, and compactness. The compactness of a districting plan, which is often judged by the “eyeball test,” has been quantified in many ways, e.g., Length-Width, Polsby-Popper, and Moment-of-Inertia. This paper considers the number of cut edges, which has recently gained traction in the redistricting literature … Read more

Solving Bang-Bang Problems Using The Immersed Interface Method and Integer Programming

In this paper we study numerically solving optimal control problems with bang-bang control functions. We present a formal Lagrangian approach for solving the optimal control problem, and address difficulties encountered when numerically solving the state and adjoint equations by using the immersed interface method. We note that our numerical approach does not approximate the discontinuous … Read more

Lower Bounds on the Size of General Branch-and-Bound Trees

A \emph{general branch-and-bound tree} is a branch-and-bound tree which is allowed to use general disjunctions of the form $\pi^{\top} x \leq \pi_0 \,\vee\, \pi^{\top}x \geq \pi_0 + 1$, where $\pi$ is an integer vector and $\pi_0$ is an integer scalar, to create child nodes. We construct a packing instance, a set covering instance, and a … Read more

A tailored Benders decomposition approach for last-mile delivery with autonomous robots

This work addresses an operational problem of a logistics service provider that consists of finding an optimal route for a vehicle carrying customer parcels from a central depot to selected facilities, from where autonomous devices like robots are launched to perform last-mile deliveries. The objective is to minimize a tardiness indicator based on the customer … Read more

A Comparative Study of Stability Representations for Solving Many-to-One Matching Problems with Utility-Weighted Objectives, Ties, and Incomplete Lists via Integer Optimization

We consider integer optimization models for finding stable solutions to many-to-one, utility-weighted matching problems with incomplete preference lists and ties. While traditional algorithmic approaches for the stable many-to-one matching problem, such as the Deferred Acceptance algorithm, offer efficient performance for the strict problem setting, adaptation to alternative settings often requires careful customization. Optimization-based approaches are … Read more

Graph Coloring with Decision Diagrams

We introduce an iterative framework for solving graph coloring problems using decision diagrams. The decision diagram compactly represents all possible color classes, some of which may contain edge conflicts. In each iteration, we use a constrained minimum network flow model to compute a lower bound and identify conflicts. Infeasible color classes associated with these conflicts … Read more