Reversing Differences

Fellow blogger Håkan Kjellerstrand posted an interesting question on OR Stack Exchange recently. Starting from a list of integers, it is trivial to compute the list of all pairwise absolute differences, but what about going in the other direction? Given the pairwise (absolute) differences, with duplicates removed, can you recover the source list (or a …

More

Collections of CPLEX Variables

Recently, someone asked for help online regarding an optimization model they were building using the CPLEX Java API. The underlying problem had some sort of network structure with \(N\) nodes, and a dynamic aspect (something going on in each of \(T\) periods, relating to arc flows I think). Forget about solving the problem: the program …

More

Greedy Methods Can Be Exact

We generally sort optimization algorithms (as opposed to models) into two or three categories, based on how certain we are that solutions will be either optimal or at least “good”. An answer by Michael Feldmeier to a question I posted on OR Stack Exchange neatly summarizes the categories: exact methods eventually cough up provably optimal …

More

1-D Cutting Stock with Overlap

An interesting variation of the 1-D cutting stock problem was posed on OR Stack Exchange. Rather than having a specified demand for various size cut pieces, the requirement is to cut pieces to cover a specified number of units of fixed lengths. Moreover, you can use multiple pieces to cover one target unit, but if …

More

Brainpower Matters: The French H-Bomb

Michel Carayol, father of the French H-Bomb. The article below illuminates several mysteries concerning the French development of thermonuclear weapons. Why did it take so long? Did the French really need help from the British? Who had the crucial idea of radiation compression? The original inventors were Ulam and Teller. In the USSR it was Sakharov. The …

More

Evaluating Expressions in CPLEX

There’s a feature in the Java API for CPLEX (and in the C++ and C APIs; I’m not sure about the others) that I don’t see mentioned very often, possibly because use cases may not arise all that frequently. It became relevant in a recent email exchange, though, so I thought I’d highlight it. As …

More

R v. Python

A couple of days ago, I was having a conversation with someone that touched on the curriculum for a masters program in analytics. One thing that struck me was requirement of one semester each of R and Python programming. On the one hand, I can see a couple of reasons for requiring both: some jobs …

More

A Java Container for Parameters

A few days ago, I posted about a Swing class (and supporting stuff) that I developed to facilitate my own computations research, and which I have now made open-source in a Bitbucket repository. I finally got around to cleaning up another Java utility class I wrote, and which I use regularly in experiments. I call …

More

Indicator Constraints v. Big M

Way, way back I did a couple of posts related to how to model “logical indicators” (true/false values that control enforcement of constraints): Logical Indicators in Mathematical Program Indicator Implies Relation The topic ties in to the general issue of “big M” model formulations. Somewhere around version 10, CPLEX introduced what they call indicator constraints, …

More

Naming CPLEX Objects

A CPLEX user recently asked the following question on a user forum: “Is there a way to print the constraints as interpreted by CPLEX immediately after adding these constraints using addEq, addLe etc.” The context for a question like this is often an attempt to debug either a model or the code creating the model. …

More

How to Crash CPLEX

A question elsewhere on the blog reminded me that some users of the CPLEX programming APIs are not conscious of a “technicality” that, when violated, might cause CPLEX to crash (or at least throw an exception). The bottom line can be stated easily enough: modifying a CPLEX model while solving it is a Bozo no-no. …

More

Failures to Listen

One year ago today, Rachael Denhollander addressed the Ingham County court in Michigan, her abuser, and the institutions that failed to protect her and her #SisterSurvivors. Listen again to part of what she said on January 24, 2018: This is what it looks like when institutions create a culture where a predator can flourish unafraid and …

More

Guessing Pareto Solutions: A Test

In yesterday’s post, I described a simple multiple-criterion decision problem (binary decisions, no constraints), and suggested a possible way to identify a portion of the Pareto frontier using what amounts to guesswork: randomly generate weights; use them to combine the multiple criteria into a single objective function; optimize that (trivial); repeat ad nauseam. I ran …

More

Two Books – Real Gifts

I have a pile of about 10 books I’m wading through, but two are of special note as I write this. As I noted in my last blog of 2017 I have the privilege of reading, and especially of reading books. For the past few years I’ve read on average between 20-30 nonfiction works cover-to-cover per year. …

More

Living Values

In the open letter we wrote to the College of Arts & Letters community in January 2018, we promised to look critically at ourselves, recognize our failures, and rebuild the trust that is required of us. This commitment has led to an intense period of critical self-reflection in the Dean’s Office and across the College in …

More

Of Typewriters and Permutations (II)

This continues my previous post about the problem of optimally laying out a one-dimensional typewriter keyboard, where “optimally” is taken to mean minimizing the expected amount of lateral movement to type a few selected books. As I noted there, Nate Brixius correctly characterized the problem as a quadratic assignment problem (QAP). I’ll in fact try …

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

A Few Reflections on the TOME Initiative

WASHINGTON, DC – Today a group of colleagues from the Association of American Universities, Association of Research Libraries, and Association of University Presses met to advance the Towards an Open Monograph Ecosystem (TOME) initiative. It was heartening to see the progress the initiative has made since our first gathering in the summer of 2016. At the time, I was enthusiastic …

More

Selecting Box Sizes

Someone posted an interesting question about box sizes on Mathematics Stack Exchange. He (well, his girlfriend to be precise) has a set of historical documents that need to be preserved in boxes (apparently using a separate box for each document). He wants to find a solution that minimizes the total surface area of the boxes …

More

Evolution of a (data) visualization

Last summer, I taught the MAET Year 2 Summer Cohort with Danah Henriksen. After teaching the class, Danah realized she had taught five cohorts of (awesome) students and that we had some information available from pre- and post-course self-reported surveys to understand how students grew in terms of their confidence in using different educational (and …

More

Callback Cuts That Repeat

The following post is specific to the CPLEX integer programming solver. I have no idea whether it applies to other solvers, or even which other solver have cut callbacks. Every so often, a user will discover that a callback routine they wrote has “rediscovered” a cut it previously generated. This can be a bit concerning …

More

Grouping Rows of a Matrix

I spent a large chunk of yesterday afternoon doing something I thought would be simple (relatively speaking) in LaTeX. I wanted to group rows of a matrix (actually, in my case, a vector) with right braces, and label the groups. An example of what I wanted is in the image below. This seems to me …

More

Big M and Integrality Tolerance

A change I made to an answer I posted on OR-Exchange, based on a comment from a well-informed user of OR-X, might be worth repeating here on the blog. It has to do with issues that can occur when using “big M” type integer programming models, a topic I’ve covered here before. As I mentioned …

More

Cultivating a Culture of Trust

It has been difficult to write for the public in the months since posting the Open Letter to the College of Arts & Letters in the wake of the survivor impact statements that are transforming Michigan State University.1 Part of the difficulty is what my thoughtful #SpartanDean colleague, Prabu David, emphasized when he wrote that it is challenging to find the right …

More

Stephen Hawking (1942-2018)

Roger Penrose writes in the Guardian, providing a scientifically precise summary of Hawking’s accomplishments as a physicist (worth reading in full at the link). Penrose and Hawking collaborated to produce important singularity theorems in general relativity in the late 1960s. Here is a nice BBC feature: A Brief History of Stephen Hawking. The photo above …

More

How NSA Tracks You (Bill Binney)

Anyone who is paying attention knows that the Obama FBI/DOJ used massive government surveillance powers against the Trump team during and after the election. A FISA warrant on Carter Page (and Manafort and others?) was likely used to mine stored communications of other Trump team members. Hundreds of “mysterious” unmasking requests by Susan Rice, Samantha …

More

National Indian Law Library Bulletin (2/22/2018)

Here: The National Indian Law Library added new content to the Indian Law Bulletins on 2/22/18. U.S. Supreme Court Bulletin http://www.narf.org/nill/bulletins/sct/2017-2018update.html Petition for certiorari was denied in Renteria, et al. v. Superior Court of California, Tulare County, et al. (Indian Child Welfare Act) and in Norton, et al. v. Ute Indian Tribe of the Uintah and Ouray Reservation, et …

More

Documentary Films as Soccer Storytelling

I recently went on a cinematic journey that took me from women’s soccer in Zanzibar to a failed stadium-and-entertainment complex in Buenos Aires. My travel agency, so to speak, was the Football Scholars Forum. On February 23 it held an online discussion of two low-budget, high-return documentary films. (A recording of the event can be found here. …

More