Advanced constraint programming modeling

advancedModelingWeek3.py

from ortools.sat.python import cp_model

''' course: https://www.coursera.org/learn/advanced-modeling#about '''



def basicScheduling():
    model = cp_model.CpModel()

    taskList = ["FUNDS", "SOLDIERS", "DEFENSE", "WEAPONRY", "ELITEARMY", "RAW_MATERIALS", "CRAFTSMEN", "CASTING", "BRICKS", "WALL"]
    numOfTasks = len(taskList)
    durationList = [10, 10, 25, 25, 10, 20, 15, 20, 10, 20]
    precedenceList = [[0, 1], [0, 5], [0, 6], [0, 8], [1, 3], [1, 2], [3, 4], [2, 4], [5, 7], [6, 7], [6, 9], [8, 9], [7, 3], [9, 2]]
    totalDuration = sum(durationList)

    startTimeVarList = []
    endTimeVarList = []
    for task in range(numOfTasks):
        startTimeVarList.append(model.NewIntVar(0, totalDuration, "startTimeForTask"+str(task)))
        endTimeVarList.append(model.NewIntVar(0, totalDuration, "totalTimeForTask" + str(task)))
        model.Add(endTimeVarList[task] == startTimeVarList[task] + durationList[task])

    for precedence in precedenceList:
        model.Add(startTimeVarList[precedence[0]] + durationList[precedence[0]] <= startTimeVarList[precedence[1]])

    makeSpanVar = model.NewIntVar(0, totalDuration, "makeSpan")
    model.AddMaxEquality(makeSpanVar, endTimeVarList)
    model.Minimize(makeSpanVar)

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

    if status == cp_model.INFEASIBLE:
        print("Infeasible model")

    if status == cp_model.OPTIMAL:
        print('Minimum makeSpan: %i' % solver.ObjectiveValue(), "\n")

        for task in range(numOfTasks):
            print("Start time for "+str(taskList[task]) +" is "+str(solver.Value(startTimeVarList[task])))
    print("----------------------------")



#----------------------------------------------------------------------------------------------------------------------#





def schedulingWithUnaryResource():
    model = cp_model.CpModel()

    taskList = ["FUNDS", "SOLDIERS", "DEFENSE", "WEAPONRY", "ELITEARMY", "RAW_MATERIALS", "CRAFTSMEN", "CASTING", "BRICKS", "WALL"]
    numOfTasks = len(taskList)
    durationList = [10, 10, 25, 25, 10, 20, 15, 20, 10, 20]
    precedenceList = [[0, 1], [0, 5], [0, 6], [0, 8], [1, 3], [1, 2], [3, 4], [2, 4], [5, 7], [6, 7], [6, 9], [8, 9], [7, 3], [9, 2]]
    unaryResourceForTasks = [5, 7, 8, 9]
    totalDuration = sum(durationList)

    startTimeVarList = []
    endTimeVarList = []
    intervalVarList = []
    for task in range(numOfTasks):
        startTimeVarList.append(model.NewIntVar(0, totalDuration, "startTimeForTask"+str(task)))
        endTimeVarList.append(model.NewIntVar(0, totalDuration, "totalTimeForTask" + str(task)))
        intervalVarList.append(model.NewIntervalVar(startTimeVarList[task], durationList[task], endTimeVarList[task], "intervalVarForTask"+str(task)))

    for precedence in precedenceList:
        model.Add(startTimeVarList[precedence[0]] + durationList[precedence[0]] <= startTimeVarList[precedence[1]])


    varList = []
    for task in unaryResourceForTasks:
        varList.append(intervalVarList[task])
    model.AddNoOverlap(varList)


    makeSpanVar = model.NewIntVar(0, totalDuration, "makeSpan")
    model.AddMaxEquality(makeSpanVar, endTimeVarList)
    model.Minimize(makeSpanVar)

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

    if status == cp_model.INFEASIBLE:
        print("Infeasible model")

    if status == cp_model.OPTIMAL:
        print('Minimum makeSpan: %i' % solver.ObjectiveValue(), "\n")

        for task in range(numOfTasks):
            print("Start time for "+str(taskList[task]) +" is "+str(solver.Value(startTimeVarList[task])))
    print("----------------------------")





#----------------------------------------------------------------------------------------------------------------------#




