title: How to quickly get a feasible solution to a linear program in Python?
body: <p><strong>Goal:</strong> Compute the intersection of two convex polytopes.</p>
  
  <p>I am using <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html" rel="nofollow noreferrer"><code>scipy.spatial.HalfspaceIntersection</code></a> to do this. The following image shows the resultant intersection: <a href="https://i.stack.imgur.com/H9nRn.png" rel="nofollow noreferrer"><img src="https://i.stack.imgur.com/H9nRn.png" alt="rviz-screenshot"></a></p>
  
  <p><strong>My problem:</strong> Determine an initial feasible point.</p>
  
  <p>You see, the current <code>Python</code> implementation of <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.spatial.HalfspaceIntersection.html#scipy.spatial.HalfspaceIntersection" rel="nofollow noreferrer"><code>scipy.spatial.HalfspaceIntersection</code></a> requires an <code>interior_point</code> to be passed as an argument.</p>
  
  <blockquote>
    <p><code>interior_point : ndarray of floats, shape (ndim,)</code><br>
    Point clearly inside the region defined by halfspaces. Also called a feasible point, it can be obtained by linear programming.</p>
  </blockquote>
  
  <p>Now, at the moment, I am manually supplying the feasible point because I was just drafting a prototype to experiment with <code>HalfspaceIntersection</code>.
  But now I have reached a point where I do not want to manually specify it.</p>
  
  <p><a href="https://www.scipy.org/" rel="nofollow noreferrer">SciPy</a>'s optimization module <a href="https://docs.scipy.org/doc/scipy/reference/generated/scipy.optimize.linprog.html" rel="nofollow noreferrer"><code>scipy.optimize.linprog</code></a> implements two general <em>Linear Programming (LP)</em> solvers: <em>simplex</em>, and <em>interior-point</em>. However, they seem to require a cost function. [<a href="https://docs.scipy.org/doc/scipy/reference/optimize.html#linear-programming" rel="nofollow noreferrer">1</a>]</p>
  
  <p>Since I want to spend the least amount of processing time as possible computing this feasible point, I was wondering how I can run any of these LP methods <em>without</em> a cost function, i.e., only run until the solution has reached a <em>feasible</em> status.</p>
  
  <p><strong>Questions:</strong></p>
  
  <ol>
  <li><p>Is <code>scipy.optimize.linprog</code> the right way to go for computing this feasible interior point?</p></li>
  <li><p>If yes, how can I use either <em>simplex</em> or <em>interior-point</em> <strong>without</strong> a cost function?</p></li>
  <li><p>Why does <code>scipy.spatial.HalfspaceIntersection</code> <em>require</em> an <code>interior point</code> to be passed as an argument in the first place? To the best of my understanding, an intersection of halfspaces is the removal of the redundant inequalities of a given set of inequalities. Why is a feasible point required for this?</p></li>
  </ol>