notebook.community

Edit and run

OR Tools

  • 설치 
      pip3 install ortools
  • 문서
  • 예제 코드 Github
  • 사용 방법
    • 변수 생성
    • 제약조건 정의
    • 목적 함수 정의
    • Solver 실행
    • <변제목솔>
  • 흠 자꾸 죽음...
    • Solver에서 변수 2번째 할당할 때 죽네
  • OR Tools Solver 자체는 어렵지 않은 느낌, 수식을 코드화할 수 있느냐가 관건일 듯
  • Scipy의 Optimization도 있음




In [4]:



    


from ortools.linear_solver import pywraplp
$$x + y$$$$0 \leq x \leq 1$$$$0 \leq y \leq 2$$
  • solver 객체 생성




In [5]:



    


solver = pywraplp.Solver('SolveSimpleSystem',
                       pywraplp.Solver.GLOP_LINEAR_PROGRAMMING)



    











In [3]:



    


type(solver)



    


















    
Out[3]:








ortools.linear_solver.pywraplp.Solver

















In [4]:



    


dir(solver)



    


















    
Out[4]:








['ABNORMAL',
 'AT_LOWER_BOUND',
 'AT_UPPER_BOUND',
 'Add',
 'BASIC',
 'BOP_INTEGER_PROGRAMMING',
 'BoolVar',
 'CBC_MIXED_INTEGER_PROGRAMMING',
 'CLP_LINEAR_PROGRAMMING',
 'Clear',
 'ComputeConstraintActivities',
 'ComputeExactConditionNumber',
 'Constraint',
 'EnableOutput',
 'ExportModelAsLpFormat',
 'ExportModelAsMpsFormat',
 'FEASIBLE',
 'FIXED_VALUE',
 'FREE',
 'GLOP_LINEAR_PROGRAMMING',
 'INFEASIBLE',
 'Infinity',
 'IntVar',
 'InterruptSolve',
 'Iterations',
 'LoadModelFromProto',
 'LookupConstraint',
 'LookupVariable',
 'Maximize',
 'Minimize',
 'NOT_SOLVED',
 'NumConstraints',
 'NumVar',
 'NumVariables',
 'OPTIMAL',
 'Objective',
 'RowConstraint',
 'SetSolverSpecificParametersAsString',
 'SetTimeLimit',
 'Solve',
 'Sum',
 'SupportsProblemType',
 'SuppressOutput',
 'UNBOUNDED',
 'VerifySolution',
 'WallTime',
 '__class__',
 '__del__',
 '__delattr__',
 '__dict__',
 '__dir__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattr__',
 '__getattribute__',
 '__gt__',
 '__hash__',
 '__init__',
 '__init_subclass__',
 '__le__',
 '__lt__',
 '__module__',
 '__ne__',
 '__new__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__setattr__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 '__swig_destroy__',
 '__swig_getmethods__',
 '__swig_setmethods__',
 '__weakref__',
 'infinity',
 'iterations',
 'nodes',
 'set_time_limit',
 'this',
 'wall_time']

solver.NumVar(Lower Bound, Upper Bound, 변수 이름)





In [5]:



    


x = solver.NumVar(0, 1, 'x')
y = solver.NumVar(0, 2, 'y')
  • solver.NumVar(lb:'double', ub:'double', name:'std::string const &')




In [6]:



    


type(y)



    


















    
Out[6]:








ortools.linear_solver.pywraplp.Variable

















In [7]:



    


x



    


















    
Out[7]:








x

















In [8]:



    


dir(x)



    


















    
Out[8]:








['Integer',
 'Lb',
 'ReducedCost',
 'SetLb',
 'SetUb',
 'SolutionValue',
 'Ub',
 '__add__',
 '__class__',
 '__del__',
 '__delattr__',
 '__dict__',
 '__dir__',
 '__div__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattr__',
 '__getattribute__',
 '__gt__',
 '__hash__',
 '__init__',
 '__init_subclass__',
 '__le__',
 '__lt__',
 '__module__',
 '__mul__',
 '__ne__',
 '__neg__',
 '__new__',
 '__radd__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__rmul__',
 '__rsub__',
 '__setattr__',
 '__sizeof__',
 '__str__',
 '__sub__',
 '__subclasshook__',
 '__swig_destroy__',
 '__swig_getmethods__',
 '__swig_setmethods__',
 '__truediv__',
 '__weakref__',
 'basis_status',
 'index',
 'integer',
 'lb',
 'name',
 'reduced_cost',
 'solution_value',
 'this',
 'ub']
  • 목적 함수 생성




