Efficient Heuristic Algorithms for Maximum Utility Product Pricing Problems

We propose improvements to some of the best heuristic algorithms for optimal product pricing problem originally designed by Dobson and Kalish in the late 1980’s and in the early 1990’s. Our improvements are based on a detailed study of a fundamental decoupling structure of the underlying mixed integer programming (MIP) problem and on incorporating more … Read more

Semi-continuous network flow problems

We consider semi-continuous network flow problems, that is, a class of network flow problems where some of the variables are restricted to be semi-continuous. We introduce the semi-continuous inflow set with variable upper bounds as a relaxation of general semi-continuous network flow problems. Two particular cases of this set are considered, for which we present … Read more

Convergence Analysis of a Long-Step Primal-Dual Infeasible Interior-Point LP Algorithm Based on Iterative Linear Solvers

In this paper, we consider a modified version of a well-known long-step primal-dual infeasible IP algorithm for solving the linear program $\min\{c^T x : Ax=b, \, x \ge 0\}$, $A \in \Re^{m \times n}$, where the search directions are computed by means of an iterative linear solver applied to a preconditioned normal system of equations. … Read more

Uniform Boundedness of a Preconditioned Normal Matrix Used in Interior Point Methods

Solving systems of linear equations with “normal” matrices of the form $A D^2 A^T$ is a key ingredient in the computation of search directions for interior-point algorithms. In this article, we establish that a well-known basis preconditioner for such systems of linear equations produces scaled matrices with uniformly bounded condition numbers as $D$ varies over … Read more