def schedulingWithMultipleUnaryResources():
    model = cp_model.CpModel()

    taskList = ["FUNDS", "SOLDIERS", "DEFENSE", "WEAPONRY", "ELITEARMY", "RAW_MATERIALS", "CRAFTSMEN", "CASTING", "BRICKS", "WALL"]
    numOfTasks = len(taskList)
    durationList = [10, 10, 25, 25, 10, 20, 15, 20, 10, 20]
    precedenceList = [[0, 1], [0, 5], [0, 6], [0, 8], [1, 3], [1, 2], [3, 4], [2, 4], [5, 7], [6, 7], [6, 9], [8, 9], [7, 3], [9, 2]]
    unaryResourceForTasks = [[5, 7, 8, 9], [1, 5, 6, 8], [3, 1, 4, 9]]
    totalDuration = sum(durationList)

    startTimeVarList = []
    endTimeVarList = []
    intervalVarList = []
    for task in range(numOfTasks):
        startTimeVarList.append(model.NewIntVar(0, totalDuration, "startTimeForTask"+str(task)))
        endTimeVarList.append(model.NewIntVar(0, totalDuration, "totalTimeForTask" + str(task)))
        intervalVarList.append(model.NewIntervalVar(startTimeVarList[task], durationList[task], endTimeVarList[task], "intervalVarForTask"+str(task)))

    for precedence in precedenceList:
        model.Add(startTimeVarList[precedence[0]] + durationList[precedence[0]] <= startTimeVarList[precedence[1]])


    for taskSet in unaryResourceForTasks:
        varList = []
        for task in taskSet:
            varList.append(intervalVarList[task])
        model.AddNoOverlap(varList)


    makeSpanVar = model.NewIntVar(0, totalDuration, "makeSpan")
    model.AddMaxEquality(makeSpanVar, endTimeVarList)
    model.Minimize(makeSpanVar)

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

    if status == cp_model.INFEASIBLE:
        print("Infeasible model")

    if status == cp_model.OPTIMAL:
        print('Minimum makeSpan: %i' % solver.ObjectiveValue(), "\n")

        for task in range(numOfTasks):
            print("Start time for "+str(taskList[task]) +" is "+str(solver.Value(startTimeVarList[task])))
    print("----------------------------")




#----------------------------------------------------------------------------------------------------------------------#




def resourceConstrainedProjectScheduling():
    model = cp_model.CpModel()

    taskList = ["FUNDS", "SOLDIERS", "DEFENSE", "WEAPONRY", "ELITEARMY", "RAW_MATERIALS", "CRAFTSMEN", "CASTING", "BRICKS", "WALL"]
    numOfTasks = len(taskList)
    durationList = [10, 10, 25, 25, 10, 20, 15, 20, 10, 20]
    totalDuration = sum(durationList)
    precedenceList = [[0, 1], [0, 5], [0, 6], [0, 8], [1, 3], [1, 2], [3, 4], [2, 4], [5, 7], [6, 7], [6, 9], [8, 9], [7, 3], [9, 2]]
    resourceRequiredForTask = [[0, 0, 0, 0, 0, 3, 0, 2, 1, 2], [0, 3, 0, 0, 0, 2, 2, 0, 1, 0], [0, 0, 2, 2, 1, 0, 0, 0, 0, 2]]
    resourceLimitList = [4, 4, 4]

    startTimeVarList = []
    endTimeVarList = []
    intervalVarList = []
    for task in range(numOfTasks):
        startTimeVarList.append(model.NewIntVar(0, totalDuration, "startTimeForTask"+str(task)))
        endTimeVarList.append(model.NewIntVar(0, totalDuration, "totalTimeForTask" + str(task)))
        intervalVarList.append(model.NewIntervalVar(startTimeVarList[task], durationList[task], endTimeVarList[task], "intervalVarForTask"+str(task)))

    for precedence in precedenceList:
        model.Add(startTimeVarList[precedence[0]] + durationList[precedence[0]] <= startTimeVarList[precedence[1]])

    for resource, requirementList in enumerate(resourceRequiredForTask):
        model.AddCumulative(intervalVarList, requirementList, resourceLimitList[resource])

    makeSpanVar = model.NewIntVar(0, totalDuration, "makeSpan")
    model.AddMaxEquality(makeSpanVar, endTimeVarList)
    model.Minimize(makeSpanVar)

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

    if status == cp_model.INFEASIBLE:
        print("Infeasible model")

    if status == cp_model.OPTIMAL:
        print('Minimum makeSpan: %i' % solver.ObjectiveValue(), "\n")

        for task in range(numOfTasks):
            print("Start time for "+str(taskList[task]) +" is "+str(solver.Value(startTimeVarList[task])))
    print("----------------------------")




#----------------------------------------------------------------------------------------------------------------------#




