# Copyright (c) 2022 AIRBUS and its affiliates.
# This source code is licensed under the MIT license found in the
# LICENSE file in the root directory of this source tree.
import logging
import os
import random
from collections.abc import Iterable, Sequence
from typing import Any, Optional
from minizinc import Instance, Model, Solver
from discrete_optimization.generic_tools.cp_tools import (
CpSolverName,
MinizincCpSolver,
find_right_minizinc_solver_name,
)
from discrete_optimization.generic_tools.do_problem import ParamsObjectiveFunction
from discrete_optimization.generic_tools.hyperparameters.hyperparameter import (
EnumHyperparameter,
FloatHyperparameter,
)
from discrete_optimization.generic_tools.lns_cp import MznConstraintHandler
from discrete_optimization.generic_tools.result_storage.result_storage import (
ResultStorage,
)
from discrete_optimization.knapsack.problem import (
KnapsackProblem,
KnapsackSolution,
MultidimensionalKnapsackProblem,
MultidimensionalKnapsackSolution,
MultiScenarioMultidimensionalKnapsackProblem,
)
from discrete_optimization.knapsack.solvers import KnapsackSolver
logger = logging.getLogger(__name__)
this_path = os.path.dirname(os.path.abspath(__file__))
[docs]
class CpKnapsackSolver(MinizincCpSolver, KnapsackSolver):
hyperparameters = [
EnumHyperparameter(
name="cp_solver_name", enum=CpSolverName, default=CpSolverName.CHUFFED
)
]
def __init__(
self,
problem: KnapsackProblem,
params_objective_function: Optional[ParamsObjectiveFunction] = None,
silent_solve_error: bool = False,
**kwargs: Any,
):
super().__init__(
problem=problem, params_objective_function=params_objective_function
)
self.silent_solve_error = silent_solve_error
self.key_decision_variable = ["list_items"]
[docs]
def retrieve_solution(
self, _output_item: Optional[str] = None, **kwargs: Any
) -> KnapsackSolution:
"""Return a d-o solution from the variables computed by minizinc.
Args:
_output_item: string representing the minizinc solver output passed by minizinc to the solution constructor
**kwargs: keyword arguments passed by minzinc to the solution contructor
containing the objective value (key "objective"),
and the computed variables as defined in minizinc model.
Returns:
"""
items = kwargs["list_items"]
taken = [0] * self.problem.nb_items
weight = 0
value = 0
for i in range(len(items)):
if items[i] != 0:
taken[items[i] - 1] = 1
weight += self.problem.list_items[items[i] - 1].weight
value += self.problem.list_items[items[i] - 1].value
return KnapsackSolution(
problem=self.problem,
value=value,
weight=weight,
list_taken=taken,
)
[docs]
def init_model(self, **kwargs: Any) -> None:
kwargs = self.complete_with_default_hyperparameters(kwargs)
cp_solver_name = kwargs["cp_solver_name"]
model = Model(os.path.join(this_path, "../minizinc/knapsack_mzn.mzn"))
solver = Solver.lookup(find_right_minizinc_solver_name(cp_solver_name))
instance = Instance(solver, model)
instance["nb_items"] = self.problem.nb_items
instance["values"] = [0] + [
self.problem.list_items[i].value for i in range(self.problem.nb_items)
]
instance["weights"] = [0] + [
self.problem.list_items[i].weight for i in range(self.problem.nb_items)
]
instance["max_capacity"] = self.problem.max_capacity
self.instance = instance
[docs]
class Cp2KnapsackSolver(MinizincCpSolver, KnapsackSolver):
hyperparameters = [
EnumHyperparameter(
name="cp_solver_name", enum=CpSolverName, default=CpSolverName.CHUFFED
)
]
def __init__(
self,
problem: KnapsackProblem,
params_objective_function: Optional[ParamsObjectiveFunction] = None,
silent_solve_error: bool = False,
**kwargs: Any,
):
super().__init__(
problem=problem, params_objective_function=params_objective_function
)
self.silent_solve_error = silent_solve_error
[docs]
def init_model(self, **kwargs: Any) -> None:
kwargs = self.complete_with_default_hyperparameters(kwargs)
cp_solver_name = kwargs["cp_solver_name"]
model = Model(os.path.join(this_path, "../minizinc/knapsack_global.mzn"))
solver = Solver.lookup(find_right_minizinc_solver_name(cp_solver_name))
instance = Instance(solver, model)
instance["nb_items"] = self.problem.nb_items
instance["values"] = [
self.problem.list_items[i].value for i in range(self.problem.nb_items)
]
instance["weights"] = [
self.problem.list_items[i].weight for i in range(self.problem.nb_items)
]
instance["max_capacity"] = self.problem.max_capacity
self.instance = instance
[docs]
def retrieve_solution(
self, _output_item: Optional[str] = None, **kwargs: Any
) -> KnapsackSolution:
"""Return a d-o solution from the variables computed by minizinc.
Args:
_output_item: string representing the minizinc solver output passed by minizinc to the solution constructor
**kwargs: keyword arguments passed by minzinc to the solution contructor
containing the objective value (key "objective"),
and the computed variables as defined in minizinc model.
Returns:
"""
items_taken = kwargs["taken"]
taken = [0] * self.problem.nb_items
weight = 0.0
value = 0.0
for i in range(len(items_taken)):
if items_taken[i] != 0:
taken[
self.problem.index_to_index_list[self.problem.list_items[i].index]
] = 1
weight += self.problem.list_items[i].weight
value += self.problem.list_items[i].value
return KnapsackSolution(
problem=self.problem,
value=value,
weight=weight,
list_taken=taken,
)
[docs]
class CpMultidimensionalKnapsackSolver(MinizincCpSolver):
problem: MultidimensionalKnapsackProblem
hyperparameters = [
EnumHyperparameter(
name="cp_solver_name", enum=CpSolverName, default=CpSolverName.CHUFFED
)
]
def __init__(
self,
problem: MultidimensionalKnapsackProblem,
params_objective_function: Optional[ParamsObjectiveFunction] = None,
silent_solve_error: bool = False,
**kwargs: Any,
):
super().__init__(
problem=problem, params_objective_function=params_objective_function
)
self.silent_solve_error = silent_solve_error
self.key_decision_variable = ["list_items"]
[docs]
def init_model(self, **kwargs: Any) -> None:
kwargs = self.complete_with_default_hyperparameters(kwargs)
cp_solver_name = kwargs["cp_solver_name"]
model = Model(
os.path.join(this_path, "../minizinc/multidimension_knapsack.mzn")
)
solver = Solver.lookup(find_right_minizinc_solver_name(cp_solver_name))
instance = Instance(solver, model)
instance["nb_items"] = self.problem.nb_items
instance["nb_dimension"] = len(self.problem.max_capacities)
instance["values"] = [
int(self.problem.list_items[i].value) for i in range(self.problem.nb_items)
]
instance["weights"] = [
[
self.problem.list_items[i].weights[j]
for j in range(instance["nb_dimension"])
]
for i in range(self.problem.nb_items)
]
instance["max_capacity"] = self.problem.max_capacities
self.instance = instance
[docs]
def retrieve_solution(
self, _output_item: Optional[str] = None, **kwargs: Any
) -> MultidimensionalKnapsackSolution:
"""Return a d-o solution from the variables computed by minizinc.
Args:
_output_item: string representing the minizinc solver output passed by minizinc to the solution constructor
**kwargs: keyword arguments passed by minzinc to the solution contructor
containing the objective value (key "objective"),
and the computed variables as defined in minizinc model.
Returns:
"""
taken = kwargs["taken"]
return MultidimensionalKnapsackSolution(problem=self.problem, list_taken=taken)
[docs]
class CpMultidimensionalMultiScenarioKnapsackSolver(MinizincCpSolver):
problem: MultiScenarioMultidimensionalKnapsackProblem
hyperparameters = [
EnumHyperparameter(
name="cp_solver_name", enum=CpSolverName, default=CpSolverName.CHUFFED
)
]
def __init__(
self,
problem: MultiScenarioMultidimensionalKnapsackProblem,
params_objective_function: Optional[ParamsObjectiveFunction] = None,
silent_solve_error: bool = False,
**kwargs: Any,
):
super().__init__(
problem=problem, params_objective_function=params_objective_function
)
self.silent_solve_error = silent_solve_error
self.key_decision_variable = ["list_items"]
[docs]
def init_model(self, **kwargs: Any) -> None:
kwargs = self.complete_with_default_hyperparameters(kwargs)
cp_solver_name = kwargs["cp_solver_name"]
model = Model(
os.path.join(this_path, "../minizinc/multidim_multiscenario_knapsack.mzn")
)
solver = Solver.lookup(find_right_minizinc_solver_name(cp_solver_name))
instance = Instance(solver, model)
list_problems: Sequence[
MultidimensionalKnapsackProblem
] = self.problem.list_problem
instance["nb_items"] = list_problems[0].nb_items
instance["nb_dimension"] = len(list_problems[0].max_capacities)
instance["nb_scenario"] = len(list_problems)
instance["values"] = [
[
int(list_problems[j].list_items[i].value)
for j in range(instance["nb_scenario"])
]
for i in range(instance["nb_items"])
]
instance["weights"] = [
[
[
list_problems[k].list_items[i].weights[j]
for k in range(instance["nb_scenario"])
]
for j in range(instance["nb_dimension"])
]
for i in range(instance["nb_items"])
]
instance["max_capacity"] = [
[list_problems[s].max_capacities[k] for s in range(instance["nb_scenario"])]
for k in range(instance["nb_dimension"])
]
self.instance = instance
[docs]
def retrieve_solution(
self, _output_item: Optional[str] = None, **kwargs: Any
) -> MultidimensionalKnapsackSolution:
"""Return a d-o solution from the variables computed by minizinc.
Args:
_output_item: string representing the minizinc solver output passed by minizinc to the solution constructor
**kwargs: keyword arguments passed by minzinc to the solution contructor
containing the objective value (key "objective"),
and the computed variables as defined in minizinc model.
Returns:
"""
taken = kwargs["taken"]
return MultidimensionalKnapsackSolution(problem=self.problem, list_taken=taken)
[docs]
class KnapsackConstraintHandler(MznConstraintHandler):
hyperparameters = [
FloatHyperparameter(name="fraction_fix", default=0.95, low=0.0, high=1.0),
]
def __init__(self, fraction_fix: float = 0.95):
self.fraction_fix = fraction_fix
[docs]
def adding_constraint_from_results_store(
self,
solver: MinizincCpSolver,
child_instance: Instance,
result_storage: ResultStorage,
last_result_store: Optional[ResultStorage] = None,
**kwargs: Any,
) -> Iterable[Any]:
if not isinstance(solver, CpMultidimensionalMultiScenarioKnapsackSolver):
raise ValueError(
"cp_solver must a CPMultidimensionalMultiScenarioSolver for this constraint."
)
if last_result_store is None:
raise ValueError("This constraint need last_result_store to be not None.")
strings = []
nb_item = solver.problem.list_problem[0].nb_items
range_item = range(nb_item)
subpart_item = set(random.sample(range_item, int(self.fraction_fix * nb_item)))
current_best_solution = last_result_store.get_last_best_solution()[0]
if not isinstance(
current_best_solution, (KnapsackSolution, MultidimensionalKnapsackSolution)
):
raise RuntimeError(
"current_best_solution must be a KnapsackSolution "
"or a KnapsackSolutionMultidimensional."
)
for i in range_item:
if i in subpart_item:
strings += [
"constraint taken["
+ str(i + 1)
+ "] == "
+ str(1 if current_best_solution.list_taken[i] else 0)
+ ";\n"
]
child_instance.add_string(strings[-1])
return strings