# 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,
result_storage: ResultStorage,
result_storage_last_iteration: ResultStorage,
child_instance: Instance,
**kwargs: Any,
) -> Iterable[Any]:
"""Add constraints to the internal model of a solver based on previous solutions
Args:
solver: solver whose internal model is updated
result_storage: all results so far
result_storage_last_iteration: results from last LNS iteration only
child_instance: minizinc instance where to include the constraints
**kwargs:
Returns:
empty list, not used
"""
if not isinstance(solver, CpMultidimensionalMultiScenarioKnapsackSolver):
raise ValueError(
"cp_solver must a CPMultidimensionalMultiScenarioSolver for this constraint."
)
if len(result_storage_last_iteration) == 0:
raise ValueError(
"This constraint need result_storage_last_iteration to be not empty."
)
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 = result_storage_last_iteration.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