A Graph-Based Approach for Relating Integer Programs

This paper presents a framework for classifying and comparing instances of integer linear programs (ILPs) based on their mathematical structure. It has long been observed that the structure of ILPs can play an important role in determining the effectiveness of certain solution techniques; those that work well for one class of ILPs are often found to be effective in solving similarly structured problems. In this work, the structure of a given ILP instance is captured via a graph-based representation, where decision variables and constraints are described by nodes, and edges denote the presence of decision variables in certain constraints. Using machine learning techniques for graph-structured data, we introduce two approaches for leveraging the graph representations for relating ILPs. In the first approach, a graph convolutional network (GCN) is used to classify ILP graphs as having come from one of a known number of problem classes. The second approach makes use of latent features learned by the GCN to compare ILP graphs to one another directly. As part of the latter approach, we introduce a formal measure of graph-based structural similarity. A series of empirical studies indicate strong performance for both the classification and comparison procedures. Additional properties of ILP graphs, namely, losslessness and permutation invariance, are also explored via computational experiments. Download the paper (free) | GitHub Data/Code

Auto-generating Solver Code (tex2solver)

tex2solver makes it easy to transfer LaTeX-typeset optimization models to programming code for use in a solver. Simply copy-and-paste your LaTeX code (or take a screenshot of your model), then choose your desired solver and programming language. tex2solver will generate the code you need to be able to solve instances of your model. With tex2solver, it's easy to keep your math model and solver code in sync. tex2solver currently works with PuLP, but support for other popular solvers (including CPLEX and Gurobi) is forthcoming. Visit tex2solver.com to get started for free.

Vehicle Routing Visualization (VeRoViz)

This open-source software package, for Python and with web-based components, is designed to help vehicle routing researchers easily create test problems, generate time and distance matrices, and visualize solutions with dynamic 3D movies. Visit veroviz.org for installation instructions, documentation, and examples.

Image-based Comparison of Mixed Integer Linear Programs (MILPs)

Operations researchers have long drawn insight from the structure of constraint coefficient matrices (CCMs) for mixed integer programs (MIPs). We propose a new question - can pictorial representations of CCM structure be used to identify similar MIP models and instances? In this paper, CCM structure is visualized using digital images, and computer vision techniques are employed to detect latent structural features therein. The resulting feature vectors are used to measure similarity between images and, consequently, MIPs. An introductory analysis examines the collection of instances in MIPLIB 2017, an online repository for MIP instances. Results indicate that structure-based comparisons may allow for relationships to be identified between MIPs from disparate application areas. Additionally, image-based comparisons reveal that ostensibly similar variations of an MIP model may yield instances with markedly different mathematical structures. Download Paper | Visit Companion Website

UAVs in Logistics

The Optimator Lab has been working on drone-assisted last-mile delivery for over a decade, starting with The Flying Sidekick Traveling Salesman Problem (2015). Since then, the lab has produced several extensions:

• The Multiple Flying Sidekicks Traveling Salesman Problem (mFSTSP) | GitHub Repo
• mFSTSP with Variable Drone Speeds | GitHub Repo
• The Time-Dependent Multiple Flying Sidekicks Traveling Salesman Problem
• Drone Scheduling with Weather Considerations

Mission Planning and Dynamic Re-planning

This research considers an optimal allocation problem for a fleet of UAVs that must perform individual tasks in support of overall mission objectives. Each task may be prioritized, and each UAV may have unique capabilities/limitations. New algorithms have been developed to determine which UAVs should perform each task. In the event of changes in battlespace conditions, re-planning algorithms determine updated mission plans that balance the objectives of maximizing overall mission effectiveness while minimizing changes to the initial plans.

Incorporating the Human Element in UAV Tasking

UAVs, while unmanned, still require significant human interaction. For example, each Predator requires three human operators on the ground. Future operations are expected to require a single operator to manage multiple UAVs simultaneously. Mission success may be compromised if operators are tasked to perform an excessive number of tasks concurrently. We have developed new mathematical programming models to schedule operator and UAV tasks simultaneously, ensuring a tenable operator workload while maximizing UAV effectiveness.

UAV Sensor Tasking

Many UAVs feature a suite of directional onboard sensors. With an increasing number of assets deployed, communication bandwidth limitations prohibit all of these sensors from broadcasting data simultaneously. We are exploring a persistent surveillance problem that requires the determination of (1) where each sensor should focus, (2) in what "mode" should each sensor operate (e.g., high definition or lower definition video), and (3) when should each sensor broadcast data to a ground control station.