Basic constraint programming modeling

basicModelingWeek2.py

from ortools.sat.python import cp_model

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



def yellowTurbanModel(movesList, timeBound, powerList, durationList):

    model = cp_model.CpModel()

    moveOccurVarList = []
    for move in movesList:
        moveOccurVarList.append(model.NewBoolVar(name=move))

    varCoeffList = []
    for index, moveOccurVar in enumerate(moveOccurVarList):
        varCoeffList.append(moveOccurVar * durationList[index])
    model.AddLinearConstraint(sum(varCoeffList), 0, timeBound)

    varCoeffList = []
    for index, moveOccurVar in enumerate(moveOccurVarList):
        varCoeffList.append(powerList[index] * moveOccurVar)
    model.Maximize(sum(varCoeffList))

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

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

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

        for index, move in enumerate(movesList):
            print(move, ":", solver.Value(moveOccurVarList[index]))
    print("----------------------------")



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



def baguaProblem(spotList, damageList, spotGroupsList):

    model = cp_model.CpModel()

    attackSpotVarDict = {}
    for spot in spotList:
        attackSpotVarDict[spot] = model.NewBoolVar(name=str(spot))

    for spotGroup in spotGroupsList:
        varCoeffList = []
        for spot in spotGroup:
            varCoeffList.append(attackSpotVarDict[spot])
        model.AddLinearConstraint(sum(varCoeffList), 0, 1)

    varCoeffList = []
    for index, spot in enumerate(spotList):
        varCoeffList.append(damageList[index] * attackSpotVarDict[spot])
    model.Maximize(sum(varCoeffList))

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

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

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

        for spot, attackSpotVar in attackSpotVarDict.items():
            print(spot, ":", solver.Value(attackSpotVar))
    print("----------------------------")




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



def baguaProblemFixedCardinality(spotList, damageList, spotGroupsList, size):

    model = cp_model.CpModel()
    numOfSpots = len(spotList)

    attackSpotVarList = []
    for i in range(size):
        attackSpotVarList.append(model.NewIntVar(0, numOfSpots-1, name="attackSpot"+str(i)))

    #symmetry breaking: ensures ordered and all different
    for i in range(size-1):
        model.Add(attackSpotVarList[i] < attackSpotVarList[i+1])


    selectSpotVarList = []
    for i in range(numOfSpots):
        selectSpotVarList.append(model.NewBoolVar(name="selectSpot"+str(i)))

    for i in range(size):
        model.AddElement(attackSpotVarList[i], selectSpotVarList, 1)

    for spotGroup in spotGroupsList:
        varCoeffList = []
        for spot in spotGroup:
            varCoeffList.append(selectSpotVarList[spot-1])
        model.AddLinearConstraint(sum(varCoeffList), 0, 1)


    damageVarList = []
    maxDamage = max(damageList)
    for i in range(size):
        damageVarList.append(model.NewIntVar(lb=0, ub=maxDamage, name="damage"+str(i)))
        model.AddElement(attackSpotVarList[i], damageList, damageVarList[i])
    model.Maximize(sum(damageVarList))


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

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

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

        for attackSpotVar in attackSpotVarList:
            solution = solver.Value(attackSpotVar)
            print("Spot", spotList[solution], "is selected")

        for index, selectSpotVar in enumerate(selectSpotVarList):
            print(spotList[index], ":", solver.Value(selectSpotVar))
    print("----------------------------")




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




def baguaProblemBoundedCardinality(spotList, damageList, spotGroupsList, size):

    model = cp_model.CpModel()
    numOfSpots = len(spotList)
    damageList = [0] + damageList
    spotList = [0] + spotList


    attackSpotVarList = []
    for i in range(size):
        attackSpotVarList.append(model.NewIntVar(0, numOfSpots, name="attackSpot"+str(i)))

    attackEquals0VarList = []
    for i in range(size):
        attackEquals0VarList.append(model.NewBoolVar(name="attackEquals0"+str(i)))

    for i in range(size):
        model.Add(attackSpotVarList[i] == 0).OnlyEnforceIf(attackEquals0VarList[i])
        model.Add(attackSpotVarList[i] > 0).OnlyEnforceIf(attackEquals0VarList[i].Not())

    #symmetry breaking: ensures ordered and all different except 0
    for i in range(size-1):
        model.Add(attackSpotVarList[i] >= attackSpotVarList[i+1]).OnlyEnforceIf(attackEquals0VarList[i])
        model.Add(attackSpotVarList[i] > attackSpotVarList[i+1]).OnlyEnforceIf(attackEquals0VarList[i].Not())


    selectSpotVarList = []
    for i in range(numOfSpots+1):
        selectSpotVarList.append(model.NewBoolVar(name="selectSpot"+str(i)))

    for i in range(size):
        model.AddElement(attackSpotVarList[i], selectSpotVarList, 1)

    for spotGroup in spotGroupsList:
        varCoeffList = []
        for spot in spotGroup:
            varCoeffList.append(selectSpotVarList[int(spot)])
        model.AddLinearConstraint(sum(varCoeffList), 0, 1)


    damageVarList = []
    maxDamage = max(damageList)
    for i in range(size):
        damageVarList.append(model.NewIntVar(lb=0, ub=maxDamage, name="damage"+str(i)))
        model.AddElement(attackSpotVarList[i], damageList, damageVarList[i])
    model.Maximize(sum(damageVarList))


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

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

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

        for attackSpotVar in attackSpotVarList:
            solution = solver.Value(attackSpotVar)
            print("Spot", spotList[solution], "is selected")

        for index, selectSpotVar in enumerate(selectSpotVarList):
            print(spotList[index], ":", solver.Value(selectSpotVar))
    print("----------------------------")





if __name__ == '__main__':

    yellowTurbanModel(movesList = ["move1", "move2", "move3", "move4"],
                      timeBound= 10,
                      powerList=[6, 8, 5, 3, 4],
                      durationList=[4, 5, 3, 2, 3])


    baguaProblem(spotList=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
                 damageList=[10, 8, 4, 2, 6, 9, 5 , 3, 8, 10],
                 spotGroupsList= [[1,4,6], [1,2,6,7], [1,3,6,8], [1,2,3], [2,9,10], [5,6,8,10], [7,8,10], [1,3,5]])


    baguaProblemFixedCardinality(spotList=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
                                 damageList=[10, 8, 4, 2, 6, 9, 5 , 3, 8, 10],
                                 spotGroupsList=[[1,4,6], [1,2,6,7], [1,3,6,8], [1,2,3], [2,9,10], [5,6,8,10], [7,8,10], [1,3,5]],
                                 size=3)


    baguaProblemBoundedCardinality(spotList=[1, 2, 3, 4, 5, 6, 7, 8, 9, 10],
                                   damageList=[10, 8, 4, 2, 6, 9, 5, 3, 8, 10],
                                   spotGroupsList=[[1,4,6], [1,2,6,7], [1,3,6,8], [1,2,3], [2,9,10], [5,6,8,10], [7,8,10], [1,3,5]],
                                   size=3)