## A MILP Approach to DRAM Access Worst-Case Analysis

The Dynamic Random Access Memory (DRAM) is among the major points of contention in multi-core systems. We consider a challenging optimization problem arising in worst-case performance analysis of systems architectures: computing the worst-case delay (WCD) experienced when accessing the DRAM due to the interference of contending requests. The WCD is a crucial input for micro-architectural … Read more

## Decomposition Methods for Global Solutions of Mixed-Integer Linear Programs

This paper introduces two decomposition-based methods for two-block mixed-integer linear programs (MILPs), which aim to take advantage of separable structures of the original problem by solving a sequence of lower-dimensional MILPs. The first method is based on the $\ell_1$-augmented Lagrangian method (ALM), and the second one is based on a modified alternating direction method of … Read more

## On the Complexity of Inverse Mixed Integer Linear Optimization

Inverse optimization is the problem of determining the values of missing input parameters that are closest to given estimates and that will make a given solution optimal. This study is concerned with the relationship of a particular inverse mixed integer linear optimization problem (MILPs) to both the original problem and the separation problem associated with … Read more

## Accelerating Domain Propagation: an Efficient GPU-Parallel Algorithm over Sparse Matrices

Fast domain propagation of linear constraints has become a crucial component of today’s best algorithms and solvers for mixed integer programming and pseudo-boolean optimization to achieve peak solving performance. Irregularities in the form of dynamic algorithmic behaviour, dependency structures, and sparsity patterns in the input data make efficient implementations of domain propagation on GPUs and, … Read more

## A Comparison of two Mixed-Integer Linear Programs for Piecewise Linear Function Fitting

The problem of fitting continuous piecewise linear (PWL) functions to discrete data has applications in pattern recognition and engineering, amongst many others. To find an optimal PWL function, it is required that the positioning of the breakpoints connecting adjacent linear segments are not constrained, and are allowed to be placed freely. While the PWL fitting … Read more

## The SCIP Optimization Suite 7.0

The SCIP Optimization Suite provides a collection of software packages for mathematical optimization centered around the constraint integer programming framework SCIP. This paper discusses enhancements and extensions contained in version 7.0 of the SCIP Optimization Suite. The new version features the parallel presolving library PaPILO as a new addition to the suite. PaPILO 1.0 simplifies … Read more

## A K-Nearest Neighbor Heuristic for Real-Time DC Optimal Transmission Switching

While transmission switching is known to reduce power generation costs, the difficulty of solving even DC optimal transmission switching (DCOTS) has prevented optimal transmission switching from becoming commonplace in real-time power systems operation. In this paper, we present a k-nearest neighbors (KNN) heuristic for DCOTS which relies on the insight that, for routine operations on … Read more

## Testing Copositivity via Mixed-Integer Linear Programming

We describe a simple method to test if a given matrix is copositive by solving a single mixed-integer linear programming (MILP) problem. This methodology requires no special coding to implement and takes advantage of the computational power of modern MILP solvers. Numerical experiments demonstrate that the method is robust and efficient. Citation Dept. of Business … Read more

## On the propagation of quality requirements for mechanical assemblies in industrial manufacturing

A frequent challenge encountered by manufacturers of mechanical assemblies consists of the definition of quality criteria for the assembly lines of the subcomponents which are mounted into the final product. The rollout of Industry 4.0 standards paves the way for the usage of data-driven, intelligent approaches towards this goal. In this work, we investigate such … Read more

## Mixed-Integer Linear Programming for Scheduling Unconventional Oil Field Development

The scheduling of drilling and hydraulic fracturing of wells in an unconventional oil field plays an important role in the profitability of the field. A key challenge arising in this problem is the requirement that neither drilling nor oil production can be done at wells within a specified neighborhood of a well being fractured. We … Read more