def sequenceDependencyProblem():
    model = cp_model.CpModel()

    lengthOfChannel = 32
    numOfShipsWithDummyShip = 8
    numOfShips = 7
    speedList = [5, 6, 4, 5, 4, 7, 3, 0]
    maxSpeed = max(speedList)
    desiredTimeList = [271, 43, 385, 33, 115, 281, 175, 600]
    shipKindList = [1, 2, 1, 2, 2, 1, 2, 3]
    leeway = 2
    maxTime = 600

    startTimeVarList = []
    endTimeVarList = []
    for ship in range(numOfShipsWithDummyShip):
        startTimeVarList.append(model.NewIntVar(0, maxTime, "startTimeForShip"+str(ship)))
        endTimeVarList.append(model.NewIntVar(0, maxTime, "endTimeForShip" + str(ship)))

    nextShipVarList = []
    for ship in range(numOfShips):
        nextShipVarList.append(model.NewIntVar(0, numOfShipsWithDummyShip-1, "nextShipForShip"+str(ship)))

    model.Add(startTimeVarList[numOfShipsWithDummyShip-1] == maxTime)
    model.Add(endTimeVarList[numOfShipsWithDummyShip-1] == maxTime)

    for ship in range(numOfShips):
        model.Add(endTimeVarList[ship] == startTimeVarList[ship] + lengthOfChannel * speedList[ship])
        model.Add(startTimeVarList[ship] >= desiredTimeList[ship])

    model.AddAllDifferent(nextShipVarList)

    nextShipKindVarList = []
    nextShipStartTimeVarList = []
    nextShipEndTimeVarList = []
    nextShipSpeedVarList = []
    for ship in range(numOfShips):

        nextShipKindVarList.append(model.NewIntVar(1, 3, "nextShipKindForShip"+str(ship)))
        model.AddElement(nextShipVarList[ship], shipKindList, nextShipKindVarList[ship])

        nextShipSpeedVarList.append(model.NewIntVar(0, maxSpeed, "nextShipSpeedForShip"+str(ship)))
        model.AddElement(nextShipVarList[ship], speedList, nextShipSpeedVarList[ship])

        nextShipStartTimeVarList.append(model.NewIntVar(0, maxTime, "nextShipStartTimeForShip"+str(ship)))
        model.AddElement(nextShipVarList[ship], startTimeVarList, nextShipStartTimeVarList[ship])

        nextShipEndTimeVarList.append(model.NewIntVar(0, maxTime, "nextShipEndTimeForShip"+str(ship)))
        model.AddElement(nextShipVarList[ship], endTimeVarList, nextShipEndTimeVarList[ship])


    for ship in range(numOfShips):
        isOppositeDirectionNextShipVar = model.NewBoolVar("isOppositeDirectNextShipOf"+str(ship))

        model.Add(shipKindList[ship] + nextShipKindVarList[ship] == 3).OnlyEnforceIf(isOppositeDirectionNextShipVar)
        model.Add(endTimeVarList[ship] <= nextShipStartTimeVarList[ship]).OnlyEnforceIf(isOppositeDirectionNextShipVar)

        model.Add(startTimeVarList[ship] + speedList[ship]*leeway <= nextShipStartTimeVarList[ship]).OnlyEnforceIf(isOppositeDirectionNextShipVar.Not())
        model.Add(endTimeVarList[ship] + nextShipSpeedVarList[ship] * leeway <= nextShipEndTimeVarList[ship]).OnlyEnforceIf(isOppositeDirectionNextShipVar.Not())


    objectiveVar = model.NewIntVar(0, maxTime, "Objective")
    varList = []
    for ship in range(numOfShips):
        varList.append(endTimeVarList[ship])
    model.AddMaxEquality(objectiveVar, varList)
    model.Minimize(objectiveVar)

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

    if status == cp_model.INFEASIBLE:
        print("Infeasible model")

    if status == cp_model.OPTIMAL:
        print('Minimum makeSpan: %i' % solver.ObjectiveValue(), "\n")
        print("start =", [solver.Value(startTimeVarList[ship]) for ship in range(numOfShipsWithDummyShip)])
        print("end =", [solver.Value(endTimeVarList[ship]) for ship in range(numOfShipsWithDummyShip)])
        print("next =", [solver.Value(nextShipVarList[ship]) for ship in range(numOfShips)])
    print("----------------------------")




#----------------------------------------------------------------------------------------------------------------------#




