discrete_optimization.rcpsp_multiskill.solvers package

Submodules

discrete_optimization.rcpsp_multiskill.solvers.cp_mspsp_instlib module

class discrete_optimization.rcpsp_multiskill.solvers.cp_mspsp_instlib.CpMspspMznMultiskillRcpspSolver(problem: MultiskillRcpspProblem, cp_solver_name: CpSolverName = CpSolverName.CHUFFED, params_objective_function: ParamsObjectiveFunction | None = None, silent_solve_error: bool = False, **kwargs)

Bases: MinizincCpSolver

constraint_end_time_string(task, end_time, sign: SignEnum = SignEnum.EQUAL) → str

constraint_objective_equal_makespan(task_sink)

constraint_objective_makespan()

constraint_objective_max_time_set_of_jobs(set_of_jobs)

constraint_start_time_string(task, start_time, sign: SignEnum = SignEnum.EQUAL) → str

constraint_sum_of_ending_time(set_subtasks: set[Hashable])

constraint_sum_of_starting_time(set_subtasks: set[Hashable])

constraint_task_to_mode(task_id, mode)

constraint_used_employee(task, employee, indicator: bool = False)

init_from_model(**args)

init_model(**args)

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

problem: MultiskillRcpspProblem

retrieve_solution(_output_item: str | None = None, **kwargs: Any) → MultiskillRcpspSolution

Return a d-o solution from the variables computed by minizinc.

Parameters:

• _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:

discrete_optimization.rcpsp_multiskill.solvers.cp_mspsp_instlib.chuffed_specific_code()

discrete_optimization.rcpsp_multiskill.solvers.cp_mspsp_instlib.create_usefull_res_data(rcpsp_problem: MultiskillRcpspProblem)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn module

class discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.CpMultiskillRcpspSolver(problem: MultiskillRcpspProblem, cp_solver_name: CpSolverName = CpSolverName.CHUFFED, params_objective_function: ParamsObjectiveFunction | None = None, silent_solve_error: bool = False, **kwargs)

Bases: MinizincCpSolver

add_hard_special_constraints(partial_solution)

constraint_end_time_string(task, end_time, sign: SignEnum = SignEnum.EQUAL) → str

constraint_objective_equal_makespan(task_sink)

constraint_objective_max_time_set_of_jobs(set_of_jobs)

constraint_start_time_string(task, start_time, sign: SignEnum = SignEnum.EQUAL) → str

constraint_sum_of_ending_time(set_subtasks: set[Hashable])

constraint_sum_of_starting_time(set_subtasks: set[Hashable])

constraint_task_to_mode(task_id, mode)

constraint_used_employee(task, employee, indicator: bool = False)

init_model(**args)

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

manual_cumulative_resource_constraints(instance)

manual_starting_time(instance)

problem: MultiskillRcpspProblem

retrieve_solution(_output_item: str | None = None, **kwargs: Any) → MultiskillRcpspSolution

Return a d-o solution from the variables computed by minizinc.

Parameters:

• _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:

write_search_strategy_chuffed(instance)

class discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.CpPartialPreemptiveMultiskillRcpspSolver(problem: MultiskillRcpspProblem, cp_solver_name: CpSolverName = CpSolverName.CHUFFED, params_objective_function: ParamsObjectiveFunction | None = None, silent_solve_error: bool = False, **kwargs)

Bases: CpPreemptiveMultiskillRcpspSolver

init_model(**args)

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

class discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.CpPreemptiveMultiskillRcpspSolver(problem: MultiskillRcpspProblem, cp_solver_name: CpSolverName = CpSolverName.CHUFFED, params_objective_function: ParamsObjectiveFunction | None = None, silent_solve_error: bool = False, **kwargs)

Bases: MinizincCpSolver

add_hard_special_constraints(partial_solution)

constraint_duration_string_preemptive_i(task, duration, part_id=1, sign: SignEnum = SignEnum.EQUAL) → str

constraint_duration_to_min_duration_preemptive(task, min_duration)

constraint_end_time_string(task, end_time, sign: SignEnum = SignEnum.EQUAL) → str

constraint_is_paused(task, is_paused)

constraint_objective_equal_makespan(task_sink)

constraint_objective_max_time_set_of_jobs(set_of_jobs)

constraint_start_time_string(task, start_time, sign: SignEnum = SignEnum.EQUAL) → str

constraint_start_time_string_preemptive_i(task, start_time, part_id=1, sign: SignEnum = SignEnum.EQUAL) → str

constraint_sum_of_ending_time(set_subtasks: set[Hashable])

constraint_sum_of_starting_time(set_subtasks: set[Hashable])

constraint_task_to_mode(task_id, mode)

constraint_used_employee(task, employee, part_id=1, indicator: bool = False)

init_model(**args)

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

