MIT IAP 2013 Software Tools for Operations Research Tutorial: Customizing Integer Programming Solvers with Callbacks

The Operations Research Center offered a new course this IAP, 15.S60 SSIM: Software Tools for Operations Research. The course consisted of the following modules (as summarized by Iain Dunning here): introductory and advanced classes on R (Allison O’Hair, Andre Calmon, John Silberholz), data visualization (Virot Chiraphadhanakul), using Python for mathematical modelling (Iain Dunning) convex optimization …

Continue reading ‘MIT IAP 2013 Software Tools for Operations Research Tutorial: Customizing Integer Programming Solvers with Callbacks’ »

Equivalent Notions for Convergence in Distribution and Equality in Distribution of Random Variables

The following is based on material created for the MIT class 6.436/15.085 Fundamentals of Probability. You can download the pdf version used in the class here. 1. Equality in Distribution and Convergence in Distribution 1.1. Review of Definitions In this section, we consider several perspectives on what it means for two random variables to be …

Continue reading ‘Equivalent Notions for Convergence in Distribution and Equality in Distribution of Random Variables’ »

A Parallel Implementation of the Floyd Warshall Algorithm for the All Pairs Shortest Path Problem with a JUNG Wrapper

The All Pairs Shortest Path (APSP) problem is to compute the shortest path between every pair of points in a directed weighted graph.  The Floyd Warshall algorithm is a dynamic programming algorithm that solves the APSP problem in time.  The running time is impressive, as there are pairs of nodes, so the average time spent per pair …

Continue reading ‘A Parallel Implementation of the Floyd Warshall Algorithm for the All Pairs Shortest Path Problem with a JUNG Wrapper’ »

From Separation to Optimization in Cplex: Using User Cut Callbacks and Lazy Constraint Callbacks to Solve Large TSPs in Java

Edit: some of the material here has been superceded by the tutorial I gave for the 2013 MIT IAP.  However, that tutorial does not discuss multi-threading or the Karger Stein algorithm, which are covered below.   Introduction For many important problems in combinatorial optimization, known efficient algorithms (and approximation algorithms) rely on a separation oracle …

Continue reading ‘From Separation to Optimization in Cplex: Using User Cut Callbacks and Lazy Constraint Callbacks to Solve Large TSPs in Java’ »

Sorting in Parallel in Java using Executors and Arrays.sort

Below is HeavySort, a parallel sorting algorithm in Java. The algorithm takes the following steps: Input: An list A of length n and to be sorted with m threads. Divide A into m pieces, and sort each piece onto a new list Bi. Build a list C with first the smallest element of A, then …

Continue reading ‘Sorting in Parallel in Java using Executors and Arrays.sort’ »

The Central Limit Theorem

A proof of the central limit theorem not using characteristic functions or any complex analysis is provided. The basic approach is as follows. We show that for a sequence of i.i.d. random variables with finite second moments, truncating the tails of each random variable leaves the sum “nearby.” As our truncated random variables are bounded …

Continue reading ‘The Central Limit Theorem’ »

Use Tikz and Hyperref to make commutative diagrams with linked labels in LaTeX

In the example below, a commutative diagram was drawn using Tikz. The arrows in the diagram have labels that link to the corresponding theorem below. Download this example. The LaTeX code used to generate this figure is below. \documentclass{article} \pagestyle{empty} \usepackage{tikz,amsmath} \usetikzlibrary{arrows,shapes,matrix} \newtheorem{thm}{Theorem} \usepackage{hyperref} \hypersetup{ colorlinks=true, } \begin{document} \begin{figure} \centering \begin{tikzpicture} \matrix(m)[matrix of math nodes, …

Continue reading ‘Use Tikz and Hyperref to make commutative diagrams with linked labels in LaTeX’ »