# Transforming an arbitrary linear program into one with an interior point

Primal-dual interior point methods for linear programming require interior primal and dual starting points. I am looking for a good reference containing a description for modifying a given linear program (without solving an auxiliary LP and without doubling the number of variables or constraints) to one with a primal and dual interior point. The linear program is given in the form $\min c^Tx$ s.t. $Ax\ge b$ (or $Ax=b$, $x\ge 0$) and may possibly be primal or dual infeasible.

• Here's hit #1 on google. Seems to be what you're looking for. I haven't gone through it, though. link.springer.com/chapter/10.1007/978-1-4613-3449-1_5 – Tyler Olsen Jun 5 '18 at 0:34
• @TylerOlsen: This is not quite what I want, though it is related. I want to apply a standard interior point algorithm to a modified problem. – Arnold Neumaier Jun 5 '18 at 9:01