Solutions are the same for darts game

Answered

August 30, 2021 16:32 Edited

Hi,

I want to know where a player can throw at when playing a darts game. The goal of a darts game is to checkout with a double or double bullseye. When s=4 is the legal moves are:

S1, S2, D1 and D2

S3 and T1 are not legal because they result in s=1 from which checkout is not possible.

There are a total of 62 possible actions. 20 singles, 20 doubles, 20 triples, single bullseye and double bullseye

singles_z = ['S1', 'S2', 'S3', 'S4', 'S5', 'S6', 'S7', 'S8', 'S9', 'S10', 'S11', 'S12', 'S13', 'S14', 'S15', 'S16', 'S17', 'S18', 'S19', 'S20']
doubles_z = ['D1', 'D2', 'D3', 'D4', 'D5', 'D6', 'D7', 'D8', 'D9', 'D10', 'D11', 'D12', 'D13', 'D14', 'D15', 'D16', 'D17', 'D18', 'D19', 'D20']
triples_z = ['T1', 'T2', 'T3', 'T4', 'T5', 'T6', 'T7', 'T8', 'T9', 'T10', 'T11', 'T12', 'T13', 'T14', 'T15', 'T16', 'T17', 'T18', 'T19', 'T20']
bullseye_z = ['SB', 'DB']

The numerical scores of above are defined as

singles_h = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20]
doubles_h = [2, 4, 6, 8, 10, 12, 14, 16, 18, 20, 22, 24, 26, 28, 30, 32, 34, 36, 38, 40]
triples_h = [3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 33, 36, 39, 42, 45, 48, 51, 54, 57, 60]
bullseye_h = [25, 50]

Next, I define the model

s = 4 
m = gurobi.Model()
m.Params.LogToConsole = 0
m.Params.PoolSearchMode = 2
m.Params.PoolSolutions = 62 # maximum possible actions


singles = m.addVars(20, vtype=gurobi.GRB.BINARY, name=singles_z)
doubles = m.addVars(20, vtype=gurobi.GRB.BINARY, name=doubles_z)
triples = m.addVars(20, vtype=gurobi.GRB.BINARY, name=triples_z)
bullseye = m.addVars(2, vtype=gurobi.GRB.BINARY, name=bullseye_z)
new_score = m.addVar(vtype=gurobi.GRB.BINARY, name="new score")


# only one dart is thrown
m.addConstr(gurobi.quicksum(singles) +
            gurobi.quicksum(doubles) +
            gurobi.quicksum(triples) +
            gurobi.quicksum(bullseye) == 1)

# in the case of no checkout; new score >= 2
m.addConstr(s - gurobi.quicksum(singles[i] * singles_h[i] for i in range(20)) -
                gurobi.quicksum(doubles[i] * doubles_h[i] for i in range(20)) -
                gurobi.quicksum(triples[i] * triples_h[i] for i in range(20)) -
                gurobi.quicksum(bullseye[i] * bullseye_h[i] for i in range(2)) >= 2 * new_score)

# in the case of a checkout, new score = 0
m.addConstr((new_score == 0) >> (s - gurobi.quicksum(singles[i] * singles_h[i] for i in range(20)) -
                                     gurobi.quicksum(doubles[i] * doubles_h[i] for i in range(20)) -
                                     gurobi.quicksum(triples[i] * triples_h[i] for i in range(20)) -
                                     gurobi.quicksum(bullseye[i] * bullseye_h[i] for i in range(2)) == 0))

# in addition, in the case of a checkout, there should be a double or bullseye
m.addConstr((new_score == 0) >> (gurobi.quicksum(doubles) + gurobi.quicksum(bullseye) == 1))

m.optimize()

if m.Status == gurobi.GRB.OPTIMAL:
    solutions = m.SolCount
    print(f'found {solutions} solutions')

    for solution in range(0, solutions):
        m.setParam(gurobi.GRB.Param.SolutionNumber, solution)
        if solution == 0:
            for i in range(20):
                if singles[i].X == 1:
                    print("%s used" % (singles_z[i]))
                if doubles[i].X == 1:
                    print("%s used" % (doubles_z[i]))
                if triples[i].X == 1:
                    print("%s used" % (triples_z[i]))
            for i in range(2):
                if bullseye[i].X == 1:
                    print("%s used" % (bullseye_z[i]))
        else:
            for i in range(20):
                if singles[i].Xn == 1:
                    print("%s used" % (singles_z[i]))
                if doubles[i].Xn == 1:
                    print("%s used" % (doubles_z[i]))
                if triples[i].Xn == 1:
                    print("%s used" % (triples_z[i]))
            for i in range(2):
                if bullseye[i].Xn == 1:
                    print("%s used" % (bullseye_z[i]))

