Decision Problem Catalog¶

The Euboulia decision engine ships with a catalog of solved optimization problems — used both for automated testing and for live demos. For how a decision is created and solved, see Decisions; this page is the reference list of the problems themselves.

There are three groups: benchmark problems (self-contained and deterministic — bundled for CI testing), knowledge-graph problems (constraint data pulled live from a connected graph), and the supply-chain scenarios (a manufacturing-scheduling ladder of increasing realism).

Benchmark problems (self-contained, deterministic)¶

These 16 problems are bundled with the engine for automated testing — each is fully specified in its prompt and has a known optimum.

1. bakery — A bakery uses a stand-mixer and a slow bake oven to make bread and cookies. Each machine can run for at most 3000 hours per year. To bake a loaf of bread takes 1 hour in the stand mixer and 3 hours in the oven. A batch of cookies requires 0.5 hours in the mixer and 1 hour in the oven. The profit per loaf of bread is $5 and the profit per batch of cookies is $3. How should the bakery operate to maximize total profit?

2. terracotta_jars — An artisan makes two types of terracotta jars: a thin jar and a stubby jar. Each thin jar requires 50 minutes of shaping time and 90 minutes of baking time. Each stubby jar requires 30 minutes of shaping time and 150 minutes of baking time. Per week, there are 3000 minutes available for shaping and 4000 minutes available for baking. The profit per thin jar is $5 and the profit per stubby jar is $9. How many jars of each type should the artisan make to maximize profit?

3. office_printers — An office supply company makes two types of printers: color printers and black and white printers. Different sections of the factory with different teams produce each printer. The color printer team can produce at most 20 color printers per day while the black and white printer team can produce at most 30 black and white printers per day. Both teams require use of the same paper tray installing machine and this machine can make at most 35 printers of either type each day. Color printers generate a profit of $200 per printer while black and white printers generate a profit of $70 per printer. How many of each printer should be made to maximize the company's profit?

4. hand_sanitizer — A company make both liquid and foam hand sanitizer. Liquid hand sanitizer requires 40 units of water and 50 units of alcohol. Foam hand sanitizer requires 60 units of water and 40 units of alcohol. The company has available 2000 units of water and 2100 units of alcohol. The number of foam hand sanitizers made must exceed the number of liquid hand sanitizers. In addition, at most 30 liquid hand sanitizers can be made. If each liquid hand sanitizer can clean 30 hands and each foam hand sanitizer can clean 20 hands, how many of each should the company make to maximize the number of hands that can be cleaned?

5. diabetes_medicine — A university research lab can make two types of diabetes medicine, medicine A and medicine B. Per dose, medicine A takes 30 units of imported material and 50 units of mRNA to make. Per dose, medicine B takes 40 units of imported material and 30 units of mRNA to take. The lab has available at most 300 units of imported material and 400 units of mRNA. The lab can make at most 5 doses of medicine A and the number of doses of medicine B must be larger than the number of doses of medicine A. If one dose of medicine A can treat 12 people and one dose of medicine B can treat 8 people, how many doses of each should be made to maximize the number of people that can be treated?

6. diet — A car manufacturing company makes hamburgers and chicken wraps for workers. They need to ensure workers get at least 2200 calories, 50 grams of protein, and 70 grams of carbs. One hamburger costs $6.5 and contains 800 calories, 19 grams of protein, and 20 grams of carbs. One chicken wrap costs $4 and contains 450 calories, 12 grams of protein, and 10 grams of carbs. What is the minimum cost diet that the company can provide for its workers?

7. children_transport — Children can go to school either by van or by minibus. A van can take 6 kids and produces 7 units of pollution. A minibus can take 10 kids and produced 10 units of pollution. There are at least 150 kids than need to go to school and at most 10 minibuses can be used. In addition, the number of vans used must exceed the number of minibuses. How many of each should be used to minimize the total amount of pollution produced?

8. medicine_machines — A patient can be hooked up to two machines to have medicine delivered, machine 1 and machine 2. Machine 1 delivers 0.5 units of medicine to the heart per minute and 0.8 units of medicine per minute to the brain. Machine 2 delivers 0.3 units of medicine per minute to the heart and 1 unit of medicine per minute to the brain. In addition however, machine 1 creates 0.3 units of waste per minute while machine 2 creates 0.5 units of waste per minute. If at most 8 units of medicine can be received by the heart and at least 4 units of medicine should be received by the brain, how many minutes should each machine be used to minimize the total amount of waste produced?