problem: MultiskillRcpspProblem

retrieve_solution(_output_item: str | None = None, **kwargs: Any) → PreemptiveMultiskillRcpspSolution

Return a d-o solution from the variables computed by minizinc.

Parameters:

• _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:

class discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.PrecomputeEmployeesForTasks(ms_rcpsp_problem: MultiskillRcpspProblem, cp_solver_name: CpSolverName = CpSolverName.CHUFFED)

Bases: object

init_model(**kwargs)

retrieve_solutions(result, parameters_cp: ParametersCp)

solve(parameters_cp: ParametersCp | None = None, time_limit: float | None = 100.0, nr_solutions: int = 100, all_solutions: bool = False, **args)

Solve the CP problem with minizinc

Parameters:

• parameters_cp – parameters specific to CP solvers

• time_limit – the solve process stops after this time limit (in seconds). If None, no time limit is applied.

• nr_solutions – of not all_solutions, the solve stops after finding nr_solutions

• all_solutions – if True, do not stop when reaching nr_solutions

• **args – passed to init_model()

Returns:

class discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.SearchStrategyMultiskillRcpsp(value)

Bases: Enum

An enumeration.

NONE = 'none'

PRIORITY_SEARCH_START_UNIT_USED = 'priority_smallest'

START_THEN_USED_UNIT = 'durThenStartThenMode'

class discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.SolutionPrecomputeEmployeesForTasks(unit_used, worker_type_used, mode_dict, overskill_unit, overskill_type)

