code: def _presolve(c, A_ub, b_ub, A_eq, b_eq, bounds, rr, tol=1e-9):
      """
      Given inputs for a linear programming problem in preferred format,
      presolve the problem: identify trivial infeasibilities, redundancies,
      and unboundedness, tighten bounds where possible, and eliminate fixed
      variables.
  
      Parameters
      ----------
      c : 1D array
          Coefficients of the linear objective function to be minimized.
      A_ub : 2D array, optional
          2D array such that ``A_ub @ x`` gives the values of the upper-bound
          inequality constraints at ``x``.
      b_ub : 1D array, optional
          1D array of values representing the upper-bound of each inequality
          constraint (row) in ``A_ub``.
      A_eq : 2D array, optional
          2D array such that ``A_eq @ x`` gives the values of the equality
          constraints at ``x``.
      b_eq : 1D array, optional
          1D array of values representing the RHS of each equality constraint
          (row) in ``A_eq``.
      bounds : sequence of tuples
          ``(min, max)`` pairs for each element in ``x``, defining
          the bounds on that parameter. Use None for each of ``min`` or
          ``max`` when there is no bound in that direction.
      rr : bool
          If ``True`` attempts to eliminate any redundant rows in ``A_eq``.
          Set False if ``A_eq`` is known to be of full row rank, or if you are
          looking for a potential speedup (at the expense of reliability).
      tol : float
          The tolerance which determines when a solution is "close enough" to
          zero in Phase 1 to be considered a basic feasible solution or close
          enough to positive to serve as an optimal solution.
  
      Returns
      -------
      c : 1D array
          Coefficients of the linear objective function to be minimized.
      c0 : 1D array
          Constant term in objective function due to fixed (and eliminated)
          variables.
      A_ub : 2D array, optional
          2D array such that ``A_ub @ x`` gives the values of the upper-bound
          inequality constraints at ``x``.
      b_ub : 1D array, optional
          1D array of values representing the upper-bound of each inequality
          constraint (row) in ``A_ub``.
      A_eq : 2D array, optional
          2D array such that ``A_eq @ x`` gives the values of the equality
          constraints at ``x``.
      b_eq : 1D array, optional
          1D array of values representing the RHS of each equality constraint
          (row) in ``A_eq``.
      bounds : sequence of tuples
          ``(min, max)`` pairs for each element in ``x``, defining
          the bounds on that parameter. Use None for each of ``min`` or
          ``max`` when there is no bound in that direction. Bounds have been
          tightened where possible.
      x : 1D array
          Solution vector (when the solution is trivial and can be determined
          in presolve)
      undo: list of tuples
          (index, value) pairs that record the original index and fixed value
          for each variable removed from the problem
      complete: bool
          Whether the solution is complete (solved or determined to be infeasible
          or unbounded in presolve)
      status : int
          An integer representing the exit status of the optimization::
  
           0 : Optimization terminated successfully
           1 : Iteration limit reached
           2 : Problem appears to be infeasible
           3 : Problem appears to be unbounded
           4 : Serious numerical difficulties encountered
  
      message : str
          A string descriptor of the exit status of the optimization.
  
      References
      ----------
      .. [5] Andersen, Erling D. "Finding all linearly dependent rows in
             large-scale linear programming." Optimization Methods and Software
             6.3 (1995): 219-227.
      .. [8] Andersen, Erling D., and Knud D. Andersen. "Presolving in linear
             programming." Mathematical Programming 71.2 (1995): 221-245.
  
      """
      # ideas from Reference [5] by Andersen and Andersen
      # however, unlike the reference, this is performed before converting
      # problem to standard form
      # There are a few advantages:
      #  * artificial variables have not been added, so matrices are smaller
      #  * bounds have not been converted to constraints yet. (It is better to
      #    do that after presolve because presolve may adjust the simple bounds.)
      # There are many improvements that can be made, namely:
      #  * implement remaining checks from [5]
      #  * loop presolve until no additional changes are made
      #  * implement additional efficiency improvements in redundancy removal [2]
  
      undo = []  # record of variables eliminated from problem
      # constant term in cost function may be added if variables are eliminated
      c0 = 0
      complete = (
          False  # complete is True if detected infeasible/unbounded
      )
      x = np.zeros(
          c.shape
      )  # this is solution vector if completed in presolve
  
      status = 0  # all OK unless determined otherwise
      message = ""
  
      # Standard form for bounds (from _clean_inputs) is list of tuples
      # but numpy array is more convenient here
      # In retrospect, numpy array should have been the standard
      bounds = np.array(bounds)
      lb = bounds[:, 0]
      ub = bounds[:, 1]
      lb[np.equal(lb, None)] = -np.inf
      ub[np.equal(ub, None)] = np.inf
      bounds = bounds.astype(float)
      lb = lb.astype(float)
      ub = ub.astype(float)
  
      m_eq, n = A_eq.shape
      m_ub, n = A_ub.shape
  
      if sps.issparse(A_eq):
          A_eq = A_eq.tolil()
          A_ub = A_ub.tolil()
  
          def where(A):
              return A.nonzero()
  
          vstack = sps.vstack
      else:
          where = np.where
          vstack = np.vstack
  
      # zero row in equality constraints
      zero_row = np.array(np.sum(A_eq != 0, axis=1) == 0).flatten()
      if np.any(zero_row):
          if np.any(
              np.logical_and(zero_row, np.abs(b_eq) > tol)
          ):  # test_zero_row_1
              # infeasible if RHS is not zero
              status = 2
              message = (
                  "The problem is (trivially) infeasible due to a row "
                  "of zeros in the equality constraint matrix with a "
                  "nonzero corresponding constraint value."
              )
              complete = True
              return (
                  c,
                  c0,
                  A_ub,
                  b_ub,
                  A_eq,
                  b_eq,
                  bounds,
                  x,
                  undo,
                  complete,
                  status,
                  message,
              )
          else:  # test_zero_row_2
              # if RHS is zero, we can eliminate this equation entirely
              A_eq = A_eq[np.logical_not(zero_row), :]
              b_eq = b_eq[np.logical_not(zero_row)]
  
      # zero row in inequality constraints
      zero_row = np.array(np.sum(A_ub != 0, axis=1) == 0).flatten()
      if np.any(zero_row):
          if np.any(
              np.logical_and(zero_row, b_ub < -tol)
          ):  # test_zero_row_1
              # infeasible if RHS is less than zero (because LHS is zero)
              status = 2
              message = (
                  "The problem is (trivially) infeasible due to a row "
                  "of zeros in the equality constraint matrix with a "
                  "nonzero corresponding  constraint value."
              )
              complete = True
              return (
                  c,
                  c0,
                  A_ub,
                  b_ub,
                  A_eq,
                  b_eq,
                  bounds,
                  x,
                  undo,
                  complete,
                  status,
                  message,
              )
          else:  # test_zero_row_2
              # if LHS is >= 0, we can eliminate this constraint entirely
              A_ub = A_ub[np.logical_not(zero_row), :]
              b_ub = b_ub[np.logical_not(zero_row)]
  
      # zero column in (both) constraints
      # this indicates that a variable isn't constrained and can be removed
      A = vstack((A_eq, A_ub))
      if A.shape[0] > 0:
          zero_col = np.array(np.sum(A != 0, axis=0) == 0).flatten()
          # variable will be at upper or lower bound, depending on objective
          x[np.logical_and(zero_col, c < 0)] = ub[
              np.logical_and(zero_col, c < 0)
          ]
          x[np.logical_and(zero_col, c > 0)] = lb[
              np.logical_and(zero_col, c > 0)
          ]
          if np.any(
              np.isinf(x)
          ):  # if an unconstrained variable has no bound
              status = 3
              message = (
                  "If feasible, the problem is (trivially) unbounded "
                  "due  to a zero column in the constraint matrices. If "
                  "you wish to check whether the problem is infeasible, "
                  "turn presolve off."
              )
              complete = True
              return (
                  c,
                  c0,
                  A_ub,
                  b_ub,
                  A_eq,
                  b_eq,
                  bounds,
                  x,
                  undo,
                  complete,
                  status,
                  message,
              )
          # variables will equal upper/lower bounds will be removed later
          lb[np.logical_and(zero_col, c < 0)] = ub[
              np.logical_and(zero_col, c < 0)
          ]
          ub[np.logical_and(zero_col, c > 0)] = lb[
              np.logical_and(zero_col, c > 0)
          ]
  
      # row singleton in equality constraints
      # this fixes a variable and removes the constraint
      singleton_row = np.array(np.sum(A_eq != 0, axis=1) == 1).flatten()
      rows = where(singleton_row)[0]
      cols = where(A_eq[rows, :])[1]
      if len(rows) > 0:
          for row, col in zip(rows, cols):
              val = b_eq[row] / A_eq[row, col]
              if not lb[col] - tol <= val <= ub[col] + tol:
                  # infeasible if fixed value is not within bounds
                  status = 2
                  message = (
                      "The problem is (trivially) infeasible because a "
                      "singleton row in the equality constraints is "
                      "inconsistent with the bounds."
                  )
                  complete = True
                  return (
                      c,
                      c0,
                      A_ub,
                      b_ub,
                      A_eq,
                      b_eq,
                      bounds,
                      x,
                      undo,
                      complete,
                      status,
                      message,
                  )
              else:
                  # sets upper and lower bounds at that fixed value - variable
                  # will be removed later
                  lb[col] = val
                  ub[col] = val
          A_eq = A_eq[np.logical_not(singleton_row), :]
          b_eq = b_eq[np.logical_not(singleton_row)]
  
      # row singleton in inequality constraints
      # this indicates a simple bound and the constraint can be removed
      # simple bounds may be adjusted here
      # After all of the simple bound information is combined here, get_Abc will
      # turn the simple bounds into constraints
      singleton_row = np.array(np.sum(A_ub != 0, axis=1) == 1).flatten()
      cols = where(A_ub[singleton_row, :])[1]
      rows = where(singleton_row)[0]
      if len(rows) > 0:
          for row, col in zip(rows, cols):
              val = b_ub[row] / A_ub[row, col]
              if A_ub[row, col] > 0:  # upper bound
                  if val < lb[col] - tol:  # infeasible
                      complete = True
                  elif val < ub[col]:  # new upper bound
                      ub[col] = val
              else:  # lower bound
                  if val > ub[col] + tol:  # infeasible
                      complete = True
                  elif val > lb[col]:  # new lower bound
                      lb[col] = val
              if complete:
                  status = 2
                  message = (
                      "The problem is (trivially) infeasible because a "
                      "singleton row in the upper bound constraints is "
                      "inconsistent with the bounds."
                  )
                  return (
                      c,
                      c0,
                      A_ub,
                      b_ub,
                      A_eq,
                      b_eq,
                      bounds,
                      x,
                      undo,
                      complete,
                      status,
                      message,
                  )
          A_ub = A_ub[np.logical_not(singleton_row), :]
          b_ub = b_ub[np.logical_not(singleton_row)]
  
      # identical bounds indicate that variable can be removed
      i_f = np.abs(lb - ub) < tol  # indices of "fixed" variables
      i_nf = np.logical_not(i_f)  # indices of "not fixed" variables
  
      # test_bounds_equal_but_infeasible
      if np.all(
          i_f
      ):  # if bounds define solution, check for consistency
          residual = b_eq - A_eq.dot(lb)
          slack = b_ub - A_ub.dot(lb)
          if (A_ub.size > 0 and np.any(slack < 0)) or (
              A_eq.size > 0 and not np.allclose(residual, 0)
          ):
              status = 2
              message = (
                  "The problem is (trivially) infeasible because the "
                  "bounds fix all variables to values inconsistent with "
                  "the constraints"
              )
              complete = True
              return (
                  c,
                  c0,
                  A_ub,
                  b_ub,
                  A_eq,
                  b_eq,
                  bounds,
                  x,
                  undo,
                  complete,
                  status,
                  message,
              )
  
      ub_mod = ub
      lb_mod = lb
      if np.any(i_f):
          c0 += c[i_f].dot(lb[i_f])
          b_eq = b_eq - A_eq[:, i_f].dot(lb[i_f])
          b_ub = b_ub - A_ub[:, i_f].dot(lb[i_f])
          c = c[i_nf]
          x = x[i_nf]
          A_eq = A_eq[:, i_nf]
          A_ub = A_ub[:, i_nf]
          # record of variables to be added back in
          undo = [np.nonzero(i_f)[0], lb[i_f]]
          # don't remove these entries from bounds; they'll be used later.
          # but we _also_ need a version of the bounds with these removed
          lb_mod = lb[i_nf]
          ub_mod = ub[i_nf]
  
      # no constraints indicates that problem is trivial
      if A_eq.size == 0 and A_ub.size == 0:
          b_eq = np.array([])
          b_ub = np.array([])
          # test_empty_constraint_1
          if c.size == 0:
              status = 0
              message = (
                  "The solution was determined in presolve as there are "
                  "no non-trivial constraints."
              )
          elif np.any(
              np.logical_and(c < 0, ub_mod == np.inf)
          ) or np.any(np.logical_and(c > 0, lb_mod == -np.inf)):
              # test_no_constraints()
              # test_unbounded_no_nontrivial_constraints_1
              # test_unbounded_no_nontrivial_constraints_2
              status = 3
              message = (
                  "The problem is (trivially) unbounded "
                  "because there are no non-trivial constraints and "
                  "a) at least one decision variable is unbounded "
                  "above and its corresponding cost is negative, or "
                  "b) at least one decision variable is unbounded below "
                  "and its corresponding cost is positive. "
              )
          else:  # test_empty_constraint_2
              status = 0
              message = (
                  "The solution was determined in presolve as there are "
                  "no non-trivial constraints."
              )
          complete = True
          x[c < 0] = ub_mod[c < 0]
          x[c > 0] = lb_mod[c > 0]
          # where c is zero, set x to a finite bound or zero
          x_zero_c = ub_mod[c == 0]
          x_zero_c[np.isinf(x_zero_c)] = ub_mod[c == 0][
              np.isinf(x_zero_c)
          ]
          x_zero_c[np.isinf(x_zero_c)] = 0
          x[c == 0] = x_zero_c
          # if this is not the last step of presolve, should convert bounds back
          # to array and return here
  
      # *sigh* - convert bounds back to their standard form (list of tuples)
      # again, in retrospect, numpy array would be standard form
      lb[np.equal(lb, -np.inf)] = None
      ub[np.equal(ub, np.inf)] = None
      bounds = np.hstack((lb[:, np.newaxis], ub[:, np.newaxis]))
      bounds = bounds.tolist()
      for i, row in enumerate(bounds):
          for j, col in enumerate(row):
              if str(col) == "nan":  # comparing col to float("nan") and
                  # np.nan doesn't work. should use np.isnan
                  bounds[i][j] = None
  
      # remove redundant (linearly dependent) rows from equality constraints
      n_rows_A = A_eq.shape[0]
      redundancy_warning = (
          "A_eq does not appear to be of full row rank. To "
          "improve performance, check the problem formulation "
          "for redundant equality constraints."
      )
      if sps.issparse(A_eq):
          if rr and A_eq.size > 0:  # TODO: Fast sparse rank check?
              A_eq, b_eq, status, message = _remove_redundancy_sparse(
                  A_eq, b_eq
              )
              if A_eq.shape[0] < n_rows_A:
                  warn(redundancy_warning, OptimizeWarning)
              if status != 0:
                  complete = True
          return (
              c,
              c0,
              A_ub,
              b_ub,
              A_eq,
              b_eq,
              bounds,
              x,
              undo,
              complete,
              status,
              message,
          )
  
      # This is a wild guess for which redundancy removal algorithm will be
      # faster. More testing would be good.
      small_nullspace = 5
      if rr and A_eq.size > 0:
          try:  # TODO: instead use results of first SVD in _remove_redundancy
              rank = np.linalg.matrix_rank(A_eq)
          except (
              Exception
          ):  # oh well, we'll have to go with _remove_redundancy_dense
              rank = 0
      if rr and A_eq.size > 0 and rank < A_eq.shape[0]:
          warn(redundancy_warning, OptimizeWarning)
          dim_row_nullspace = A_eq.shape[0] - rank
          if dim_row_nullspace <= small_nullspace:
              A_eq, b_eq, status, message = _remove_redundancy(
                  A_eq, b_eq
              )
          if dim_row_nullspace > small_nullspace or status == 4:
              A_eq, b_eq, status, message = _remove_redundancy_dense(
                  A_eq, b_eq
              )
          if A_eq.shape[0] < rank:
              message = (
                  "Due to numerical issues, redundant equality "
                  "constraints could not be removed automatically. "
                  "Try providing your constraint matrices as sparse "
                  "matrices to activate sparse presolve, try turning "
                  "off redundancy removal, or try turning off presolve "
                  "altogether."
              )
              status = 4
          if status != 0:
              complete = True
      return (
          c,
          c0,
          A_ub,
          b_ub,
          A_eq,
          b_eq,
          bounds,
          x,
          undo,
          complete,
          status,
          message,
      )
  