9. project_selection — A research department has 5 project proposals. Each project has a cost (in thousands of dollars): project 1 costs 150, project 2 costs 200, project 3 costs 100, project 4 costs 250, and project 5 costs 120. Each project has an expected impact score: project 1 scores 80, project 2 scores 120, project 3 scores 50, project 4 scores 130, and project 5 scores 70. The total budget is 500 thousand dollars. Select which projects to fund to maximize total impact.

10. nurse_scheduling — A clinic needs to assign 6 nurses to 3 shifts (morning, afternoon, night). Each nurse must work exactly one shift and each shift must have at least 2 nurses. Nurse availability: Alice can work morning or afternoon, Bob can work afternoon or night, Carol can work any shift, Dave can work morning or night, Eve can work morning or afternoon, and Frank can only work night. Find a valid assignment.

11. impossible_delivery — A courier company has 3 trucks, each with a capacity of 100 kg. There are 4 deliveries requiring 90 kg, 95 kg, 85 kg, and 80 kg respectively. Each delivery must go on exactly one truck and cannot be split across trucks. Minimize the number of trucks used. (Deliberately infeasible — exercises the engine's infeasibility detection.)

12. ore_blending — A foundry blends 3 types of ore to produce 1000 kg of alloy. Ore A costs $12 per kg and contains 45% iron and 2% carbon. Ore B costs $8 per kg and contains 30% iron and 5% carbon. Ore C costs $6 per kg and contains 20% iron and 3% carbon. The final alloy must contain exactly 35% iron and at least 3% carbon. Determine the amount of each ore to use to minimize the total raw material cost.

13. weekly_production — A factory produces widgets over 3 weeks. Production capacity is 100 units per week. Weekly demand is: week 1 needs 80 units, week 2 needs 120 units, and week 3 needs 90 units. Each unit costs $10 to produce. Units produced in excess of demand can be stored for $2 per unit per week. Storage capacity is 50 units. All demand must be met each week. Minimize the total cost of production and storage.

14. safety_recommendations — A national aviation safety authority has 8 open safety recommendations from recent accident investigations. Each recommendation has an estimated implementation cost (in thousands of euros) and a risk reduction impact score based on occurrence severity and recurrence patterns from the knowledge graph. SR-001 (engine failure detection system) costs 350 and scores 85. SR-002 (runway incursion prevention) costs 180 and scores 60. SR-003 (bird strike protection) costs 500 and scores 95. SR-004 (crew fatigue monitoring) costs 120 and scores 40. SR-005 (de-icing procedure update) costs 280 and scores 75. SR-006 (TCAS software upgrade) costs 450 and scores 90. SR-007 (documentation improvement) costs 90 and scores 30. SR-008 (ATC communication protocol) costs 200 and scores 55. The annual safety improvement budget is 1000 thousand euros. Select which recommendations to implement to maximize total risk reduction.

15. inspector_allocation — An aviation safety authority must allocate 20 safety inspectors across 8 airline operators for the next quarter. Each operator has a risk density score derived from their occurrence history in the knowledge graph (incidents per aircraft per year). AlphaAir has risk density 0.267 and needs 2-5 inspectors. BetaJet has risk density 0.267 and needs 1-4 inspectors. GammaWings has risk density 0.750 and needs 1-4 inspectors. DeltaFly has risk density 0.100 and needs 2-5 inspectors. EpsilonAir has risk density 0.400 and needs 1-4 inspectors. ZetaCargo has risk density 0.400 and needs 1-3 inspectors. EtaCharter has risk density 0.300 and needs 1-2 inspectors. ThetaRegional has risk density 0.257 and needs 2-4 inspectors. Allocate inspectors to maximize total weighted risk coverage.

16. fleet_inspection — An airline operates 5 aircraft types and must schedule safety inspections over 4 weeks. The maintenance facility can perform at most 3 inspections per week. Each aircraft type has a failure risk score derived from incident frequency in the knowledge graph: A320 scores 8, B737 scores 6, ATR72 scores 9, E190 scores 4, and CRJ900 scores 7. Inspecting a type earlier provides more risk reduction — the benefit of inspecting type k in week t is proportional to the risk score multiplied by the fraction of remaining weeks. Each type must be inspected at least once. Each type can be inspected at most once per week. Maximize total risk reduction across all inspections.

Knowledge-graph problems (aviation safety graph required)¶

These three run off a connected knowledge graph — the constraint data is queried from the graph at solve time, not typed by the analyst. They power live demos with the aviation safety use case.

17. Safety inspection budget allocation — Allocate a fixed budget across airline operators. Euboulia queries the graph for operators and their incident severity, pre-computes a risk score per operator, and formulates a bounded LP: the highest-risk operator takes the largest share while every operator keeps a minimum floor.

18. Aircraft type inspection prioritization — Select which aircraft types to inspect under capacity and budget limits. Euboulia queries the graph for aircraft types and damage levels, classifies them by fleet complexity, and formulates a binary knapsack with a priority bonus for high-severity damage.

19. Airport risk mitigation scheduling — Schedule safety audits across airports based on incident history. Euboulia queries the graph for airports and their incidents, injuries and damage, and formulates a weighted scheduling problem.

Supply-chain scenarios (manufacturing scheduling)¶

A ladder of the same decision — maximize the coverage of a daily production plan over a 3-day horizon — with one more real-world wrinkle at each step. Each adds exactly one structural feature, so the optimum moves for a clear reason. See Decisions → Worked example for the narrative.

The eligibility rules, the machine that's down, and the scarce material each pull the optimum below what raw capacity alone would allow — and the shadow prices say which limit is binding.

20. escenario_0_0 — A factory schedules production over a 3-day horizon (D0, D1, D2) to maximize coverage of make-to-stock targets. There are 4 finished products (A, B, C, D) made on 2 active machines (M1, M2). Each machine runs one 8-hour shift per day, so 8 available machine-hours per machine per day. Every machine produces every product at a uniform rate of 10 pieces per hour, with no setup or changeover times. Each product has a daily stock target of 40 pieces. Each finished product consumes 4 units of its dedicated raw material per piece, and 1000 units of each raw material are available per day. Constraints: production of each product summed across machines on each day must not exceed that product's daily stock target; the total time used on each machine each day must not exceed its available hours; raw-material consumption each day must not exceed the available inventory; all quantities are non-negative. Maximize the total number of pieces produced across all products, machines, and days.

{
  "NumProducts": 4,
  "NumMachines": 2,
  "NumDays": 3,
  "NumMaterials": 4,
  "Demand": [[40,40,40],[40,40,40],[40,40,40],[40,40,40]],
  "Rate": [[10,10],[10,10],[10,10],[10,10]],
  "Hours": [[8,8,8],[8,8,8]],
  "BOM": [[4,0,0,0],[0,4,0,0],[0,0,4,0],[0,0,0,4]],
  "Inv": [[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000]]
}

21. escenario_1_0 — A factory schedules production over a 3-day horizon on 2 machines (M1, M2). There are 8 products: 4 standard make-to-stock products (A, B, C, D) each with a daily stock target of 40 pieces, and 4 non-standard make-to-order products (A', B', C', D') each with confirmed daily orders of 40 pieces. Production rates differ by machine: M1 makes each standard product at 12 pieces/hour and each non-standard product at 6 pieces/hour; M2 makes each standard product at 6 pieces/hour and each non-standard product at 12 pieces/hour. Each machine has 8 available hours per day. Each standard product consumes 4 units of its dedicated raw material per piece; each non-standard product consumes 5 units; 1000 units of each raw material are available per day. Constraints: production of each product across machines each day must not exceed its daily demand (stock target or order); machine-time used per machine per day must not exceed its available hours; raw-material consumption per day must not exceed inventory; quantities non-negative. Maximize total pieces produced.

{
  "NumProducts": 8,
  "NumMachines": 2,
  "NumDays": 3,
  "NumMaterials": 8,
  "Demand": [[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40]],
  "Rate": [[12,6],[12,6],[12,6],[12,6],[6,12],[6,12],[6,12],[6,12]],
  "Hours": [[8,8,8],[8,8,8]],
  "BOM": [[4,0,0,0,0,0,0,0],[0,4,0,0,0,0,0,0],[0,0,4,0,0,0,0,0],[0,0,0,4,0,0,0,0],[0,0,0,0,5,0,0,0],[0,0,0,0,0,5,0,0],[0,0,0,0,0,0,5,0],[0,0,0,0,0,0,0,5]],
  "Inv": [[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000]]
}

22. escenario_2_0 — A factory schedules production over a 3-day horizon (D0, D1, D2) on 2 machines (M1, M2). There are 8 products: 4 standard make-to-stock products (A, B, C, D) each with a daily stock target of 40 pieces, and 4 non-standard make-to-order products (A', B', C', D') each with confirmed daily orders of 40 pieces. Production rates differ by machine: M1 makes each standard product at 12 pieces/hour and each non-standard product at 6 pieces/hour; M2 makes each standard product at 6 pieces/hour and each non-standard product at 12 pieces/hour. Each machine has 8 available hours per day, except machine M1 is down on day D2 (0 available hours that day). Machine eligibility is restricted: machine M1 cannot produce products A or B, and machine M2 cannot produce products A' or B'. Each standard product consumes 4 units of its dedicated raw material per piece; each non-standard product consumes 5 units; 1000 units of each raw material are available per day. Constraints: production of each product across machines each day must not exceed its daily demand (stock target or order); the time used on each machine per day must not exceed its available hours; a machine may only produce products it is allowed to; raw-material consumption per day must not exceed inventory; all quantities are non-negative. Maximize the total number of pieces produced across all products, machines, and days.

{
  "NumProducts": 8,
  "NumMachines": 2,
  "NumDays": 3,
  "NumMaterials": 8,
  "Demand": [[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40]],
  "Rate": [[12,6],[12,6],[12,6],[12,6],[6,12],[6,12],[6,12],[6,12]],
  "Hours": [[8,8,0],[8,8,8]],
  "BOM": [[4,0,0,0,0,0,0,0],[0,4,0,0,0,0,0,0],[0,0,4,0,0,0,0,0],[0,0,0,4,0,0,0,0],[0,0,0,0,5,0,0,0],[0,0,0,0,0,5,0,0],[0,0,0,0,0,0,5,0],[0,0,0,0,0,0,0,5]],
  "Inv": [[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000],[1000,1000,1000]],
  "Possibility": [[0,0,1,1,1,1,1,1],[1,1,1,1,0,0,1,1]]
}

23. escenario_3_0 — A factory schedules production over a 3-day horizon (D0, D1, D2) on 2 machines (M1, M2). There are 8 products: 4 standard make-to-stock products (A, B, C, D) each with a daily stock target of 40 pieces, and 4 non-standard make-to-order products (A', B', C', D') each with confirmed daily orders of 40 pieces. Production rates differ by machine: M1 makes each standard product at 12 pieces/hour and each non-standard product at 6 pieces/hour; M2 makes each standard product at 6 pieces/hour and each non-standard product at 12 pieces/hour. Each machine has 8 available hours per day, except machine M1 is down on day D2 (0 available hours that day). Machine eligibility is restricted: machine M1 cannot produce products A or B, and machine M2 cannot produce products A' or B'. Each standard product consumes 4 units of its dedicated raw material per piece; each non-standard product consumes 5 units; raw material is scarce — only 120 units of each raw material are available per day. Constraints: production of each product across machines each day must not exceed its daily demand (stock target or order); the time used on each machine per day must not exceed its available hours; a machine may only produce products it is allowed to; raw-material consumption per day must not exceed inventory; all quantities are non-negative. Maximize the total number of pieces produced across all products, machines, and days.

{
  "NumProducts": 8,
  "NumMachines": 2,
  "NumDays": 3,
  "NumMaterials": 8,
  "Demand": [[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40],[40,40,40]],
  "Rate": [[12,6],[12,6],[12,6],[12,6],[6,12],[6,12],[6,12],[6,12]],
  "Hours": [[8,8,0],[8,8,8]],
  "BOM": [[4,0,0,0,0,0,0,0],[0,4,0,0,0,0,0,0],[0,0,4,0,0,0,0,0],[0,0,0,4,0,0,0,0],[0,0,0,0,5,0,0,0],[0,0,0,0,0,5,0,0],[0,0,0,0,0,0,5,0],[0,0,0,0,0,0,0,5]],
  "Inv": [[120,120,120],[120,120,120],[120,120,120],[120,120,120],[120,120,120],[120,120,120],[120,120,120],[120,120,120]],
  "Possibility": [[0,0,1,1,1,1,1,1],[1,1,1,1,0,0,1,1]]
}