Bases: object

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.add_constraints_string(child_instance, list_of_strings)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.add_fake_task_cp_data(rcpsp_problem: MultiskillRcpspProblem, ignore_fake_task: bool = True, max_time_to_consider: int | None = None)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.add_hard_special_constraints(partial_solution: PartialSolution, cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.add_soft_special_constraints(partial_solution: PartialSolution, cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.define_second_part_objective(weights, name_penalty, equal=False)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.hard_end_window(end_times_window: dict[Hashable, tuple[int, int]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.hard_start_after_nunit(list_start_after_nunit: list[tuple[Hashable, Hashable, int]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.hard_start_at_end(list_start_at_end: list[tuple[Hashable, Hashable]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.hard_start_at_end_plus_offset(list_start_at_end_plus_offset, cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.hard_start_times(dict_start_times: dict[Hashable, int], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.hard_start_together(list_start_together: list[tuple[Hashable, Hashable]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.hard_start_window(start_times_window: dict[Hashable, tuple[int, int]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.soft_end_window(end_times_window: dict[Hashable, tuple[int, int]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.soft_start_after_nunit(list_start_after_nunit: list[tuple[Hashable, Hashable, int]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.soft_start_at_end(list_start_at_end: list[tuple[Hashable, Hashable]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.soft_start_at_end_plus_offset(list_start_at_end_plus_offset: list[tuple[Hashable, Hashable, int]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.soft_start_times(dict_start_times: dict[Hashable, int], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.soft_start_together(list_start_together: list[tuple[Hashable, Hashable]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.soft_start_window(start_times_window: dict[Hashable, tuple[int, int]], cp_solver: CpMultiskillRcpspSolver | CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.stick_to_solution(solution: RcpspSolution, cp_solver: CpMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cp_mzn.stick_to_solution_preemptive(solution: PreemptiveRcpspSolution, cp_solver: CpPreemptiveMultiskillRcpspSolver)

discrete_optimization.rcpsp_multiskill.solvers.cpsat module

class discrete_optimization.rcpsp_multiskill.solvers.cpsat.CpSatMultiskillRcpspSolver(problem: Problem, **kwargs: Any)

Bases: OrtoolsCpSatSolver

add_lexico_constraint(obj: str, value: float) → Iterable[Constraint]

Add a constraint on a computed sub-objective

Parameters:

• obj – a string representing the desired objective. Should be one of self.get_lexico_objectives_available().

• value – the limiting value. If the optimization direction is maximizing, this is a lower bound, else this is an upper bound.

Returns:

the created constraints.

constraint_mode()

constraint_precedence()

constraint_redundant_cumulative_skills()

constraint_redundant_cumulative_worker()

create_base_variable()

create_constraint_resource()

create_cost_objective_function()

create_cumulative_resource_constraint(res: str)

create_disjunctive_worker()

create_employee_intervals(one_worker_per_task: bool, one_skill_per_task: bool)

create_non_renewable_res_constraint(res: str)

create_opt_variable_modes()

create_skills_constraint_to_mode()

create_skills_constraint_worker(**args)

create_skills_constraints_v2(**args)

using skills_used variable

create_skills_variables()

create_workload_variables()

get_lexico_objective_value(obj: str, res: ResultStorage) → float

Get best internal model objective value found by last call to solve().

The default implementation consists in using the fit of the last solution in result_storage. This assumes: - that the last solution is the best one for the objective considered - that no aggregation was performed but rather that the fitness is a TupleFitness

with values in the same order as self.problem.get_objective_names().

Parameters:

• obj – a string representing the desired objective. Should be one of self.get_lexico_objectives_available().

• res – result storage returned by last call to solve().

Returns:

get_lexico_objectives_available() → List[str]

List objectives available for lexico optimization

It corresponds to the labels accepted for obj argument for - set_lexico_objective() - add_lexico_constraint() - get_lexico_objective_value()

Default to self.problem.get_objective_names().

Returns:

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='redundant_skill_cumulative', default=True, depends_on=None, name_in_kwargs='redundant_skill_cumulative'), CategoricalHyperparameter(name='redundant_worker_cumulative', default=True, depends_on=None, name_in_kwargs='redundant_worker_cumulative')]

Hyperparameters available for this solver.

These hyperparameters are to be feed to **kwargs found in

• __init__()

• init_model() (when available)

• solve()

static implements_lexico_api() → bool

Tell whether this solver is implementing the api for lexicographic optimization.

Should return True only if

• set_lexico_objective()

• add_lexico_constraint()

• get_lexico_objective_value()

have been really implemented, i.e. - calling set_lexico_objective() and add_lexico_constraint()

should actually change the next call to solve(),

• get_lexico_objective_value() should correspond to the internal model objective

init_model(**args: Any) → None

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

problem: MultiskillRcpspProblem

retrieve_solution(cpsolvercb: CpSolverSolutionCallback) → Solution

Construct a do solution from the cpsat solver internal solution.

It will be called each time the cpsat solver find a new solution. At that point, value of internal variables are accessible via cpsolvercb.Value(VARIABLE_NAME).

Parameters:

cpsolvercb – the ortools callback called when the cpsat solver finds a new solution.

Returns:

the intermediate solution, at do format.

set_lexico_objective(obj: str) → None

Update internal model objective.

Parameters:

obj – a string representing the desired objective. Should be one of self.get_lexico_objectives_available().

Returns:

discrete_optimization.rcpsp_multiskill.solvers.ga module

class discrete_optimization.rcpsp_multiskill.solvers.ga.GaMultiskillRcpspSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

problem: RcpspProblem

solve(parameters_ga: ParametersAltGa | None = None, **args)

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

discrete_optimization.rcpsp_multiskill.solvers.lns_lp module

class discrete_optimization.rcpsp_multiskill.solvers.lns_lp.InitialMultiskillRcpspSolution(problem: MultiskillRcpspProblem, params_objective_function: ParamsObjectiveFunction | None = None, initial_method: InitialRcpspMethod = InitialRcpspMethod.PILE)

Bases: InitialSolution

get_starting_solution() → ResultStorage

discrete_optimization.rcpsp_multiskill.solvers.lns_post_process module

class discrete_optimization.rcpsp_multiskill.solvers.lns_post_process.MultiskillRcpspPostProcessSolution(problem: MultiskillRcpspProblem, params_objective_function: ParamsObjectiveFunction | None = None)

Bases: PostProcessSolution

build_other_solution(result_storage: ResultStorage) → ResultStorage

class discrete_optimization.rcpsp_multiskill.solvers.lns_post_process.PreemptiveMultiskillRcpspPostProcessSolution(problem: MultiskillRcpspProblem, params_objective_function: ParamsObjectiveFunction | None = None)

Bases: PostProcessSolution

build_other_solution(result_storage: ResultStorage) → ResultStorage

discrete_optimization.rcpsp_multiskill.solvers.lns_post_process.compute_schedule_per_employees(solution: PreemptiveMultiskillRcpspSolution | MultiskillRcpspSolution, problem: MultiskillRcpspProblem, predecessors_dict)

discrete_optimization.rcpsp_multiskill.solvers.lns_post_process.sgs_variant(solution: MultiskillRcpspSolution, problem: MultiskillRcpspProblem, predecessors_dict)

discrete_optimization.rcpsp_multiskill.solvers.lns_post_process.sgs_variant_preemptive(solution: PreemptiveMultiskillRcpspSolution, problem: MultiskillRcpspProblem, predecessors_dict)

discrete_optimization.rcpsp_multiskill.solvers.lns_post_process.shift_left_method(solution: PreemptiveMultiskillRcpspSolution | MultiskillRcpspSolution, problem: MultiskillRcpspProblem, predecessors_dict)

discrete_optimization.rcpsp_multiskill.solvers.lp module

class discrete_optimization.rcpsp_multiskill.solvers.lp.MathOptMultiskillRcpspSolver(problem: MultiskillRcpspProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs)

Bases: OrtoolsMathOptMilpSolver

convert_to_variable_values(solution: MultiskillRcpspSolution) → dict[Variable, int]

Convert a solution to a mapping between model variables and their values.

Will be used by set_warm_start() to provide a suitable SolutionHint.variable_values. See https://or-tools.github.io/docs/pdoc/ortools/math_opt/python/model_parameters.html#SolutionHint for more information.

Override it in subclasses to have a proper warm start.

init_model(**args)

Initialize internal model used to solve.

Can initialize a ortools, milp, gurobi, … model.

problem: MultiskillRcpspProblem

retrieve_current_solution(get_var_value_for_current_solution: Callable[[Any], float], get_obj_value_for_current_solution: Callable[[], float]) → MultiskillRcpspSolution

Retrieve current solution from internal gurobi solution.

This converts internal gurobi solution into a discrete-optimization Solution. This method can be called after the solve in retrieve_solutions() or during solve within a gurobi/pymilp/cplex callback. The difference will be the get_var_value_for_current_solution and get_obj_value_for_current_solution callables passed.

Parameters:

• get_var_value_for_current_solution – function extracting the value of the given variable for the current solution will be different when inside a callback or after the solve is finished

• get_obj_value_for_current_solution – function extracting the value of the objective for the current solution.

Returns:

the converted solution at d-o format

solve(parameters_milp: ParametersMilp | None = None, time_limit: float | None = 30.0, **args) → ResultStorage

Solve with OR-Tools MathOpt API

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• parameters_milp – parameters passed to the MILP solver

• mathopt_solver_type – underlying solver type to use. Passed as solver_type to mathopt.solve()

• time_limit – the solve process stops after this time limit (in seconds). If None, no time limit is applied.

• mathopt_enable_output – turn on mathopt logging

• mathopt_model_parameters – passed to mathopt.solve() as model_params

• mathopt_additional_solve_parameters – passed to mathopt.solve() as params, except that parameters defined by above time_limit and parameters_milp will be overriden by them.

• store_mathopt_res – whether to store the mathopt.SolveResult generated by mathopt.solve()

• extract_solutions_from_mathopt_res – whether to extract solutions from the mathopt.SolveResult generated by mathopt.solve(). If False, the solutions are rather extracted on the fly inside a callback at each mip solution improvement. By default, this is False except for HiGHS solver type, as its OR-Tools wrapper does not yet integrate callbacks.

• **kwargs – passed to init_model() if model not yet existing

Returns:

discrete_optimization.rcpsp_multiskill.solvers.multimode_transposition module

class discrete_optimization.rcpsp_multiskill.solvers.multimode_transposition.MultimodeTranspositionMultiskillRcpspSolver(problem: MultiskillRcpspProblem, multimode_problem: RcpspProblem | PreemptiveRcpspProblem | None = None, worker_type_to_worker: dict[str, set[str | int]] | None = None, params_objective_function: ParamsObjectiveFunction | None = None, solver_multimode_rcpsp: SolverDO | None = None, **kwargs)

Bases: SolverDO

problem: MultiskillRcpspProblem

solve(**kwargs) → ResultStorage

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

discrete_optimization.rcpsp_multiskill.solvers.multimode_transposition.rebuild_multiskill_solution(multiskill_rcpsp_problem: MultiskillRcpspProblem, multimode_rcpsp_problem: RcpspProblem | PreemptiveRcpspProblem, worker_type_to_worker: dict[str, set[str | int]], solution_rcpsp: RcpspSolution | PreemptiveRcpspSolution)

discrete_optimization.rcpsp_multiskill.solvers.multimode_transposition.rebuild_multiskill_solution_cp_based(multiskill_rcpsp_problem: MultiskillRcpspProblem, multimode_rcpsp_problem: RcpspProblem | PreemptiveRcpspProblem, worker_type_to_worker: dict[str, set[str | int]], solution_rcpsp: RcpspSolution | PreemptiveRcpspSolution)

discrete_optimization.rcpsp_multiskill.solvers.rcpsp_based module

class discrete_optimization.rcpsp_multiskill.solvers.rcpsp_based.RcpspBasedMultiskillRcpspSolver(problem: MultiskillRcpspProblem | VariantMultiskillRcpspProblem, method, params_objective_function: ParamsObjectiveFunction | None = None, **args)

Bases: SolverDO

problem: MultiskillRcpspProblem | VariantMultiskillRcpspProblem

solve(**kwargs)

Generic solving function.

Parameters:

• callbacks – list of callbacks used to hook into the various stage of the solve

• **kwargs – any argument specific to the solver

Solvers deriving from SolverDo should use callbacks methods .on_step_end(), … during solve(). But some solvers are not yet updated and are just ignoring it.

Returns (ResultStorage): a result object containing potentially a pool of solutions to a discrete-optimization problem

Module contents