discrete_optimization.alb.salbp package

Subpackages

• discrete_optimization.alb.salbp.solvers package
  • Submodules
  • discrete_optimization.alb.salbp.solvers.asp module
    • AspSalbpSolver
      • AspSalbpSolver.build_heuristic_input()
      • AspSalbpSolver.build_string_data_input()
      • AspSalbpSolver.init_model()
      • AspSalbpSolver.problem
      • AspSalbpSolver.retrieve_solution()
      • AspSalbpSolver.set_warm_start()
      • AspSalbpSolver.upper_bound
  • discrete_optimization.alb.salbp.solvers.cpsat module
    • CpSatSalbp12Solver
      • CpSatSalbp12Solver.get_task_start_or_end_variable()
      • CpSatSalbp12Solver.get_task_unary_resource_is_present_variable()
      • CpSatSalbp12Solver.hyperparameters
      • CpSatSalbp12Solver.init_model()
      • CpSatSalbp12Solver.init_model_binary()
      • CpSatSalbp12Solver.init_model_scheduling()
      • CpSatSalbp12Solver.problem
      • CpSatSalbp12Solver.retrieve_solution()
      • CpSatSalbp12Solver.set_warm_start()
    • CpSatSalbpSolver
      • CpSatSalbpSolver.get_task_start_or_end_variable()
      • CpSatSalbpSolver.get_task_unary_resource_is_present_variable()
      • CpSatSalbpSolver.hyperparameters
      • CpSatSalbpSolver.init_model()
      • CpSatSalbpSolver.init_model_binary()
      • CpSatSalbpSolver.init_model_scheduling()
      • CpSatSalbpSolver.modeling
      • CpSatSalbpSolver.problem
      • CpSatSalbpSolver.retrieve_solution()
      • CpSatSalbpSolver.set_warm_start()
    • ModelingCpsatSalbp
      • ModelingCpsatSalbp.BINARY
      • ModelingCpsatSalbp.SCHEDULING
  • discrete_optimization.alb.salbp.solvers.dp module
    • DpSalbpSolver
      • DpSalbpSolver.init_model()
      • DpSalbpSolver.problem
      • DpSalbpSolver.retrieve_solution()
      • DpSalbpSolver.set_warm_start()
  • discrete_optimization.alb.salbp.solvers.greedy module
    • GreedySalbpSolver
      • GreedySalbpSolver.problem
      • GreedySalbpSolver.solve()
  • discrete_optimization.alb.salbp.solvers.optal module
    • OptalSalbp12Solver
      • OptalSalbp12Solver.add_lexico_constraint()
      • OptalSalbp12Solver.get_lexico_objective_value()
      • OptalSalbp12Solver.get_lexico_objectives_available()
      • OptalSalbp12Solver.get_task_interval_variable()
      • OptalSalbp12Solver.implements_lexico_api()
      • OptalSalbp12Solver.init_model()
      • OptalSalbp12Solver.init_model_scheduling()
      • OptalSalbp12Solver.problem
      • OptalSalbp12Solver.retrieve_solution()
      • OptalSalbp12Solver.set_lexico_objective()
      • OptalSalbp12Solver.set_warm_start()
    • OptalSalbpSolver
      • OptalSalbpSolver.get_task_interval_variable()
      • OptalSalbpSolver.hyperparameters
      • OptalSalbpSolver.init_model()
      • OptalSalbpSolver.init_model_scheduling()
      • OptalSalbpSolver.problem
      • OptalSalbpSolver.retrieve_solution()
      • OptalSalbpSolver.set_warm_start()
  • Module contents

Submodules

discrete_optimization.alb.salbp.parser module

discrete_optimization.alb.salbp.parser.get_data_available(data_folder: str | None = None, data_home: str | None = None) → list[str]

Get datasets available for tsp.

Params:

data_folder: folder where datasets for weighted tardiness problem should be found.

If None, we look in “wt” subdirectory of data_home.

data_home: root directory for all datasets. Is None, set by

default to “~/discrete_optimization_data “

discrete_optimization.alb.salbp.parser.parse_alb_file(file_path: str) → SalbpProblem

Parses a .alb file using string splitting and tokenization. No Regular Expressions used.