In [9]:



    


objective = solver.Objective()



    











In [10]:



    


dir(objective)



    


















    
Out[10]:








['AddOffset',
 'BestBound',
 'Clear',
 'GetCoefficient',
 'Offset',
 'SetCoefficient',
 'SetMaximization',
 'SetMinimization',
 'SetOffset',
 'SetOptimizationDirection',
 'Value',
 '__class__',
 '__del__',
 '__delattr__',
 '__dict__',
 '__dir__',
 '__doc__',
 '__eq__',
 '__format__',
 '__ge__',
 '__getattr__',
 '__getattribute__',
 '__gt__',
 '__hash__',
 '__init__',
 '__init_subclass__',
 '__le__',
 '__lt__',
 '__module__',
 '__ne__',
 '__new__',
 '__reduce__',
 '__reduce_ex__',
 '__repr__',
 '__setattr__',
 '__sizeof__',
 '__str__',
 '__subclasshook__',
 '__swig_destroy__',
 '__swig_getmethods__',
 '__swig_setmethods__',
 '__weakref__',
 'maximization',
 'minimization',
 'offset',
 'this']
  • SetCoefficient : 계수 설정




In [11]:



    


objective.SetCoefficient(x, 1)
objective.SetCoefficient(y, 1)

SetMaximization() : 최대화





In [12]:



    


objective.SetMaximization()
  • 해풀기




In [13]:



    


solver.Solve()
print('Solution:')
print('x = ', x.solution_value())
print('y = ', y.solution_value())



    


















    






Solution:
x =  1.0
y =  2.0

















In [19]:



    


type(solver)



    


















    
Out[19]:








ortools.linear_solver.pywraplp.Solver

















In [20]:



    


x



    


















    
Out[20]:








x

















In [21]:



    


x.solution_value()



    


















    
Out[21]:








1.0

Linear Optimization

  • Maximize $$3x+4y$$

  • 제약조건 $$x+2y \leq 14$$ $$3x-y \geq 0$$ $$x-y \leq 2$$

  • 변제목솔




In [6]:



    


x = solver.NumVar(-solver.infinity(), solver.infinity(), 'x')



    











In [7]:



    


y = solver.NumVar(-solver.infinity(), solver.infinity(), 'y')



    











In [9]:



    


# Constraint 1: x + 2y <= 14
contraint1 = solver.Constraint(-solver.infinity(), 14)
contraint1.SetCoefficient(x, 1)
contraint1.SetCoefficient(y, 2)

# Constraint 2: 3x - y >= 0
contraint2 = solver.Constraint(0, solver.infinity())
contraint2.SetCoefficient(x, 3)
contraint2.SetCoefficient(y, -1)

#  Constraint 3: x - y <= 2
contraint3 = solver.Constraint(-solver.infinity(), 2)
contraint3.SetCoefficient(x, 1)
contraint3.SetCoefficient(y, -1)



    











In [10]:



    


objective = solver.Objective()



    











In [13]:



    


objective.SetCoefficient(x, 3)
objective.SetCoefficient(y, 4)
objective.SetMaximization()



    











In [14]:



    


solver.Solve()



    


















    
Out[14]:








0

















In [15]:



    


opt_solution = 3 * x.solution_value() + 4 * y.solution_value()



    











In [27]:



    


print('Number of variables =', solver.NumVariables())
print('Number of constraints =', solver.NumConstraints())
# The value of each variable in the solution.
print('Solution:')
print('x = ', round(x.solution_value())) # 부동소수점 처리하기 위해 round
print('y = ', round(y.solution_value())) 
# The objective value of the solution.
print('Optimal objective value =', round(opt_solution))



    


















    






Number of variables = 2
Number of constraints = 4
Solution:
x =  6
y =  4
Optimal objective value = 34
  • 부동소수점.. 5.9999, 3.999 이런식으로 나와서 round 처리




In [29]:



    


from ortools.sat.python import cp_model


class SchoolSchedulingProblem(object):
    def __init__(self, subjects, teachers, curriculum, specialties,
                 working_days, periods, levels, sections, teacher_work_hours):
        self.subjects = subjects
        self.teachers = teachers
        self.curriculum = curriculum
        self.specialties = specialties
        self.working_days = working_days
        self.periods = periods
        self.levels = levels
        self.sections = sections
        self.teacher_work_hours = teacher_work_hours


