Online Solver Module¶
This module contains an algorithm to solve the Online Packing Problem.
Notes¶
The algorithm implemented here to solve the online packing problem is described in [1], on section 6, as Algorithm 6.1. It uses the MWU (Multiplicative Weights Update) method, as described in [2], and Integer/Linear prorgamming solvers. Hence the Mwu-Max and the Offline Solvers modules.
References¶
- 1
Agrawal, Shipra & Devanur, Nikhil. (2014). Fast Algorithms for Online Stochastic Convex Programming. Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms. 2015. 10.1137/1.9781611973730.93.
- 2
Arora, Sanjeev & Hazan, Elad & Kale, Satyen. (2012). The Multiplicative Weights Update Method: a Meta Algorithm and Applications. Theory of Computing [electronic only]. 8. 10.4086/toc.2012.v008a006.
-
class
online_solver.OnlineSolver(cost_dimension: int, total_time: int, capacity: float, e: Optional[float] = None, solver_cls: Type[fast_online_packing.offline_solvers.base_solver.BaseSolver] = <class 'fast_online_packing.offline_solvers.python_mip_solver.PythonMIPSolver'>)[source]¶ Solves the Online Packing Problem.
- Parameters
- cost_dimensionint
Dimension of the cost vectors to be used.
- total_timeint
Total number of instants.
- capacityfloat
Capacity restriction of the problem instance.
- efloat or None, default=None
Epsilon parameter to be used in the algorithm. If none is given, a theorical optimum epsilon is set.
- solver_clsType[BaseSolver]
Offline solver to be used.
- Attributes
- pPackingProblem
Packing Problem instance, that holds and enforces all problem-related aspects.
- efloat
Epsilon parameter used in the algorithm.
- mwuMwuMax
MWU instance.
- zUnion[float, None]
Algorithm calculated parameter Z.
- deltafloat
Decimal fraction of instants used to estimate Z.
- total_timeint
Total number of instants in the algorithm.
- current_timeint
Count of the instant the algorithm currently is. 1-indexed.
- optimum_valuefloat
Sum of the values of the items packed in the optimal solution (solving offline).
- cost_dimensionint
Property that gets the dimension of the problem instance’s cost vectors.
Methods
print_params()
Print parameters used in the algorithm.
pack_one(available_values, available_costs)
Choose one of the given items to pack on the current instant.
compute_optimum()
Solves the offline problem for the previously set instants, in order to find the optimum solution.
print_result()
Print a results report.
get_premises_min()
Gets the minimum value of the capacity and optimum-value-sum so that premises and theoric guarantees are valid.
respect_premises()
Informs if the algorithm is in agreement with the theoric premises.
-
compute_optimum() → float[source]¶ Solve the problem offline to find out the optimum solution.
- Returns
- The optimum solution for the problem.
-
get_premises_min() → float[source]¶ Get the minimum value of capacity and optimum_value for the premises to be valid.
- Returns
- float
Minimum value of capacity and optimum_value for premises to be valid.
-
pack_one(available_values: List[float], available_costs: List[List[float]]) → int[source]¶ Receives the new instant’s items and chooses one to pack.
- Parameters
- available_valueslist of float
Value of the items available on the current instant.
- available_costslist of list of float
Cost vectors of the items available on the current instant.
- Returns
- int
Index of the chosen item or -1 if none of the items were packed.