# 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

# Branching Partitions the Feasible Region

Yesterday’s post got me started on the subject of the geometry of a linear program (LP). Today I want to review another well-known geometric aspect, this time of integer linear programs (ILPs) and mixed integer linear programs (MILPs), that perhaps slips some people’s minds when they are wrestling with their models. Most solvers use some …

More

# The Geometry of a Linear Program

I frequently see questions on forums, in blog comments, or in my in-box that suggest the person asking the question is either unfamiliar with the geometry of a linear program, unsure of the significance of it, or just not connecting their question to the geometry. This post is just the starting point for addressing some …

More

# Flagging a Specific Variable Value

A recent question on a web forum, one I’ve seen asked elsewhere, was the following: in a mathematical programming model, how does one constrain a binary variable to take the value 1 if another variable takes a specific (predefined) value, and 0 otherwise? If the binary variable is , the other variable is , and …

More

# Making Math Fun

I was a math major from undergrad to doctorate, so obviously I think math is fun. Equally obvious to me (especially after teaching a variety of mathematical topics to college students), not everyone shares that opinion, which is too bad. Recently, though, I came across an organization devoted to making math fun for small children, …

More

# Analogies between Analogies

As reported by Stan Ulam in Adventures of a Mathematician: “A mathematician is a person who can find analogies between theorems; a better mathematician is one who can see analogies between proofs and the best mathematician can notice analogies between theories. One can imagine that the ultimate mathematician is one who can see analogies between …

More

# Gender differences in preferences, choices, and outcomes: SMPY longitudinal study

The recent SMPY paper below describes a group of mathematically gifted (top 1% ability) individuals who have been followed for 40 years. This is precisely the pool from which one would hope to draw STEM and technological leadership talent. There are 1037 men and 613 women in the study. The figures show significant gender …

More

# On quantum measurement (Part 5: Quantum Venn diagrams)

Here’s what you missed, in case you have stumbled into this series midway. As you are wont to do, of course. Part 1 had me reminiscing about how I got interested in the quantum measurement problem, even though my Ph.D. was in theoretical nuclear physics, not “foundational” stuff, and introduced the incomparable Hans Bethe, who …

More

# Linearize That!

For whatever reason, I’ve seen a bunch of questions posted on various fora boiling down to “How do I linearize <insert grossly nonlinear function>?” Whether by coincidence or due to some virtual viral epidemic, I’ve seen three or four in the past week that involved logarithms. So, without further ado, here is the quick solution: …

More