Pseudocode in LyX Revisited

This post is strictly for users of LyX. In a previous post I offered up a LyX module for typesetting pseudocode. Unfortunately, development of that module bumped up against some fundamental incompatibilities between the algorithmicx package and the way LyX layouts work. The repository for it remains open, but I decided to shift my efforts …

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

Guessing Pareto Solutions

One of the challenges of multiple-criteria decision-making (MCDM) is that, in the absence of a definitive weighting or prioritization of criteria, you cannot talk meaningfully about a “best” solution. (Optimization geeks such as myself tend to find that a major turn-off.) Instead, it is common to focus on Pareto efficient solutions. We can say that …

More

Binary / Integer Conversion in R

I’ve been poking around in R with an unconstrained optimization problem involving binary decision variables. (Trust me, it’s not as trivial as it sounds.) I wanted to explore the entire solution space. Assuming \(n\) binary decisions, this means looking at the set \(\{0,1\}^n\), which contains \(2^n\) 0-1 vectors of dimension \(n\). For reasons I won’t …

More

Threads and Memory

Yesterday I had a rather rude reminder (actually, two) of something I’ve known for a while. I was running a Java program that uses CPLEX to solve an integer programming model. The symptoms were as follows: shortly after the IP solver run started, I ran out of RAM, the operating system started paging memory to …

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

Pseudocode in LyX

Fair warning: This post is for LyX users only. When I’m writing a paper or presentation in LaTeX (using LyX, of course) and want to include a program chunk or algorithm in pseudocode, I favor the algorithmicx package (and specifically the algpseudocode style). There being no intrinsic support for the package in LyX, I have …

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

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

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

Usefulness of Computer Science: An Example

I thought I would follow up on my June 29 post, “Does Computer Science Help with OR?“, by giving a quick example of how exposure to fundamentals of computer science recently helped me. A current research project involves optimization models containing large numbers of what are basically set covering constraints, constraints of the form \(\displaystyle …

More

Does Computer Science Help with OR?

Fair warning: tl/dr. After reading a blog post yesterday by John D. Cook, “Does computer science help you program?“, I decided to throw in my two cents (convert to euros at your own risk) on a related topic: does computer science (which I will extend to including programming) help you as an OR/IE/management science/analytics professional? …

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

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

Creating A New MIME Type

I struggled a bit this afternoon creating a new MIME type and associating it with a particular application, so I’m going to archive the solution here for future reference. This was on a Linux Mint system, but I found the key information in a GNOME documentation page, so I suspect it works for Ubuntu and …

More

Thread Safety

As I noted in yesterday’s post, one of the major changes associated with the new “generic” callback structure in CPLEX is that users now bear the responsibility of making their callbacks thread-safe. As I also noted yesterday, this is pretty new stuff for me. So I’m going to try to share what I know about thread …

More

CPLEX 12.8: Generic Callbacks

IBM is getting ready to release CPLEX 12.8, and I had the opportunity to attend a presentation about by Xavier Nodet at the 2017 INFORMS annual meeting. Here are links to two presentations by Xavier: CPLEX Optimization Studio 12.8 – What’s New and CPLEX 12.8 – the Generic Callback. As with any new release, there …

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

Premature Obituaries

[T]he report of my death was an exaggeration. (Mark Twain, 1897) In a recent blog post, “Data Science Is Not Dead“, Jean-Francois Puget discussed and dissented with a post by Jeroen ter Heerdt titled “Data Science is dead.” Barring the possibility that Schroedinger shoved data science into a box and sealed it, both assertions cannot …

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

Adventures with TeX Live

Since I use the Linux Mint operating system, the obvious (if not only) choice for a LaTeX distribution is TeX Live. (If you are not familiar with, or are not interested in, the LaTeX typesetting system, you have already read too far in this post.) On Mint, Ubuntu and other Debian-type operating systems, you typically …

More

MSU Students Do Microfinance

Several years ago, I found out about Kiva.org, an online “microfinance” site where individuals can make small loans ($25 is the standard increment at Kiva) to entrepreneurs in low income settings. The entrepreneurs actually apply for larger amounts, which they typically receive from third-party “field partners”. The entrepreneurs repay the loans with interest to the …

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

Pro Bono Analytics Is Growing Social

Pro Bono Analytics is a program by INFORMS (the Institute for Operations Research and the Management Sciences, for the acronym-averse), “the largest society in the world for professionals in the field of operations research (O.R.), management science, and analytics”. PBA “connects our members and other analytics professionals with nonprofit organizations working in underserved and developing communities”. …

More

Mapping Trackball Buttons

For years, I’ve used a Logitech M570 wireless trackball with my Linux Mint PC. I generally prefer trackballs to mice — no need to lift and reposition after a bunch of movement — and I find that using my thumb, rather than my index finger (or, if I’m in a bad mood, my middle finger) …

More

Mint Upgrade Woes

As I mentioned a couple of months ago, I upgraded a laptop from Linux Mint 17.3 (“Rebecca”) to 18.0 (“Sarah”) with minimal difficulties. My laptop serves as a guinea pig for these things. Once I’m sure things work fine on the laptop, I’ll consider upgrading my desktop as well. A few days ago I finally …

More