Data hosted with ♥ by Pastebin.com - Download Raw - See Original
  1. import numpy as np
  2. from typing import Tuple
  3.  
  4.  
  5. class SimpleLP:
  6. """
  7. Represents simple LP problem with tableau and indexing-vector of basis-columns
  8.  
  9. members:
  10. self.tableau - stored simplex tableau
  11.  
  12. self.basis - contains ordered indices of identity submatrix within tableau.
  13. This enables reading the solution from tableau
  14. """
  15.  
  16. def init(self, A, b, c):
  17. """Creates simplex tableau assuming canonical form and b>=0 (self.tableau)
  18.  
  19. Also creates an index-vector of basis-columns in the tableau (self.basis).
  20.  
  21.  
  22. Args:
  23. A (np.array): canonical LP A (matrix)
  24. b (np.array): canonical LP b (1-D vector)
  25. c (np.array): canonical LP c (1-D vector)
  26. """
  27. c = np.array(c)
  28. b = np.array(b)
  29. A = np.array(A)
  30. m = A.shape[0]
  31. n = c.shape[0]
  32.  
  33. zeroth_row = np.hstack([c, [0] * (m + 1)])
  34. bottom_pack = np.hstack((A, np.identity(m), b.reshape(m, 1)))
  35.  
  36. self.tableau = np.vstack((zeroth_row, bottom_pack))
  37.  
  38. self.basis = np.arange(n, n + m) # identity submatrix in such specific problems is in the last columns
  39.  
  40. def readSolution(self) -> Tuple[np.float32, np.array]:
  41. """Reads off the full solution from the tableau
  42.  
  43. Returns:
  44. Tuple[np.float32, np.array]: returns objective value and 1-D vector of decisions
  45. """
  46.  
  47. # TODO: add your code for objective function value here (None is not solution)
  48. obj = None
  49.  
  50. decisions = np.zeros((self.tableau.shape[1] - 1))
  51. decisions[self.basis] = self.tableau[1:, -1]
  52.  
  53. return obj, decisions
  54.  
  55.  
  56. class NaiveSimplex:
  57. """
  58.  
  59. Represents all functionalities of "naive" simplex
  60.  
  61. Raises:
  62. ValueError: if pivot row is 0
  63.  
  64. """
  65.  
  66. @staticmethod
  67. def pivot(lp_problem: SimpleLP, row: int, col: int) -> SimpleLP:
  68. """Does Gauss-Jordan elimination around the (row,col)
  69. element of simplex tableau
  70.  
  71. Args:
  72. lp_problem (SimpleLP): LP over which to operate
  73. row (int): pivot's row
  74. col (int): pivot's column
  75.  
  76. Raises:
  77. ValueError: pivot cannot be in the row of the reduction factors
  78.  
  79. Returns:
  80. SimpleLP: returns reference to LP (for chaining)
  81. """
  82.  
  83. if row == 0: # cannot pivot around zeroth row in tableau
  84. raise ValueError
  85.  
  86. # TODO: add your code here - tableau must be pivoted and basis updated (watch the order in basis vector!)
  87.  
  88. return lp_problem
  89.  
  90. @staticmethod
  91. def solve(lp_problem: SimpleLP) -> SimpleLP:
  92. """Solves the input LP
  93.  
  94. Args:
  95. lp_problem (SimpleLP): Input LP to be solved
  96.  
  97. Returns:
  98. SimpleLP: returns None if the problem is unbounded, or reference to the LP otherwise
  99. """
  100.  
  101. # TODO: add your code here - should call pivot method, like this: NaiveSimplex.pivot(lp_problem)
  102.  
  103. return lp_problem