discrete_optimization.singlemachine.solvers package

Submodules

discrete_optimization.singlemachine.solvers.cpmpy_solver module

class discrete_optimization.singlemachine.solvers.cpmpy_solver.CpmpySingleMachineSolver(problem: WeightedTardinessProblem, **kwargs: Any)

Bases: CpmpySolver

CPMPy-based solver for the Single Machine Weighted Tardiness Problem.

This solver can use two different formulations: - CP (Constraint Programming): A model based on temporal variables and disjunctive constraints. It’s generally more efficient for scheduling problems. - LP (Mixed-Integer Linear Programming): A model based on relative ordering variables and “big-M” constraints.

get_hard_meta_constraints() → List[MetaCpmpyConstraint]

Returns the list of hard meta-constraints. These constraints define the core logic of the problem and should not be relaxed.

get_soft_meta_constraints() → List[MetaCpmpyConstraint]

Returns the list of soft meta-constraints for explanation purposes. These are constraints that can potentially be relaxed if the model is UNSAT.

init_model(model_type: SingleMachineModel = SingleMachineModel.CP, add_impossible_constraints: bool = False, **kwargs: Any) → None

Builds the CPMpy model based on the chosen formalism (CP or LP). It defines variables, constraints, meta-constraints, and the objective function.

retrieve_current_solution() → Solution

Constructs a WTSolution from the solved CPMpy model.

class discrete_optimization.singlemachine.solvers.cpmpy_solver.SingleMachineModel(*values)

Bases: Enum

Enum to select the modeling formulation.

CP = 0

LP = 1

discrete_optimization.singlemachine.solvers.cpsat module

class discrete_optimization.singlemachine.solvers.cpsat.CpsatWTSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SchedulingCpSatSolver[int], WarmstartMixin

get_task_start_or_end_variable(task: int, start_or_end: StartOrEnd) → LinearExpr | IntVar | int | int8 | uint8 | int32 | uint32 | int64 | uint64

Retrieve the variable storing the start or end time of given task.

Parameters:

• task

• start_or_end

Returns:

init_model(**args: Any) → None

Init cp model and reset stored variables if any.

problem: WeightedTardinessProblem

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_warm_start(solution: WTSolution) → None

Make the solver warm start from the given solution.

variables: dict

discrete_optimization.singlemachine.solvers.dp module

class discrete_optimization.singlemachine.solvers.dp.DpWTSolver(problem: WeightedTardinessProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: DpSolver, WarmstartMixin

hyperparameters: list[Hyperparameter] = [CategoricalHyperparameter(name='add_dominated_transition', default=False, depends_on=None, name_in_kwargs='add_dominated_transition')]

Hyperparameters available for this solver.

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

• __init__()

• init_model() (when available)

• solve()

init_model(**kwargs: Any) → None

Initialize internal model used to solve.

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

problem: WeightedTardinessProblem

retrieve_solution(sol: Solution) → Solution

set_warm_start(solution: WTSolution) → None

Make the solver warm start from the given solution.

discrete_optimization.singlemachine.solvers.greedy module

class discrete_optimization.singlemachine.solvers.greedy.GreedySingleMachineSolver(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

Greedy solver inserting jobs only using their initial index.

problem: WeightedTardinessProblem

solve(callbacks: list[Callback] | None = None, **kwargs: Any) → 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

class discrete_optimization.singlemachine.solvers.greedy.GreedySingleMachineWSPT(problem: Problem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: SolverDO

Greedy solver for the Single Machine Weighted Tardiness problem based on the Weighted Shortest Processing Time (WSPT) heuristic.

It sorts jobs in increasing order of (processing_time / weight).

problem: WeightedTardinessProblem

solve(callbacks: list[Callback] | None = None, **kwargs: Any) → 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.singlemachine.solvers.lp module

class discrete_optimization.singlemachine.solvers.lp.GurobiSingleMachineSolver(problem: WeightedTardinessProblem, **kwargs: Any)

Bases: _BaseLpSingleMachineSolver, GurobiMilpSolver

convert_to_variable_values(solution: Solution) → dict[gurobipy.Var, float]

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

Will be used by set_warm_start().

Override it in subclasses to have a proper warm start. You can also override set_warm_start() if default behaviour is not sufficient.

class discrete_optimization.singlemachine.solvers.lp.MathOptSingleMachineSolver(problem: WeightedTardinessProblem, **kwargs: Any)

Bases: _BaseLpSingleMachineSolver, OrtoolsMathOptMilpSolver

convert_to_variable_values(solution: Solution) → dict[Variable, float]

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.

discrete_optimization.singlemachine.solvers.optal module

class discrete_optimization.singlemachine.solvers.optal.OptalSingleMachineSolver(problem: WeightedTardinessProblem, params_objective_function: ParamsObjectiveFunction | None = None, **kwargs: Any)

Bases: OptalSolver

build_command(parameters_cp: ParametersCp | None = None, time_limit: int = 10, **args: Any)

Build the command line call for optal cp. You can pass parameters from the Parameters class of optal cp for example : searchType=fds, worker0-1.noOverlapPropagationLevel=4 if you want worker 0 and 1 to use this parameters etc. TODO : list such parameters in hyperparameter of this wrapped solver.

init_model(**args: Any) → None

Instantiate a CP model instance

Afterwards, self.instance should not be None anymore.

problem: WeightedTardinessProblem

retrieve_current_solution(dict_results: dict) → Solution

discrete_optimization.singlemachine.solvers.optal.to_dict(problem: WeightedTardinessProblem)

Exports the problem description to a JSON file.

Module contents