After running the script, I get the following output:

Why is D1 two times a solution? After inspecting m.getVars() for the two solutions, I don't see any differences.

Thanks in advance!

Comments

10 comments

Official comment
Simranjit Kaur

Gurobi Staff

June 23, 2025 02:48 Edited
This post is more than three years old. Some information may not be up to date. For current information, please check the Gurobi Documentation or Knowledge Base. If you need more help, please create a new post in the community forum. Or why not try our AI Gurobot?.
Matthias Miltenberger

Gurobi Staff

August 30, 2021 10:16
Hi Huib,

It seems that you have deleted your previous post about the same issue - including the entire discussion. This community forum is also meant to help solve similar issues of other users, so please do not delete your post after it has been answered.

Best regards,
Matthias
0
Huib Meulenbelt

August 30, 2021 11:19
Hi Matthias,

Noted. The answer of Jaromił gave as output only S2. I included his excellent tips and added the loop over the solutions, making this question/script way more robust. However, as a result my question changed to such an extend I believed I needed to open a new topic.
0
Matthias Miltenberger

Gurobi Staff

August 30, 2021 11:27
Hi Huib,

It is completely fine to open a new post - also for related questions. This is actually good practice to keep single posts more concise and to the point.

With the original discussion inaccessible now, your new post is more difficult to comprehend and answer.

Best regards,
Matthias
0
Huib Meulenbelt

August 30, 2021 16:39
Understood. Basically I want to know why SolutionNumber 1 is equal to SolutionNumber 4. If I run the code below for solution #1
```
print([(var.Xn, var.VarName) for var in m.getVars() if var.Xn != 0])
```
I get the following output

[(1.0, 'D1'), (1.0, 'new score')]

If I run the same for #4 I get:

[(1.0, 'D1'), (1.0, 'new score')]

So, the solutions are the same right? Why doesn't my model observe this? Thanks in advance
0
Huib Meulenbelt

August 31, 2021 17:08
After searching for similar topics I found the this topic https://support.gurobi.com/hc/en-us/community/posts/360074565451-Unexpected-identical-solutions-in-solutions-pool

Here the solution is to change PoolSearchMode to 1. If I do this, I only get a single solution, namely S1.

"The behavior comes from how indicator constraints are handled during presolving." Can I change something in my code that prevents this mentioned behavior? Or is there another solution with PoolSearchMode = 1. Thanks in advance
0
Tobias Achterberg

Gurobi Staff

August 31, 2021 23:28
It is an interesting coincidence that you are running into this issue now, because I am currently trying to improve this behavior of Gurobi. I think that I found a nice way to do so and will pick up your model as an additional test. Thanks!
0
Tobias Achterberg

Gurobi Staff

August 31, 2021 23:33
Indeed, with our current development version, I still get the wrong behavior for your model:
```
found 5 solutions
S2 used
D1 used
S1 used
D2 used
D1 used
```
But with my fix I get
```
found 4 solutions
S2 used
D1 used
S1 used
D2 used
```
I guess this is what you would have expected.

This fix will most likely be part of the Gurobi 9.5 release, which is scheduled for November 2021.
1
Huib Meulenbelt

September 01, 2021 06:21
Okay good to hear! Looking forward to the new release!
0
Maliheh Aramon

Gurobi Staff

December 01, 2021 00:09
Hi Huib,

Gurobi 9.5 was recently released. Included in this release is a fix for the bug you observed, reporting duplicate solutions for a model with indicator constraints and PoolSearchMode=2. Using Gurobi 9.5, you should see the output you expected.

We hope this fix works well for you. Thank you for reporting this bug and please let us know of any other issues in the future.

Best regards,

Maliheh
0

Post is closed for comments.

Solutions are the same for darts game

Comments

Didn't find what you were looking for?