The problem:

I have several 'objects' separated in an OR relation such as:

• {b = 360} OR {b = 160; c = 160} OR {b = 160; d = 160} OR {b = 160; e = 160}
• {a = 360} OR {a = 160; c = 160} OR {a = 160; d = 160} OR {a = 160; e = 160}
• {c = 1697; d = 1697} OR {c = 1697; d = 1019; e = 678} OR {c = 1019; d = 1697; e = 678}

There is about 80-90 of these.

I need to get one 'object' out of each of these lines in a way, that

• a >= x (where x is an arbitrary integer, it comes as a parameter)
• b >= y (where y is an arbitrary integer, it comes as a parameter)
• e > c AND e > d
• (c d) * 2 e produces the largest possible number

So long story short I need to get a and b as close as possible to x and y as possible, while c, d and e is as close as possible to each other, e being the highest value.

If you, by chance, have a good title for this, please share, it might help attract people that can help.

If you don't know the answer but know of a topic at least related, please share, so I can search better.

I already tought about bruteforcing it, but it has about 876488338465357824 possible combinations so that's not a valid way to do this.

I don't need this to be exactly perfect, a good approximation might suffice.

CodePudding user response：

In the constraints you’ve listed, nothing bounds e from above, and your objective function (c d) * 2 e grows as e grows. So when producing a solution for each line just take e = infinity, and all others finite, and you have your optimum for each line. In terms of which OR-clause you take for each line, just take one which doesn’t constrain e.

CodePudding user response：

I don't know that that formulation is exactly what you want, but to get you started, here's some Python that calls out to OR-Tools to find an optimal solution.

from ortools.sat.python import cp_model

objects = [
    [dict(b=360), dict(b=160, c=160), dict(b=160, d=160), dict(b=160, e=160)],
    [dict(a=360), dict(a=160, c=160), dict(a=160, d=160), dict(a=160, e=160)],
    [dict(c=1697, d=1697), dict(c=1697, d=1019, e=678), dict(c=1019, d=1697, e=678)],
]


def main():
    model = cp_model.CpModel()
    # Adjust as necessary.
    infinity = 9999
    x = 0
    y = 0
    variables = dict(
        a=model.NewIntVar(x, infinity, "a"),
        b=model.NewIntVar(y, infinity, "b"),
        c=model.NewIntVar(-infinity, infinity, "c"),
        d=model.NewIntVar(-infinity, infinity, "d"),
        e=model.NewIntVar(-infinity, infinity, "e"),
    )
    model.Maximize((variables["c"]   variables["d"]) * 2   variables["e"])
    model.Add(variables["e"] > variables["c"])
    model.Add(variables["e"] > variables["d"])
    for object in objects:
        indicators = []
        for possibility in object:
            indicator = model.NewBoolVar("")
            for key, value in possibility.items():
                model.Add(variables[key] == value).OnlyEnforceIf(indicator)
            indicators.append(indicator)
        model.AddBoolOr(indicators)
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    if status == cp_model.OPTIMAL:
        print({key: solver.Value(variable) for (key, variable) in variables.items()})


if __name__ == "__main__":
    main()