How to define that m successive variables should be the same
Answered
Hi all,
Player A and player B participate in a tennis game. Each player can "serve" m times. A player wins when he scores n points. The number of points of A is a and the number of points of B is b. E is the event associated with all the sequences of a + b in a game started by A that results in a (resp., b) points scored by A (resp., B).
The number of completed service sequences (of m serves) is K. R is the number of remaining server by either A or B during the last serve and is always smaller than m.
I wrote the following Python to calculate K and R.
import gurobipy as gurobi
from gurobipy import GRB
def calculate_k_and_r(a: int, b: int, m: int, n: int) -> list:
model = gurobi.Model()
R = model.addVar(vtype=GRB.INTEGER, name='K', lb=0)
K = model.addVar(vtype=GRB.INTEGER, name='R', lb=0)
model.addConstr(gurobi.quicksum([K * m + R]) == a + b)
model.addConstr(R <= m - 1)
model.optimize()
return [K.Xn, R.Xn]
Now E can be decomposed into
- Ka:= ceil(K / 2) service sequences by A
- Kb:= floor(K / 2) service sequences by B
- R serves of A (resp., B) when K is even (resp., when K is odd)
If we take a score trajectory where A starts, a = 5, b = 1, m = 2, we get Ka = 2, Kb = 1 and R = 0. A potential score trajectory looks as follows:
- (0, 0)
- (1, 0)
- (2, 0)
- (3, 0)
- (3, 1)
- (4, 1)
- (5, 1)
Indeed we see 2 complete service sequences of A, 1 complete service sequence of B and 0 remaining serves for B's last service sequence (3, 0).
I would like to transform the above data to the following format:
[A, A, B, B, A, A, B]
or
[1, 1, 0, 0, 1, 1, 0]
model = gurobi.Model()
serves = [model.addVar(vtype=GRB.BINARY, name=f'serve_{s+1}') for s in range(a + b)]
How should I define the constraint that m Vars in `serves` are the same value? We also need to check whether R != 0 for the last Var.
Please advice
-
Hi Huib,
The question you have posed doesn't need to be posed as an optimization problem. If you have the expression
K * m + R == a + b
and all values are non-negative integers with R < m then K, R can be calculated as
K = floor( (a+b)/m) # or (a+b)//m in Python
R = a+b - K*mThe sequence that you're wanting to print can be achieved with
arr = ["B"]*(a+b+1)
arr[::2*m] = ["A"]*len(arr[::2*m])
arr[1::2*m] = ["A"]*len(arr[1::2*m])
print(arr)You mentioned that a player wins when they reach n points, but you neither use the value of n inside your function, or explain how it relates to the outputs you want to see.
Can you please clarify?
- Riley
0 -
Ah yes, thank you for taking a look at it. So, I was making it way too difficult.
You're right, I excluded that from my question to simplify the project. But a player wins when he reaches n points or when there is a tie (both players score n - 1) and the player wins two consecutive points hereafter. In the case of a tie, the serve changes per point. How would you include these rules into your array?
0 -
Hi Huib,
I think we're still missing a part of the question here.
Let's say n = 5, a = 0, b = 0. So a game of "first to 5" is about to start.
What do you want to do with this information? If there was a question such as "how many different ways can player A win, given the current scores" then this would make more sense, but at the moment it is not clear what you are wanting to produce and how the value of n affects this.
Maybe we can use n = 5, a = 0, b = 0 as an example. What are the exact outputs you would like to see in this case?
- Riley
0 -
Hi Riley,
In the end that's exactly what I want to do; get all the different ways a score can be achieved. To be precise, I want all the ways A (B) can score a (b) points on his own serve. Below is my script where the output is all the different paths:
def get_score_on_serve_sequences(a: int, b: int, m: int, n: int, server: str, receiver: str) -> list:
sequences = []
model = create_model()
served = get_serve_sequence(a=a, b=b, m=m, n=n, server=server, receiver=receiver)
scored = [model.addVar(vtype=GRB.BINARY, name=f'serve_{idx+1}') for idx, _ in enumerate(served)]
if server == 'A':
model.addConstr(gurobi.quicksum([serve * score for serve, score in zip(served, scored)]) == a)
else:
model.addConstr(gurobi.quicksum([serve * score for serve, score in zip(served, scored)]) == b)
model.addConstrs((scored[_] == 0 for _, serve in enumerate(served) if serve == 0))
model.optimize()
if model.Status == GRB.OPTIMAL:
solutions = model.SolCount
for solution in range(0, solutions):
model.setParam(GRB.Param.SolutionNumber, solution)
sequences.append([int(score.Xn) for score in scored])
return sequencesHowever, I want to rewrite my function get_serve_sequence(). I used your earlier suggestion to write the following:
def get_serve_sequence(a: int, b: int, m: int, n: int, server: str, receiver: str) -> list:
sequence = [receiver] * (a + b + 1)
sequence[::2 * m] = [server] * len(sequence[::2 * m])
sequence[1::2 * m] = [server] * len(sequence[1::2 * m])
return sequenceHowever, now I want to also include a tie. When a tie is reached at score n - 1, n - 1, the server changes per turn.
So the output of get_serve_sequence(a=14, b=12, m=2, n=11, server='A', receiver='B') should be
['A', 'A', 'B', 'B', 'A', 'A', 'B', 'B', 'A', 'A', 'B', 'B', 'A', 'A', 'B', 'B', 'A', 'A', 'B', 'B', 'A', 'B', 'A', 'B', 'A', 'B']
0 -
Hi Huib,
I think something like this would work. Some of the numbers may need tweaking as I haven't tested it, but this is the general idea.
def get_serve_sequence(a: int, b: int, m: int, n: int, server: str, receiver: str) -> list:
sequence = [receiver] * (a + b + 1)
sequence[::2 * m] = [server] * len(sequence[::2 * m])
sequence[1::2 * m] = [server] * len(sequence[1::2 * m])
if a + b > 2*(n-1):
sequence[:2*(n-1)-a-b] = [receiver] * (a+b - 2*(n-1))
sequence[2*(n-1)::2] = [server] * sequence[2*(n-1)::2]
return sequence
Unfortunately, mixed integer linear programming is really not the appropriate solution to "get all the different ways a score can be achieved". This is either solved directly with binomial coefficients, or with dynamic programming.Your model doesn't have an objective so the solver will stop at the first feasible solution, and model.SolCount will always be 1. You could force it to find multiple solutions using SolutionPools, but then you need to tell it how many solutions to find - which is the problem you're trying to solve.
- Riley
0
Please sign in to leave a comment.
Comments
5 comments