Locomotive and farmer example.

Several algorithms are available in the literature for finding the entire set of Pareto-optimal solutions in MultiObjective Linear Programming (MOLP). However, it has not been proposed so far an interior point algorithm that finds all Pareto-optimal solutions of MOLP. We present an explicit construction, based on a transformation of any MOLP into a finite sequence of SemiDefinite Programs (SDP), the solutions of which give the entire set of Pareto-optimal extreme points solutions of MOLP. These SDP problems are solved by interior point methods; thus our approach provides a pseudo-polynomial interior point methodology to find the set of Pareto-optimal solutions of MOLP.

"In the Partial Vertex Cover (PVC) problem we are given an undirected graph G = (V, E), a positive cost associated with each vertex and a positive integer k and the goal is to find a minimum cost subset of vertices S such that atleast k edges of the graph are covered. In this paper we consider two new generalization of the PVC problem. In the first variation which we call Partition Vertex Cover (Partition-VC) problem, the edges of the graph G are divided into n disjoint partitions $P_1, P_2... P_n$ and we have to select a minimum cost subset of vertices S such that atleast $k_i$ edges are covered from partition $P_i$. In the second variation which we call Knapsack Partition Vertex Cover (KPVC) problem, in addition to the previous conditions, each edge e has a profit $pi_{e}$ associated with it and we have an added knapsack constraint that the total profit of the covered edges in partition $P_i$ should be atleast $Pi_i$. We give an $O(log n)$ approximation for both the problems using a combination of deterministic rounding and randomized rounding approach that operates on the LP strengthened by adding Knapsack Cover inequalities as proposed by Carr, Fleischer, Leung & Phillips. We also show that these bounds can not be further improved by reducing the set cover problem to the Partition-VC problem in polynomial time. We also give an $O(f)$ approximation for the Partition-VC problem using a primal dual schema where f is the maximum number of edges in any partition."

Open source "industrial strength" linear and integer programming.

First in a two-part series. I think the vector notation gets a little bit dense (diagonalizing rewrites immediately after Hadamard products, bleagch) but it might be worth thinking about if there's a cleaner way of writing out some of this stuff. Presents a straightforward use for LP solvers to determine feasibility -- might be a reasonable test example for explaining the mechanics of the simplex algorithm. Finally, might be useful to think about in the context of making book against one or more "combinatorial" betting markets. In particular, I've been thinking about this in the context of NCAA betting pools...

Luca Trevisan's notes on approximation algorithms via LP relaxations of integer programs. Includes metric Steiner tree stuff -- at which point it's a review of 6.854, although with the difference (for me) that I think I understand it this time around.

"Oliver Friedman, Thomas Dueholm Hansen, and Uri Zwick have managed to prove subexponential lower bounds of the form for ... two basic randomized pivot rules for the simplex algorithm! This is the first result of its kind and deciding if this is possible was an open problem for several decades." And they do it using MDPs!

"We revisit the matrix problems sparse null space and matrix sparsification, and show that they are equivalent. We then proceed to seek algorithms for these problems: We prove the hardness of approximation of these problems, and also give a powerful tool to extend algorithms and heuristics for sparse approximation theory to these problems."

"l1-minimization refers to finding the minimum l1-norm solution to an underdetermined linear system b=Ax. It has recently received much attention, mainly motivated by the new compressive sensing theory that shows that under quite general conditions the minimum l1-norm solution is also the sparsest solution to the system of linear equations. Although the underlying problem is a linear program, conventional algorithms such as interior-point methods suffer from poor scalability for large-scale real world problems. A number of accelerated algorithms have been recently proposed that take advantage of the special structure of the l1-minimization problem. In this paper, we provide a comprehensive review of five representative approaches, namely, Gradient Projection, Homotopy, Iterative Shrinkage-Thresholding, Proximal Gradient, and Augmented Lagrange Multiplier. …"

You had me at, "a novel about linear programming." And with Kantorovich as a protagonist? I'm sold.

A month and a half old, but still ... cool! "I will describe the construction of a 43-dimensional polytope with 86 facets and diameter bigger than 43." From the comments, I find out that my TA from 6.854 is now working at Yahoo, writing papers about online auctions that look interesting.

"A key problem in multiobjective linear programming is to find the set of all efficient extreme points in objective space. In this paper we introduce oriented projective geometry as an efficient and effective framework for solving this problem. The key advantage of oriented projective geometry is that we can work with an "optimally simple" but unbounded efficiency-equivalent polyhedron, yet apply to it the familiar theory and algorithms that are traditionally restricted to bounded polytopes. We apply these techniques to Benson's outer approximation algorithm, using oriented projective geometry to remove an exponentially large complexity from the algorithm and thereby remove a significant burden from the running time."

"We develop elements of a theory of cooperation and coordination in networks. Rather than considering a communication network as a means of distributing information, or of reconstructing random processes at remote nodes, we ask what dependence can be established among the nodes given the communication constraints.…"

"Approximate dynamic programming has been used successfully in a large variety of domains, but it relies on a small set of provided approximation features to calculate solutions reliably. Large and rich sets of features can cause existing algorithms to overfit because of a limited number of samples. We address this shortcoming using $L_1$ regularization in approximate linear programming. Because the proposed method can automatically select the appropriate richness of features, its performance does not degrade with an increasing number of features. These results rely on new and stronger sampling bounds for regularized approximate linear programs. We also propose a computationally efficient homotopy method. The empirical evaluation of the approach shows that the proposed method performs well on simple MDPs and standard benchmark problems."

"…Through several nu- merical experiments, we demonstrate that both matrix- and tensor-based techniques are effective for temporal link prediction despite the inherent difficulty of the problem. Additionally, we show that tensor-based techniques are particularly effective for temporal data with varying periodic patterns."