Water Finds its Level: A Localized Method for Multicommodity Flow Problem

This paper describes a local-control method for multicommodity flow problem. Both the capacity constraints and the flow conservation constraints are relaxed. If the flow exceeds the capacity on an edge, the edge would have a congestion cost. If the flow into a vertex is not equal to that out of the vertex, the vertex would … Read more

D-optimal Data Fusion: Exact and Approximation Algorithms

We study the D-optimal Data Fusion (DDF) problem, which aims to select new data points, given an existing Fisher information matrix, so as to maximize the logarithm of the determinant of the overall Fisher information matrix. We show that the DDF problem is NP-hard and has no constant-factor polynomial-time approximation algorithm unless P = NP. … Read more

CliSAT: a SAT-based exact algorithm for hard maximum clique problems

Given a graph, the maximum clique problem (MCP) asks for determining a complete subgraph with the largest possible number of vertices. We propose a new exact algorithm, called CliSAT, to solve the MCP to proven optimality. This problem is of fundamental importance in graph theory and combinatorial optimization due to its practical relevance for a … 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

A new branch-and-filter exact algorithm for binary constraint satisfaction problems

A binary constraint satisfaction problem (BCSP) consist in determining an assignment of values to variables which is compatible with a set of constraints. The problem is called binary because the constraints involve only pairs of variables. The BCSP is a cornerstone problem in Constraint Programming (CP), appearing in a very wide range of real-world applications. … Read more

Migration from Sequence to Schedule in Total Earliness and Tardiness Scheduling Problem

Services must be delivered with high punctuality to be competitive. The classical scheduling theory offers to minimize the total earliness and tardiness of jobs to deliver punctual services. In this study, we developed a fully polynomial-time optimal algorithm to transform a given sequence, the permutation of jobs, into its corresponding minimum cost schedule, the timing … Read more

A Column and Constraint Algorithm for the Dynamic Knapsack Problem with Stochastic Item Sizes

We consider a version of the knapsack problem in which an item size is random and revealed only when the decision maker attempts to insert it. After every successful insertion the decision maker can choose the next item dynamically based on the remaining capacity and available items, while an unsuccessful insertion terminates the process. We … Read more

Dynamic programming algorithms, efficient solution of the LP-relaxation and approximation schemes for the Penalized Knapsack Problem

We consider the 0-1 Penalized Knapsack Problem (PKP). Each item has a profit, a weight and a penalty and the goal is to maximize the sum of the profits minus the greatest penalty value of the items included in a solution. We propose an exact approach relying on a procedure which narrows the relevant range … Read more

A Practical Iterative Algorithm for the Art Gallery Problem using Integer Linear Programming

In the last few decades, the search for exact algorithms for known NP-hard geometric problems has intensified. Many of these solutions make use of Integer Linear Programming (ILP) modeling and rely on state of the art solvers, to be able to find optimal solutions for large instances in a matter of minutes. In this work, … Read more