# Numerical Inaccuracy (Linear Algebra Edition)

“There are three kinds of lies: lies, damned lies, and statistics.” The origin of the statement is lost in time, but the sentiment lives on. I’m tempted to give it a 21st century update. “There are three kinds of lies: lies, damned lies, and floating point arithmetic.” I am currently working on a research project …

More

# Some Periodic Functions

Let’s start with a basic “calculus fact”. Theorem 1  If f is a non-constant, continuous periodic function on R, then there exists a smallest positive real number λ satisfying f(x+λ)=f(x) for all x. Proof: By definition of periodicity, there exists a subset Λ⊂R satisfying f(x+λ)=f(x) for every x∈R and λ∈Λ. Necessarily Λ is closed under …

More

# B.S.-ing Precisely

In a recent blog post titled “Excessive Precision“, John D. Cook points out the foolishness of articulating results to an arbitrarily high degree of precision when the inputs are themselves not that precise. To quote him: Excessive precision is not the mark of the expert. Nor is it the mark of the layman. It’s the …

More

# Coordinating Variable Signs

Someone asked me today (or yesterday, depending on whose time zone you go by) how to force a group of variables in an optimization model to take the same sign (all nonpositive or all nonnegative). Assuming that all the variables are bounded, you just need one new binary variable and a few constraints. Assume that …

More

# The French Way: Alain Connes interview

I came across this interview with Fields Medalist Alain Connes (excerpt below) via an essay by Dominic Cummings (see his blog here). Dom’s essay is also highly recommended. He has spent considerable effort to understand the history of highly effective scientific / research organizations. There is a good chance that his insights will someday be put …

More

# Adding Items to a Sequence

A question posed on OR-Exchange in 2017 asked the following: Given a tour of nodes, how does one best add two new nodes while respecting the ordering of the original tour. Specifically, the author began with a tour 0 – 1 – 2 – 4 – 6 – 0 (where node 0 is a depot) …

More

# NP Confusion

I just finished reading a somewhat provocative article on the CIO website, titled “10 reasons to ignore computer science degrees” (when hiring programmers). While I’m not in the business of hiring coders (although I recent was hired as a “student programmer” on a grant — the Universe has a sense of humor), I find myself …

More

# ICML notes

It’s never been a better time to work on AI/ML. Vast resources are being deployed in this direction, by corporations and governments alike. In addition to the marvelous practical applications in development, a theoretical understanding of Deep Learning may emerge in the next few years. The notes below are to keep track of some interesting …

More

# Recalculating Gateway Mathematics at MSU

A new approach and course offerings in the MSU Department of Mathematics adds up to MSU student success. An essential component of undergraduate education is the development of the mathematical skills and knowledge that enable students to fully contribute to society and to succeed in their chosen professions. At Michigan State University (MSU), we believe …

More

# More on “Core Points”

A few additions to yesterday’s post occurred to me belatedly. First, it may be a good idea to check whether your alleged core point $$y^0$$ is actually in the relative interior of the integer hull $$\mathrm{conv}(Y)$$. A sufficient condition is that, when you substitute $$y^0$$ into the constraints, all inequality constraints including variable bounds have …

More

# Finding a “Core Point”

In a famous (or at least relatively famous) paper [1], Magnanti and Wong suggest a method to accelerate the progress of Benders decomposition for certain mixed-integer programs by sharpening “optimality” cuts. Their approach requires the determination of what they call a core point. I’ll try to follow their notation as much as possible. Let $$Y$$ …

More

# Big Ed

Today I came across a recent interview with Ed Witten in Quanta Magazine. The article has some nice photos like the one above. I was struck by the following quote from Witten (“It from Qubit!”): When I was a beginning grad student, they had a series of lectures by faculty members to the new students about …

More

# CMSE (Computational Mathematics, Science and Engineering) at MSU

At Oregon I was part of an interdisciplinary institute that included theoretical physicists and chemists, mathematicians, and computer scientists. We tried to create a program (not even a new department, just an interdisciplinary program) in applied math and computation, but failed due to lack of support from higher administration. When I arrived at MSU as …