class SchoolSchedulingSatSolver(object):
    def __init__(self, problem):
        # Problem
        self.problem = problem

        # Utilities
        self.timeslots = [
            '{0:10} {1:6}'.format(x, y) for x in problem.working_days
            for y in problem.periods
        ]
        self.num_days = len(problem.working_days)
        self.num_periods = len(problem.periods)
        self.num_slots = len(self.timeslots)
        self.num_teachers = len(problem.teachers)
        self.num_subjects = len(problem.subjects)
        self.num_levels = len(problem.levels)
        self.num_sections = len(problem.sections)
        self.courses = [
            x * self.num_levels + y for x in problem.levels
            for y in problem.sections
        ]
        self.num_courses = self.num_levels * self.num_sections

        all_courses = range(self.num_courses)
        all_teachers = range(self.num_teachers)
        all_slots = range(self.num_slots)
        all_sections = range(self.num_sections)
        all_subjects = range(self.num_subjects)
        all_levels = range(self.num_levels)

        self.model = cp_model.CpModel()

        self.assignment = {}
        for c in all_courses:
            for s in all_subjects:
                for t in all_teachers:
                    for slot in all_slots:
                        if t in self.problem.specialties[s]:
                            name = 'C:{%i} S:{%i} T:{%i} Slot:{%i}' % (c, s, t,
                                                                       slot)
                            self.assignment[c, s, t,
                                            slot] = self.model.NewBoolVar(name)
                        else:
                            name = 'NO DISP C:{%i} S:{%i} T:{%i} Slot:{%i}' % (
                                c, s, t, slot)
                            self.assignment[c, s, t,
                                            slot] = self.model.NewIntVar(
                                                0, 0, name)

        # Constraints

        # Each course must have the quantity of classes specified in the curriculum
        for level in all_levels:
            for section in all_sections:
                course = level * self.num_sections + section
                for subject in all_subjects:
                    required_slots = self.problem.curriculum[
                        self.problem.levels[level], self.problem.subjects[
                            subject]]
                    self.model.Add(
                        sum(self.assignment[course, subject, teacher, slot]
                            for slot in all_slots
                            for teacher in all_teachers) == required_slots)

        # Teacher can do at most one class at a time
        for teacher in all_teachers:
            for slot in all_slots:
                self.model.Add(
                    sum([
                        self.assignment[c, s, teacher, slot]
                        for c in all_courses for s in all_subjects
                    ]) <= 1)

        # Maximum work hours for each teacher
        for teacher in all_teachers:
            self.model.Add(
                sum([
                    self.assignment[c, s, teacher, slot] for c in all_courses
                    for s in all_subjects for slot in all_slots
                ]) <= self.problem.teacher_work_hours[teacher])

        # Teacher makes all the classes of a subject's course
        teacher_courses = {}
        for level in all_levels:
            for section in all_sections:
                course = level * self.num_sections + section
                for subject in all_subjects:
                    for t in all_teachers:
                        name = 'C:{%i} S:{%i} T:{%i}' % (course, subject,
                                                         teacher)
                        teacher_courses[course, subject,
                                        t] = self.model.NewBoolVar(name)
                        temp_array = [
                            self.assignment[course, subject, t, slot]
                            for slot in all_slots
                        ]
                        self.model.AddMaxEquality(
                            teacher_courses[course, subject, t], temp_array)
                    self.model.Add(
                        sum(teacher_courses[course, subject, t]
                            for t in all_teachers) == 1)

    def solve(self):
        print('Solving')
        solver = cp_model.CpSolver()
        solution_printer = SchoolSchedulingSatSolutionPrinter()
        status = solver.Solve(self.model)
        print()
        print('status', status)
        print('Branches', solver.NumBranches())
        print('Conflicts', solver.NumConflicts())
        print('WallTime', solver.WallTime())


class SchoolSchedulingSatSolutionPrinter(cp_model.CpSolverSolutionCallback):
    def __init__(self):
        cp_model.CpSolverSolutionCallback.__init__(self)
        self.__solution_count = 0

    def OnSolutionCallback(self):
        print('Found Solution!')