discrete_optimization.alb.salbp.parser.remove_artifacts(text: str) → str

discrete_optimization.alb.salbp.problem module

class discrete_optimization.alb.salbp.problem.SalbpProblem(tasks_data: List[TaskData], cycle_time: int, precedences: List[Tuple[int, int]], number_of_stations: int = None)

Bases: BaseALBProblem[int, int]

Simple Assembly Line Balancing Problem.

Extends BaseALBProblem with cycle time constraints. Uses PrecedenceProblem mixin for precedence graph handling.

cycle_time

Maximum allowed time per station

number_of_tasks

Total number of tasks (for compatibility)

tasks_to_index

Mapping from task_id to index

evaluate(variable: SalbpSolution) → Dict[str, float]

Evaluate the solution.

Objective: Minimize the number of stations. Constraints: - Cycle time: Each station’s workload must not exceed cycle_time - Precedence: Handled by base class using absolute times

Returns:

• nb_stations: Number of used stations (objective)

• penalty_overtime: Sum of time exceeding cycle_time per station

• penalty_undertime: Sum of idle time per station

• penalty_precedence: Number of precedence violations (from base)

Return type:

Dictionary with

get_attribute_register() → EncodingRegister

Register for standard encoding (optional, but good for GA/CP solvers). We define the solution as a list of integers (station assignments).

get_graph_precedence() → Graph

Get precedence graph.

Uses the PrecedenceProblem mixin’s get_precedence_graph() method.

get_objective_register() → ObjectiveRegister

Defines the default objective to minimize.

get_solution_type() → type[Solution]

Returns the class implementation of a Solution.

Returns (class): class object of the given Problem.

get_solution_type_member() → SalbpSolution

satisfy(variable: SalbpSolution) → bool

Strict check for validity.

class discrete_optimization.alb.salbp.problem.SalbpProblem_1_2(tasks_data: List[TaskData], precedences: List[Tuple[int, int]], number_of_stations: int = None)

Bases: SalbpProblem

Generalisation of SALBP-(1,2) problem.

In this variant, both cycle time and number of stations can be optimized.

evaluate(variable: SalbpSolution) → Dict[str, float]

Evaluate the solution. Objective: Minimize the number of stations and cycle time

static from_salbp1(problem: SalbpProblem) → SalbpProblem_1_2

Create SALBP-1,2 problem from SALBP-1 problem.

get_objective_register() → ObjectiveRegister

Defines the default objective to minimize.

satisfy(variable: SalbpSolution) → bool

Strict check for validity.

class discrete_optimization.alb.salbp.problem.SalbpSolution(problem: SalbpProblem, allocation_to_station: list[int])

Bases: BaseALBSolution[int, int]

Solution for SALBP problem.

SALBP only assigns tasks to stations without explicit scheduling. Scheduling is computed on-demand using greedy sequential scheduling.

change_problem(new_problem: Problem) → Solution

If relevant to the optimisation problem, change the underlying problem instance for the solution.

This method can be used to evaluate a solution for different instance of problems. It should be implemented in child classes when caching subresults depending on the problem.

Parameters:

new_problem (Problem) – another problem instance from which the solution can be evaluated

Returns: None

copy() → SalbpSolution

Deep copy of the solution.

The copy() function should return a new object containing the same input as the current object, that respects the following expected behaviour: -y = x.copy() -if do some inplace change of y, the changes are not done in x.

Returns: a new object from which you can manipulate attributes without changing the original object.

get_end_time(task: int) → int

get_start_time(task: int) → int

get_start_time_in_cycle(task: int) → int

Get start time within cycle using greedy scheduling.

Since SALBP doesn’t have explicit scheduling, we compute it on-demand and cache the result.

get_station_index(task: int) → int

Get the index of the station where task is assigned.

is_allocated(task: int, unary_resource: UnaryResource) → bool

Return the usage of the unary resource for the given task.

Parameters:

• task

• unary_resource

Returns:

problem: SalbpProblem

discrete_optimization.alb.salbp.problem.calculate_salbp_lower_bounds(problem: SalbpProblem) → int

Calculates lower bounds for the SALBP-1 problem. Inspired by: https://github.com/domain-independent-dp/didp-rs

Module contents