More

# Minimizing a Median

$$\def\xorder#1{x_{\left(#1\right)}} \def\xset{\mathbb{X}} \def\xvec{\mathbf{x}}$$A somewhat odd (to me) question was asked on a forum recently. Assume that you have continuous variables $$x_{1},\dots,x_{N}$$ that are subject to some constraints. For simplicity, I’ll just write $$\xvec=(x_{1},\dots,x_{N})\in\xset$$. I’m going to assume that $$\xset$$ is compact, and so in particular the $$x_{i}$$ are bounded. The questioner wanted to …

More

# Rolling Horizons

I keep seeing questions posted by people looking for help as they struggle to optimize linear programs (or, worse, integer linear programs) with tens of millions of variables. In my conscious mind, I know that commercial optimizers such as CPLEX allow models that large (at least if you have enough memory) and can often solve …

More

# Memory Minimization

As I grow older, I’m starting to forget things (such as all the math I ever learned) … but that’s not the reason for the title of this post. A somewhat interesting question popped up on Mathematics StackExchange. It combines a basic sequencing problem (ordering the processing of computational tasks) with a single resource constraint …

More

# An evolutionary theory of music

“The beauty of music is in the ear of the beholder”, we are always told. Or perhaps we are not always told this, but I imagine that we should be told that. Because while I like a lot of music that other people like, I don’t always agree with what other people say is–not just …

More

# If This and That Then Whatever

I was asked a question that reduced to the following: if $$x$$, $$y$$ and $$z$$ are all binary variables, how do we handle (in an integer programming model) the requirement “if $$x=1$$ and $$y=1$$ then $$z=1$$”? In the absence of any constraints on $$z$$ when the antecedent is not true, this is very easy: add …

More

# Update Error: Wrong Architecture

Yesterday I ran into one of those mystifying glitches that, will infrequent, serve as a reminder that Linux is not for the faint of heart. When I booted my desktop system (Linux Mint 18.1 Serena), the system tray icon for the software updater was displaying a red “X” that indicates it tried and failed to …

More

# Von Neumann and Realpolitik

“Right, as the world goes, is only in question between equals in power, while the strong do what they can and the weak suffer what they must.” — Thucydides, Melian Dialogue. Von Neumann, Feynman, and Ulam. Adventures of a Mathematician (Ulam): … Once at Christmas time in 1937, we drove from Princeton to Duke University …

More

# Sharing “Implicit” Test Problems

The topic of reproducible research is garnering a lot of attention these days. I’m not sure there is a 100% agreed upon, specific, detailed definition of it, and I do think it’s likely to be somewhat dependent on the type of research, but for purposes of this post the Wikipedia definition (previous link) works for …

More

I love Joe Rogan — he has an open, inquisitive mind and is a sharp observer of life and human society. See, for example, this interview with Dan Bilzerian about special forces, professional poker, sex, drugs, heart attacks, life, happiness, hedonic treadmill, social media, girls, fame, prostitution, money, steroids, stem cell therapy, and plenty more. …

More

# Common Core and NGSS are not on the news