# DATA
subjects = ['English', 'Math', 'History']
levels = ['1-', '2-', '3-']
sections = ['A']
teachers = ['Mario', 'Elvis', 'Donald', 'Ian']
teachers_work_hours = [18, 12, 12, 18]
working_days = ['Monday', 'Tuesday', 'Wednesday', 'Thursday', 'Friday']
periods = ['08:00-09:30', '09:45-11:15', '11:30-13:00']
curriculum = {
    ('1-', 'English'): 3,
    ('1-', 'Math'): 3,
    ('1-', 'History'): 2,
    ('2-', 'English'): 4,
    ('2-', 'Math'): 2,
    ('2-', 'History'): 2,
    ('3-', 'English'): 2,
    ('3-', 'Math'): 4,
    ('3-', 'History'): 2
}

# Subject -> List of teachers who can teach it
specialties_idx_inverse = [
    [1, 3],  # English   -> Elvis & Ian
    [0, 3],  # Math      -> Mario & Ian
    [2, 3]  # History   -> Donald & Ian
]

problem = SchoolSchedulingProblem(
    subjects, teachers, curriculum, specialties_idx_inverse, working_days,
    periods, levels, sections, teachers_work_hours)
solver = SchoolSchedulingSatSolver(problem)
solver.solve()



    


















    






Solving

status 2
Branches 105
Conflicts 0
WallTime 0.004366168

















In [37]:



    


from ortools.sat.python import cp_model


def schedule():

    # Input data.
    positions = [
        1, 2, 8, 10, 5, 3, 4, 3, 6, 6, 4, 5, 4, 3, 4, 4, 3, 4, 2, 1, 0, 0, 0,
        0, 1, 2, 9, 9, 4, 3, 4, 3, 5, 4, 5, 2, 5, 6, 6, 7, 4, 2, 1, 0, 0, 0, 0,
        0, 0, 2, 7, 6, 5, 2, 4, 4, 6, 6, 4, 5, 5, 5, 7, 5, 4, 4, 2, 3, 1, 0, 0,
        0, 1, 2, 9, 7, 2, 2, 4, 2, 4, 5, 3, 2, 6, 7, 5, 6, 4, 4, 2, 1, 0, 0, 0,
        0, 2, 2, 8, 8, 6, 3, 3, 3, 10, 9, 6, 3, 3, 4, 5, 4, 5, 4, 2, 1, 0, 0,
        0, 0, 1, 2, 9, 5, 5, 4, 5, 2, 5, 7, 5, 3, 4, 8, 4, 4, 2, 3, 1, 0, 0, 0,
        0, 0, 1, 2, 10, 5, 5, 4, 5, 2, 4, 6, 7, 4, 4, 5, 4, 4, 3, 3, 2, 1, 0,
        0, 0, 0
    ]

    possible_shifts = [[
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 40
    ], [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 40
    ], [
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        2, 40
    ], [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        3, 40
    ], [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        4, 0
    ], [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        5, 16
    ], [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0,
        6, 16
    ], [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        7, 16
    ], [
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        1, 1, 1, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1,
        8, 40
    ]]

    # Useful numbers.
    num_slots = len(positions)
    all_slots = range(num_slots)

    num_shifts = len(possible_shifts)
    all_shifts = range(num_shifts)

    min_number_of_workers = [5 * x for x in positions]
    num_workers = 300

    # Model the problem.
    model = cp_model.CpModel()

    workers_per_shift = [
        model.NewIntVar(0, num_workers, 'shift[%i]' % i) for i in all_shifts
    ]

    # Satisfy min requirements.
    for slot in all_slots:
        model.Add(
            sum(workers_per_shift[shift] * possible_shifts[shift][slot]
                for shift in all_shifts) >= min_number_of_workers[slot])

    # Create the objective variable.
    objective = model.NewIntVar(0, num_workers, 'objective')

    # Link the objective.
    model.Add(sum(workers_per_shift) == objective)

    # Minimize.
    model.Minimize(objective)

    solver = cp_model.CpSolver()
    status = solver.Solve(model)

    if status == cp_model.OPTIMAL:
        print('Objective value = %i' % solver.ObjectiveValue())

    print('Statistics')
    print('  - conflicts : %i' % solver.NumConflicts())
    print('  - branches  : %i' % solver.NumBranches())
    print('  - wall time : %f ms' % solver.WallTime())



    











In [38]:



    


schedule()



    


















    






Objective value = 215
Statistics
  - conflicts : 0
  - branches  : 8
  - wall time : 0.000328 ms

















In [ ]:

Content source: zzsza/TIL

Similar notebooks:

notebook.community | gallery | about