Good references for reduced cost fixing?

Question

Reduced cost fixing is a technique used by mixed integer programming (MIP) solvers to safely fix variables to certain values. While this technique is well-known among the MIP community, I don't know of any standard/definitive references on it. For example, I cannot find it mentioned in the usual textbooks (Nemhauser and Wolsey; Conforti, Cornuéjols, and Zambelli; R Kipp Martin; etc), although it is mentioned in Wolsey's book but only as an exercise. It is often mentioned in research articles, but usually only in passing.

Are there any textbooks or surveys that cover (LP-based) reduced cost fixing, preferably with examples? I am looking for something that could be shared with students who are unfamiliar with the idea.

Answer 1

Unfortunately, I can't provide you with a perfect reference or a textbook including examples but I can point you to a trail of papers/surveys pointing out the origin of reduced cost fixing.

One survey paper about presolve for MILPs that also includes some examples (but not one for reduced cost fixing) is:

Suhl and Szymanski: Supdernode Processing of Mixed-Integer Models (1994)

They start the section on "reduced costs(!) fixing" with "It is long known that...". This is potentially a good reference because they also call it by the name we use today (with an extra "s" that can be overlooked). They give another nice presolve paper as reference:

Crowder, Johnson, Padberg: Solving Large-Scale Zero-One Linear Programming Problems (1982)

They call it "Continuous Reduced Cost Implications". That paper does not give a reference (but has an interesting note about them having to restart after fixings for implementation reasons, which solvers do nowadays because it turns out to be actually good sometimes).

As far as I know and based on this paper

Grötschel and Nemhauser: George Dantzig’s contributions to integer programming (2008)

I think it's save to say that the origin of reduced cost fixing (and many other basic techniques to solve MIPs) is the famous 49-city TSP paper:

Dantzig, Fulkerson, Johnson: Solution of a Large-Scale Traveling-Salesman Problem (1954)

The notation in that paper is a bit cryptic for us these days so I would not recommend it as a reference on that topic. But explaining reduced cost fixing on the example of the TSP is probably a good idea.