A First-Order Smoothing Technique for a Class of Large-Scale Linear Programs

We study a class of linear programming (LP) problems motivated by large-scale machine learning applications. After reformulating the LP as a convex nonsmooth problem, we apply Nesterov’s primal-dual smoothing technique. It turns out that the iteration complexity of the smoothing technique depends on a parameter $\th$ that arises because we need to bound the originally … Read more

Dantzig-Wolfe and block coordinate-descent decomposition in large-scale integrated refinery-planning

The integrated refinery-planning (IRP), an instrumental problem in the petroleum industry, is made of several subsystems, each of them involving a large number of decisions. Despite the complexity of the overall planning problem, this work presents a mathematical model of the refinery operations char acterized by complete horizontal integration of subsystems from crude oil purchase … Read more

On some difficult linear programs coming from Set Partitioning

We deal with the linear programming relaxation of set partitioning problems arising in airline crew scheduling. Some of these linear programs have been extremely difficult to solve with the traditional algorithms. We have used an extension of the subgradient algorithm, the volume algorithm, to produce primal solutions that might violate the constraints by at most … Read more