def sequenceDependencyProblem2():
    model = cp_model.CpModel()

    lengthOfChannelList = [24, 32]
    maxLength = max(lengthOfChannelList)
    numOfChannels = len(lengthOfChannelList)
    numOfShips = 7
    numOfShipsWithDummyShip = numOfShips + numOfChannels
    speedList = [5, 6, 4, 5, 4, 7, 3, 0, 0]
    maxSpeed = max(speedList)
    desiredTimeList = [55, 43, 47, 33, 115, 125, 175, 400, 400]
    shipKindList = [1, 2, 1, 2, 2, 1, 2, 3, 3]
    leeway = 2
    maxTime = 600

    startTimeVarList = []
    endTimeVarList = []
    channelVarList = []
    for ship in range(numOfShipsWithDummyShip):
        startTimeVarList.append(model.NewIntVar(0, maxTime, "startTimeForShip"+str(ship)))
        endTimeVarList.append(model.NewIntVar(0, maxTime, "endTimeForShip" + str(ship)))
        channelVarList.append(model.NewIntVar(0, numOfChannels-1, "channelForShip"+str(ship)))

    nextShipVarList = []
    for ship in range(numOfShips):
        nextShipVarList.append(model.NewIntVar(0, numOfShipsWithDummyShip-1, "nextShipForShip"+str(ship)))

    for ship in range(numOfShips, numOfShipsWithDummyShip):
        model.Add(startTimeVarList[ship] == maxTime)
        model.Add(endTimeVarList[ship] == maxTime)
        model.Add(channelVarList[ship] == ship - numOfShips)

    lengthVarList = []
    for ship in range(numOfShips):
        lengthVarList.append(model.NewIntVar(0, maxLength, "lengthOfChannelForShip"+str(ship)))
        model.AddElement(channelVarList[ship], lengthOfChannelList, lengthVarList[ship])

    for ship in range(numOfShips):
        model.Add(endTimeVarList[ship] == startTimeVarList[ship] + lengthVarList[ship] * speedList[ship])
        model.Add(startTimeVarList[ship] >= desiredTimeList[ship])

    model.AddAllDifferent(nextShipVarList)

    nextShipKindVarList = []
    nextShipStartTimeVarList = []
    nextShipEndTimeVarList = []
    nextShipSpeedVarList = []
    nextShipChannelVarList = []
    for ship in range(numOfShips):

        nextShipKindVarList.append(model.NewIntVar(1, 3, "nextShipKindForShip"+str(ship)))
        model.AddElement(nextShipVarList[ship], shipKindList, nextShipKindVarList[ship])

        nextShipSpeedVarList.append(model.NewIntVar(0, maxSpeed, "nextShipSpeedForShip"+str(ship)))
        model.AddElement(nextShipVarList[ship], speedList, nextShipSpeedVarList[ship])

        nextShipChannelVarList.append(model.NewIntVar(0, numOfChannels-1, "nextShipChannelForShip" + str(ship)))
        model.AddElement(nextShipVarList[ship], channelVarList, nextShipChannelVarList[ship])

        nextShipStartTimeVarList.append(model.NewIntVar(0, maxTime, "nextShipStartTimeForShip"+str(ship)))
        model.AddElement(nextShipVarList[ship], startTimeVarList, nextShipStartTimeVarList[ship])

        nextShipEndTimeVarList.append(model.NewIntVar(0, maxTime, "nextShipEndTimeForShip"+str(ship)))
        model.AddElement(nextShipVarList[ship], endTimeVarList, nextShipEndTimeVarList[ship])


    for ship in range(numOfShips):
        isOppositeDirectionNextShipVar = model.NewBoolVar("isOppositeDirectNextShipOf"+str(ship))

        model.Add(shipKindList[ship] + nextShipKindVarList[ship] == 3).OnlyEnforceIf(isOppositeDirectionNextShipVar)
        model.Add(endTimeVarList[ship] <= nextShipStartTimeVarList[ship]).OnlyEnforceIf(isOppositeDirectionNextShipVar)

        model.Add(startTimeVarList[ship] + speedList[ship]*leeway <= nextShipStartTimeVarList[ship]).OnlyEnforceIf(isOppositeDirectionNextShipVar.Not())
        model.Add(endTimeVarList[ship] + nextShipSpeedVarList[ship] * leeway <= nextShipEndTimeVarList[ship]).OnlyEnforceIf(isOppositeDirectionNextShipVar.Not())


    for ship in range(numOfShips):
        model.Add(nextShipChannelVarList[ship] == channelVarList[ship])

    objectiveVar = model.NewIntVar(0, maxTime, "Objective")
    varList = []
    for ship in range(numOfShips):
        varList.append(endTimeVarList[ship])
    model.AddMaxEquality(objectiveVar, varList)
    model.Minimize(objectiveVar)

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

    if status == cp_model.INFEASIBLE:
        print("Infeasible model")

    if status == cp_model.OPTIMAL:
        print('Minimum makeSpan: %i' % solver.ObjectiveValue(), "\n")
        print("start =", [solver.Value(startTimeVarList[ship]) for ship in range(numOfShipsWithDummyShip)])
        print("end =", [solver.Value(endTimeVarList[ship]) for ship in range(numOfShipsWithDummyShip)])
        print("next =", [solver.Value(nextShipVarList[ship]) for ship in range(numOfShips)])
    print("----------------------------")




#----------------------------------------------------------------------------------------------------------------------#






if __name__ == '__main__':

    basicScheduling()
    schedulingWithUnaryResource()
    schedulingWithMultipleUnaryResources()
    resourceConstrainedProjectScheduling()
    sequenceDependencyProblem()
    sequenceDependencyProblem2()