Offline Solvers Module¶
Available solvers for the Offline Packing LP Problem, already adapted to work with the provided Online Solvers.
Note¶
We recommend the python_mip_solver.PythonMIPSolver since it’s more flexible and usually faster.
Base Solver¶
-
class
offline_solvers.base_solver.BaseSolver(values: List[List[Union[int, float]]], costs: List[List[List[Union[int, float]]]], capacity: float)[source]¶ Abstract class unifying methods for the offline solvers.
- Parameters
- valueslist of list of (int or float)
A list of instants, where each instant contains is a list of the available values of that instant.
- costslist of list of list of (int or float)
A list of instants, where each instant is a list of options available, and each option is a list containing this option’s costs for each dimension.
- capacityfloat
The capacity of each dimension (each dimension have the same capacity).
- Attributes
- optimum_valuefloat or int
The optimum value found for the LP problem.
- packed_itemslist of int
A list containing the indexes of the items chosen in each instant.
- packed_weight_sumlist of float
A list containing the optimal solution’s total cost for each dimension.
Methods
solve()
Abstract method, should solve the LP problem.
print_result()
Prints a report containing the optimum solution and the total weights in each dimension.
Google Knapsack Solver¶
-
class
offline_solvers.google_knapsack_solver.GoogleKnapsackSolver(values: List[List[Union[int, float]]], costs: List[List[List[Union[int, float]]]], capacity: float, decimal_places: int = 6)[source]¶ Google OR-Tools solver for the multi-dimensional Knapsack problem using integer values.
- Parameters
- values
Refer to the BaseSolver parameters.
- costs
Refer to the BaseSolver parameters.
- capacity
Refer to the BaseSolver parameters.
- decimal_placesint
Decimal precision used to scale floats in values and costs into integers.
Notes
The google solver used here does not accept floating point numbers, as it considers the problem as a discrete one. Thus, we multiply every value, cost and capacity by \(10^n\) where \(n\) is decimal_places.
Also, this solver only accepts one item options per instant.
Validity Conditions: Also, there are variantions of the packing problem. Some allow the algorithm to do nothing, not packing any item, in an instant. Some compel the algorithm to make a choice in every instant. The google solver only accepts instances where it is not required to pack an item in every instant. This solver also only accepts instances where there is only one item available per instant.
Read more about the Google OR-Tools Knapsack Solver.
- Attributes
- optimum_valuefloat or int
The optimum value found for the LP problem.
- packed_itemslist of int
A list containing the indexes of the items chosen in each instant.
- packed_weight_sumlist of float
A list containing the optimal solution’s total cost for each dimension.
- solver
The instance of the used OR-Tools pywrapknapsack_solver.KnapsackSolver solver.
- adapted_valueslist of int
values scaled into an integer using decimal_places decimal places as precision.
- adapted_costslist of list of int
costs scaled into an integer using decimal_places decimal places as precision.
- adapted_capacitylist of int
A list with, for every cost dimension, the same capacity scaled into an integer using decimal_places decimal places as precision.
- decimal_placesint
Decimal precision used to scale floats in values and costs into integers.
Methods
solve()
Solves the LP problem.
print_result()
Inherited from BaseSolver.
validate_instance(values, costs)
Check if an offline packing LP instance is valid for this solver.
-
solve()[source]¶ Try to solve the LP problem and sets optimum_value, packed_items and packed_weight_sum.
- Returns
- None
-
static
validate_instance(values: List[List[Union[int, float]]], costs: List[List[List[Union[int, float]]]]) → None[source]¶ Check if a given instance is valid for this solver. Refer to the Notes to check validity conditions.
- Parameters
- values
Values for the instance. For format, refer to BaseSolver parameters.
- costs
Costs for the instance. For format, refer to BaseSolver parameters.
- Returns
- None
- Raises
- Exception
If problem instance is not valid.
Python-MIP Solver¶
-
class
offline_solvers.python_mip_solver.PythonMIPSolver(values: List[List[Union[int, float]]], costs: List[List[List[Union[int, float]]]], capacity: Union[float, int], max_seconds: int = 30)[source]¶ Python-MIP Solver, used to model and solve the offline Packing LP Problem, using a COIN-OR Branch and Cut (CBC) solver.
- Parameters
- values
Refer to the BaseSolver parameters.
- costs
Refer to the BaseSolver parameters.
- capacity
Refer to the BaseSolver parameters.
- max_secondsint, default=30
Maximum time spent searching for better solutions, in seconds.
Notes
This is a Mixed Integer Programming modeler and solver, being much more flexible than the Google Knapsack Solver, accepting all types of variantions of the problem: more than one item per instant, obligatory packing or flexible packing.
Read more about the Python-MIP Solver.
- Attributes
- optimum_valuefloat or int
The optimum value found for the LP problem.
- packed_itemslist of int
A list containing the indexes of the items chosen in each instant.
- packed_weight_sumlist of float
A list containing the optimal solution’s total cost for each dimension.
- solver
The instance of the Python-MIP solver.
- max_secondsint
Maximum time spent searching for better solutions, in seconds.
- status{mip.OptimizationStatus.OPTIMAL, mip.OptimizationStatus.FEASIBLE, mip.OptimizationStatus.INFEASIBLE}
Result of the optimization procedure.
Methods
solve()
Solves the LP problem.
print_result()
Inherited from BaseSolver.