file_path: catboost/contrib/python/scipy/py2/scipy/optimize/_linprog_util.py
imports: import numpy
  import scipy.sparse
  from warnings import warn
  from .optimize import OptimizeWarning
  from scipy.optimize._remove_redundancy import _remove_redundancy, _remove_redundancy_sparse, _remove_redundancy_dense
label_desc: Use image node_id 3 for calling a global function with example usage: _presolve(c, A_ub, b_ub, A_eq, b_eq, bounds, rr, tol) and returns: c,  c0,  A_ub,  b_ub,  A_eq,  b_eq,  bounds,  x,  undo,  complete,  status,  message, c,  c0,  A_ub,  b_ub,  A_eq,  b_eq,  bounds,  x,  undo,  complete,  status,  message, A, c,  c0,  A_ub,  b_ub,  A_eq,  b_eq,  bounds,  x,  undo,  complete,  status,  message, c,  c0,  A_ub,  b_ub,  A_eq,  b_eq,  bounds,  x,  undo,  complete,  status,  message, c,  c0,  A_ub,  b_ub,  A_eq,  b_eq,  bounds,  x,  undo,  complete,  status,  message, c,  c0,  A_ub,  b_ub,  A_eq,  b_eq,  bounds,  x,  undo,  complete,  status,  message, c,  c0,  A_ub,  b_ub,  A_eq,  b_eq,  bounds,  x,  undo,  complete,  status,  message, c,  c0,  A_ub,  b_ub,  A_eq,  b_eq,  bounds,  x,  undo,  complete,  status,  message