Saturday 26 August 2023

What does OR-Tools' CP-SAT favor the first variable?

I have a function that solves the Stigler Diet problem using the CP-SAT solver (instead of the linear solver) and minimizes error (instead of minimizing the quantity of food).

Initially, I was trying to use AddLinearConstraint to specify the minimum and maximum allowable amount of each nutrient, but the solver returned that this problem was "Infeasible". So, I just used the minimum bound and printed which nutrient was out of bounds.

For some reason, the solver chooses a solution whose first variable is far larger than the other variables, no matter what variable (nutrient) is first. For example, the allowable amount of Calcium is between 1,300 mg and 3,000 mg, but it choses a solution of 365,136 mg. If I change the first variable to Carbohydrates, then the new solution's Carbohydrate value is similarly out of proportion, while the other variables (including Calcium) are within the allowable bounds.

Why does the solver favor the first variable? If I can understand this, then I think I should be able to figure out how to get all variables within the bounds.

Below is the essential part of my program. Full working code is here: https://github.com/TravisDart/nutritionally-complete-foods

# "nutritional_requirements" and "foods" are passed in from CSV files after some preprocessing.
def solve_it(nutritional_requirements, foods):
    model = cp_model.CpModel()

    quantity_of_food = [
        model.NewIntVar(0, MAX_NUMBER * NUMBER_SCALE, food[2]) for food in foods
    ]
    error_for_quantity = [
        model.NewIntVar(0, MAX_NUMBER * NUMBER_SCALE, f"Abs {food[2]}") for food in foods
    ]

    for i, nutrient in enumerate(nutritional_requirements):
        model.Add(
            sum([food[i + FOOD_OFFSET][0] * quantity_of_food[j] for j, food in enumerate(foods)]) > nutrient[1][0]
        )
        model.AddAbsEquality(
            target=error_for_quantity[i],
            expr=sum([food[i + FOOD_OFFSET][0] * quantity_of_food[j] for j, food in enumerate(foods)]) - nutrient[1][0],
        )

    model.Minimize(sum(error_for_quantity))

    solver = cp_model.CpSolver()
    # The solution printer displays the nutrient that is out of bounds.
    solution_printer = VarArraySolutionPrinter(quantity_of_food, nutritional_requirements, foods)

    status = solver.Solve(model, solution_printer)
    outcomes = [
        "UNKNOWN",
        "MODEL_INVALID",
        "FEASIBLE",
        "INFEASIBLE",
        "OPTIMAL",
    ]
    print(outcomes[status])


from What does OR-Tools' CP-SAT favor the first variable?

No comments:

Post a Comment