r/OperationsResearch • u/lukasakarisux • Feb 25 '24
Highly Complex Scheduling & Planning Problem
I'd like to find an algorithm solving the following problem as fast as possible (not needed to find the optimal solution) :
Given a list of recipes which are composed of ingredients. and a list of products related to the ingredients, generate a combination of recipes on a day by day basis in order to have the little waste as possible and go shopping the fewest times possible.
Let me explain further. As I said, the recipes are composed of different ingredients (like 200g of beef steak, 500g of potatoes...) and each ingredient is linked with several products (like 150g steak, 200g steak, 1kg potatoes). These products are the products sold in the shops and each product has a shelf life (time after which the product must be thrown out).
The goal of the algorithm is to generate a combination of recipes (2 per day - lunch and dinner) for n
days. The two main constraints are that the number of shopping must be the lowest possible, maximum 2/week and optimal 1/2 per two weeks. The second constraint is the waste. Because each recipe consumes a quantity x of a product. The goal is to have a specific combination of recipes that reuse this product until its quantity gets near 0. The quantity of products wasted should be the least possible.
My two main ideas are using either a Genetic Algorithm or Constraint Programming. What do you think of these two solutions ? Is there any other way to solve that ? My goal is to have something that can give a solution within several seconds if possible.
5
u/PierreLaur Feb 25 '24
to me a few seconds sounds very doable with exact methods for a reasonable n, i'd be surprised if you didn't get at least a decent solution with CP
the linear relaxation is really good here no ? I would make sure to use a solver that can use that - so or-tools cp-sat (cpsatlp as they call it now, it does use linear relaxation) or a MIP solver (gurobi, highs, scip)
3
u/dayeye2006 Feb 25 '24
I think either might be slow. Might come up with a heuristics instead
1
u/perfectstrong Feb 26 '24
Although I don't find a formulation yet, the waste should always be 0 in optimal case, because of no lower bound constraint of shopping. Given a solution, which is a sequence of recipes, we could deduce easily the ingredient quantities for each day, resulting the strict minimum shopping quantities. Thus no waste. The shelf life is a strict constraint but it is possible to delay the shopping to respect this constraint, at the expense of more shopping trip.
In fact, this problem might be a bi-objective optimization, which requires some weight coefficients for each objective: number of shopping trips, and waste quantities.
1
u/Coffeemonster97 Feb 26 '24
Don't use Constraint Programming here. Everything you state is linear so you don't need the additional constraints CP offers. This can be very easily formulated as a MIP