How often are curricular standards mentioned on TV news? With my friend Patrick, I was curious about using the newsflash package for something education-related. We came up with the idea of looking at mentions of the Common Core State Standards (for Mathematics and English Language Arts / Literacy) and the Next Generation Science Standards (for …

More

# Another Absolute Value Question

Someone asked whether it is possible to eliminate the absolute value from the constraint $$Lx\le |y| \le Ux$$ (where $$L\ge 0$$ and $$U>0$$ are constants, $$x$$ is a binary variable, and $$y$$ is a continuous variable). The answer is yes, but what it takes depends on whether $$L=0$$ or $$L>0$$. The easy case is when …

More

# Fischetti on Benders Decomposition

I just came across slides for a presentation that Matteo Fischetti (University of Padova) gave at the Lunteren Conference on the Mathematics of Operations Research a few days ago. Matteo is both expert at and dare I say an advocate of Benders decomposition. I use Benders decomposition (or variants of it) rather extensively in my …

More

# Oppenheimer on Bohr (1964 UCLA)

Oppenheimer on Bohr (1964 UCLA) I came across this 1964 UCLA talk by Oppenheimer, on his hero Niels Bohr. Oppenheimer: Mathematics is “an immense enlargement of language, an ability to talk about things which in words would be simply inaccessible.” I find it strange that psychometricians usually define “verbal ability” over a vocabulary set that …

More

# Support for Benders Decomposition in CPLEX

As of version 12.7, CPLEX now has built-in support for Benders decomposition. For details on that (and other changes to CPLEX), I suggest you look at this post on J-F Puget’s blog and Xavier Nodet’s related slide show. [Update 12/7/16: There is additional information about the Benders support in a presentation by IBM’s Andrea Tramontani …

More

# MIP Models in R with OMPR

A number of R libraries now exist for formulating and solving various types of mathematical programs in R (or formulating them in R and solving them with external solvers). For a comprehensive listing, see the Optimization and Mathematical Programming task view on CRAN. I decided to experiment with Dirk Schumacher’s OMPR package for R. OMPR …

More

# Better Estimate, Worse Result

I thought I might use a few graphs to help explain an answer I posted on Quora recently. First, I’ll repeat the question here: In parametric optimization with unknown parameters, does a better estimator of the parameter always lead to better solutions to the actual problem? Here we’re trying to minimize f(x,θ) with respect to …

More

# Finding the Kernel of a Matrix

I’m working on an optimization problem (coding in Java) in which, should various celestial bodies align the wrong way, I may need to compute the rank of a real matrix and, if it’s less than full rank, a basis for its kernel. (Actually, I could get by with just one nonzero vector in the kernel, …

More

# Enforcing Simultaneous Arrivals

I’m recapping here an answer to a modeling question that I just posted on a help forum. (Since it will now appear in two different places, let’s hope it’s correct!) The original poster (OP) was working on a routing model, in which vehicles (for which I will use and if needed as indices) are assigned …

More

# MathJax Whiplash

Technology is continuously evolving, and for the most part that’s good. Every now and then, though, the evolution starts to look like a random mutation … the kind that results in an apocalyptic virus, or mutants with superpowers, or something else that is much more appealing as a plot device in a movie or TV …

More

# Matching Ordering Is Not Always Easy

In some circumstances, you might want to build an optimization model containing two sets of variables, say and , and constrain them so that the sort order of each matches. That condition is easily expressed in logical terms: if and only if for all pairs with . Translating that into a mathematical programming model that …

More

# A CP Model for the Weight Problem of Bachet de Meziriac

Fellow OR blogger Erwin Kalvelagen just posted a MINLP model for a puzzle apparently posed by French mathematician Claude Gaspard Bachet de Méziriac. You can read the puzzle statement on Erwin’s blog; a brief synopsis is that you are looking to find four integer weights that sum to 40, such that any object with integer …

More

# Creativity in mathematics and beyond: New article

Our series of articles related to the broad topic of Rethinking technology and creativity for the 21st century in the journal TechTrends continues with a new article on creativity in mathematics. This article focuses on the 4 winners of the 2014 Fields medal (one of the highest honors in mathematics and a recognition from one’s peers of highly influential and …

More

# Oracle Java 8 Update

For quite a while, I was getting security nags from Firefox every time a web site wanted to run a Java applet. Firefox would tell me I needed to upgrade to the latest version of Java. That would have been fine, except that I was already running the latest Java (1.8.0_66 as of this writing). …

More

# Milnor, Nash, and Game Theory at RAND

Nash and Milnor were involved in experimental tests of n-person game theory at RAND in 1952. Even then it was clear that game theory had little direct applicability in the real world. See also What Use Is Game Theory? , Iterated Prisoner’s Dilemma is an Ultimatum Game, and, e.g., The Econ Con or Venn Diagram …

More

# The cult of genius?

In one of his early blog posts, Terence Tao (shown above with Paul Erdos in 1985) wrote Does one have to be a genius to do maths? The answer is an emphatic NO. In order to make good and useful contributions to mathematics, one does need to work hard, learn one’s field well, learn other …

More

# David Donoho interview at HKUST

A long interview with Stanford professor David Donoho (academic web page) at the IAS at HKUST. Donoho was a pioneer in thinking about sparsity in high dimensional statistical problems. The motivation for this came from real world problems in geosciences (oil exploration), encountered in Texas when he was still a student. Geophysicists were using Compressed …

More

# Ambigrams & Math: In one embeddable ebook

Over the past two years Gaurav Bhatnagar and I have written five columns for the Math education journal At Right Angles  on the topics of mathematics and visual wordplay, specifically Ambigrams. In this five articles we have explored everything from symmetry to self-similarity, fractals to paradoxes. I have posted these articles on this website as they have been …

More

# Paradoxes & Ambigrams: Article 2 of 2

A few months ago I had posted about publication of the first of two articles on mathematics, visual wordplay and paradoxes. The second article (part of our series on Art and Math co-authored with my friend Gaurav Bhatnagar and published by At Right Angles) is now available. You can download all of the articles in the series Of Art & Math by following the links below …

More

# Optimizing Part of the Objective Function

A somewhat curious question showed up on a forum today. The author of the question has an optimization model (I’ll assume it is either a linear program or mixed integer linear program) of the form \begin{alignat*}{2} & \textrm{maximize} & & \sum_{i=1}^{N}x_{i}\\ & \textrm{s.t.} & & x\in\mathcal{X} \end{alignat*} where the feasible region $\mathcal{X}$ is presumably polyhedral. …

More

# Selecting the Least Qualifying Index

Something along the following lines cropped up recently, regarding a discrete optimization model. Suppose that we have a collection of binary variables $x_i \in B, \, i \in 1,\dots,N$ in an optimization model, where $B=\{0, 1\}$. The values of the $x_i$ will of course be dictated by the combination of the constraints and objective function. …

More

# Erdös with a non-kosher side of Bacon

Paul Erdös was a prolific and important mathematician. He also had hundreds of collaborators from around the world who coauthored papers with him. Years ago, Casper Goffman explained an idea, called the Erdös number, that describes the “collaborative distance” between Erdös and someone else, where that distance is defined by the smallest number of steps based …

More

# John Nash, dead at 86

The original title of this post was For this you won a Nobel (Memorial) Prize? But see sad news at bottom. A Beautiful Mind: Nash went to see von Neumann a few days after he passed his generals? He wanted, he had told the secretary cockily, to discuss an idea that might be of interest …

More

# What happens to an evaporating black hole?

For years now I have written about the quantum physics of black holes, and each and every time I have pushed a single idea: that if black holes behave as (almost perfect) black bodies, then they should be described by the same laws as black bodies are. And that means that besides the obvious processes …

More

# Ulam on physical intuition and visualization

The picture above is of von Neumann, Feynman, and Ulam. More Ulam. See also the nature of intuition and intuition and the two brains. Adventures of a Mathematician: (p.147-148) … the main ability to have was a visual, and also an almost tactile, way to imagine the physical situations, rather than a merely logical picture …

More

# Fischer Black: “a vision of the future that came true”

This is Barnard professor Perry Mehrling on the origin of interest rate and credit derivatives in the mind of Fischer Black. I highly recommend Mehrling’s biography of Black, which I discussed previously here: Black was both an undergrad and grad student at Harvard in physics. He didn’t really complete his PhD in physics, but sort of …

More

# Formulating Optimization Models

Periodically, on OR Exchange and other forums, I encounter what are surely homework problems involving the construction of optimization models. “The Acme Anvil Corporation makes two types of anvils, blue ones and red ones. Blue anvil use 185 kg. of steel and have a gross revenue of \$325 each; red anvils …” Really? Does anyone …

More

# Partitioning with Binary Variables

Armed with the contents of my last two posts (“The Geometry of a Linear Program“, “Branching Partitions the Feasible Region“), I think I’m ready to get to the question that motivated all this. Let me quickly enumerate a few key take-aways from those posts: The branch and bound method for solving an integer linear program …

More