Optimization Starter

Find the most profitable product mix under resource limits and market demand constraints.

Overview

The Optimization Starter template determines the profit-maximizing product mix for a manufacturing shop operating under resource constraints and customer demand limits.

Designed as the foundational “start here” linear programming model in the Boardflare optimization gallery, it uses Wayne L. Winston’s classic Giapetto woodcarving problem (Winston, 2004). Giapetto produces wooden soldiers and wooden trains. Each toy requires finishing labor and carpentry labor, and faces weekly capacity limits on available labor hours. Given profit contributions per unit and a ceiling on weekly soldier demand, the linear programming solver identifies the exact production quantities that maximize weekly profit without exceeding any shop constraint.

• Download the Python for Excel workbook

Workbook tour

Sheet and range	Description	Role
Results (A5:B10, A13:F21, A24:G31)	Main dashboard displaying optimization status, total profit, optimal product mix, and resource capacity sensitivity with shadow prices. Rows 25-27 (the first three limits, in solver order) are checked on the Validation sheet as rows 12-14; rows 28-31 are not validated.	Output
Model (A5:J14)	Product mix input grid: unit profit contributions, resource consumption per unit across up to 6 named resource columns, capacity limits in row 14, and demand bounds. The model accepts at most 7 constraint rows in total. Filled cells in the scan window A1:AZ60 outside A5:J14 (other than the title cells A1, A2 and A4) are input errors naming the cell.	Editable input
Guide	Modeling rules that the Model sheet is checked against.	Reference
Validation (A5:E15, F5:H15)	10 checks. Six benchmark cross-checks against published figures in Winston (2004) Chapter 3, run only when Model still equals the Giapetto benchmark (otherwise they read n/a (model edited)). Three computed shadow-price checks (rows 12-14, matched by position to the first three limits) compare the displayed shadow price with a re-solve using one more unit of the limit. One duality-gap check.	Verification

Using the template

1. Inspect the baseline solve

1. Open the workbook in Excel with Python for Excel enabled.
2. View the Results sheet:
   • Status: optimal
   • Message: Optimal product mix found.
   • Total profit: $180.00 per week.
   • Products manufactured: 2 products (20 Soldiers and 60 Trains).
   • Binding limits: 2 limits (Finishing hours at 100 hrs and Carpentry hours at 80 hrs).
   • Non-binding limit: Soldier demand has 20 units of unused slack (20 produced vs. 40 max demand).

2. Evaluate resource expansion

1. Navigate to the Model sheet.
2. Locate the Available capacity row at Model!C14 (Finishing hours).
3. Increase finishing hours from 100 to 120 (e.g. by scheduling overtime).
4. Return to Results: notice total profit increases by $20 to $200.00 per week, reflecting the Finishing shadow price of $1.00 per unit of the limit (computed by the solver and confirmed by re-solving with one more unit of the limit). Both Soldier and Train production shift to 40 units each.

3. Add a new product

1. On the Model sheet, locate empty row 8 (Model!A8:J8).
2. Enter product name Rocket, unit profit \$5.00, finishing requirement 3.0 hours, carpentry requirement 1.0 hour, and maximum demand 20.0 units.
3. Return to Results: Python solves the expanded linear program, recommending 70 Trains and 10 Rockets for total profit of $190.00.

Limitations and when to use this

Free alternatives

Excel Solver, built into desktop Excel (it is not available in Excel for the web), and the free OpenSolver add-in for Windows Excel (a COIN-OR CBC add-in with no stable release since 2020) can both solve this same product mix model. Excel Solver’s Simplex LP engine accepts up to 200 decision variables and 100 constraints, which covers this template’s limits of 8 products and 7 constraint rows. This workbook solves the model as a linear program with HiGHS through SciPy’s scipy.optimize.linprog, running in Python for Excel. What it adds is the product mix input grid with named resource columns, live recalculation when inputs change, a shadow price for each limit with its meaning stated on Results, an elastic repair that suggests which limits to relax when the limits conflict, input errors that name the offending cell, and a Validation sheet that checks the solve against Winston’s (2004) published Giapetto results, re-solves the shadow prices of the first three limits, and checks the duality gap.

Customizing

Adapting to custom production mixes

• Add products: Enter up to 8 products down column A of the Model sheet (Model!A6:A13), with their profit contribution in column B and a number in each resource column. Entering limits without any product raises Enter at least one product in Model!A6:A13. (an error state, not Ready). Profit and every resource coefficient are required: a blank cell is an input error naming the cell (Model!B6 is blank.), and so is any non-numeric entry, including commas, dollar signs and text such as 1,5 or 84O (Non-numeric value '1,5' at Model!C6). Minimum production (column I) and maximum demand (column J) are optional. A row with values but a blank name is an input error naming the cell (Model!A8 is blank but row 8 has values.). Fully blank rows are skipped. A ninth product in row 14 is an error naming Model!A14, because row 14 is the capacity row.
• Add resource limits: Name up to 6 shop constraints in the column headers of row 5 (Model!C5:H5), enter resource use per unit in columns C to H, and specify total available limits in row 14 (Model!C14:H14). A column is used only when it has both a name and a limit. Each of these is an input error naming the cell: a named column with a blank limit, even with no coefficients (Model!C14: limit for 'Finishing (hours)' is blank.); a limit under a blank header; a value under a column with no name (Model!C6 has a value under an unnamed column.); and a duplicate header name, which cites the repeated header cell (e.g. Model!E5 repeats the name 'Finishing (hours)'. Rename one.). A column with no name, no limit and no values is skipped. The model accepts at most 7 constraint rows in total, counting resource limits, max-demand rows and positive-minimum rows; more rows stop the model with a capacity error.
• Insert or delete rows: The capacity row is read from row 14 (CAP_ROW in notebook.py). Inserting a product row moves the capacity row to row 15, which is outside the table, so the model stops with an error naming the stray cell Model!A15. Deleting a product row moves the capacity row to row 13 and leaves Model!A14 blank, so the model stops with an error saying Model!A14 must read ‘Available capacity’. Clear product rows rather than inserting or deleting them. If the row count must change, update CAP_ROW and the table ranges together.
• Modeling rules: The Guide sheet lists the rules the Model sheet is checked against.
• Set production bounds: Specify minimum required production in column I (Model!I6:I13) and customer demand ceilings in column J (Model!J6:J13). A blank minimum means no minimum and a blank maximum means no maximum. A negative minimum (e.g. Minimum production at Model!I6 must be zero or more.), a positive minimum below \(10^{-6}\) (e.g. Minimum production at Model!I6 must be at least 1e-6 (or zero).), a negative maximum demand (e.g. Maximum demand at Model!J6 must be zero or more.), or a negative resource limit (e.g. Limit at Model!C14 must be zero or more.) is rejected as an input error naming the cell. Zero limits, zero minimums, and zero maximum demands are valid and accepted.
• Infeasible limits diagnosis: If the limits cannot be met together, the task pane reports the model as infeasible. It then lists one suggested set of limit relaxations, each shown to one decimal place, found by an elastic repair. The pane states that other repairs may exist. If the repair finds no limit to relax, only the infeasible status appears.

Developer reference

Notebook implementation

The template logic is implemented in Marimo as a single reactive notebook (notebook.py). It declares # engine-modules: table to integrate the shared optimization engine (engine/core.py and engine/table.py).

Key architectural flow: 1. bf.inputs: Reads Model!A5:J14, the scan window Model!A1:AZ60 (stray-cell check), and Validation!A16:A17 (overflow check; filled cells in A16:A17 are an error, while cells outside that check such as Validation!B16 and A18 are not read; the Validation!A5:E15 reference table is display-only and not read into Python). 2. Input parsing: Identifies active resource columns, product rows, capacity limits, and demand bounds. Fully blank product rows and resource columns are skipped. A row with values but no name, a limit with no name, a value under a column with no name, a named column with a blank limit, a blank or non-numeric profit or resource coefficient (commas, dollar signs and text are rejected), and a duplicate header are input errors naming the cell. Any filled cell in the scan window Model!A1:AZ60 outside A5:J14 (other than A1, A2 and A4) is an input error naming the cell; cells below row 60 and beyond column AZ are not scanned. The label in A14 must read ‘Available capacity’, only C14:H14 are read, and a value in B14, I14 or J14 is an error. A model with no limit, max-demand or positive-minimum row is an error, because it would be unbounded. Benchmark matching compares values by position, not names. 3. Grid generation: Synthesizes a standardized used-range grid and passes it to table.parse_model(grid, sense="max"). 4. High-performance solve: Calls table.solve_model wrapping SciPy’s HiGHS solver (scipy.optimize.linprog(method="highs")). 5. Infeasibility analysis: When constraints conflict, calls table.explain_infeasible to solve an \(L_1\)-norm elastic slack relaxation, identifying one set of limit relaxations that restores feasibility. The task pane lists them with the current and suggested limits and states that other repairs may exist. 6. Publication: Formats tabular DataFrames and publishes to summary, plan, limits, and validation. When no model is entered, summary status reports no model and validation checks remain in a neutral not run state, as do validation checks when the result is infeasible or unbounded; input errors such as a blank or non-numeric required value, content outside the table, content in the Validation overflow cells, or a blank limit under a named column clear results and display diagnostic error callouts naming the offending sheet cell.

How the calculation/model works

The mathematical formulation is a classic continuous product mix linear program:

\[\max \quad z = \sum_{j=1}^{n} c_j x_j\]

subject to:

\[\sum_{j=1}^{n} A_{i, j} x_j \le b_i \quad \forall i = 1, \dots, m\]

\[x_j \le d_j \quad \forall j \text{ with demand limits}\]

\[x_j \ge l_j \quad \forall j \text{ with minimum production requirements}\]

\[x_j \ge 0 \quad \forall j\]

In Giapetto’s woodcarving instance: - Decision variables: \(x_1\) (Soldiers), \(x_2\) (Trains). - Objective: Maximize weekly profit \(z = 3 x_1 + 2 x_2\). - Finishing labor: \(2 x_1 + x_2 \le 100\). - Carpentry labor: \(x_1 + x_2 \le 80\). - Soldier demand: \(x_1 \le 40\). - Non-negativity: \(x_1 \ge 0, x_2 \ge 0\).

At the optimal corner point \((x_1^*, x_2^*) = (20, 60)\), the profit is $180.00. The finishing and carpentry constraints are strictly binding (\(2(20) + 60 = 100\) and \(20 + 60 = 80\)), with shadow prices of $1.00 per unit of the limit computed by the solver and confirmed by re-solving with one more unit of the limit. Soldier demand has a slack of \(40 - 20 = 20\) units, with a shadow price of $0.00 per unit of the limit computed by the solver and confirmed by re-solving with one more unit of the limit.

Validation / expected results

The Validation worksheet cross-checks solver execution against Wayne L. Winston’s Operations Research: Applications and Algorithms (4th ed., Chapter 3) for published benchmarks (Chapter 3, Example 1; the source text is at https://sites.math.washington.edu/~perkins/381AWin14/handouts/chapter3.pdf), alongside computed sensitivity checks. Expected value and Tolerance columns in the Validation worksheet are display-only; the notebook verifies against its own fixed constants rather than reading sheet values, ensuring tolerance widening cannot mask solution discrepancies.

Which checks run. The six benchmark rows (objective, Soldier and Train quantities, finishing and carpentry hours used, Soldier demand used) compare against the published Giapetto values. They run only when the Model sheet still equals the benchmark: the same coefficients, unit profits, limits, bounds and sense. Labels may change, and matching is by position, so reordering rows or columns counts as an edit. When the model is edited, those rows show n/a (model edited) with neutral status. The three shadow-price rows and the duality gap (with feasibility) run on any solved model. A check that runs and does not pass is a FAIL. Because the checks are mathematical self-consistency checks on a correct solver, the FAIL branch is reachable by a solver defect, a changed benchmark constant, or valid inputs of extreme magnitude (profits or limits near 1e9 and above), where the fixed absolute tolerances (0.01, and 1e-5 for the duality gap) are smaller than floating-point rounding; this FAIL path is not exercised in the engine test templates/optimization/engine/forms/test_product_mix.py. A shadow-price row that cannot be confirmed shows a neutral state instead: n/a (no constraint) when the model has fewer constraint rows than the check needs, n/a (perturbation infeasible) when the +1 or -1 re-solve is not optimal, and n/a (degenerate: sensitivity is one-sided) when the +1 and -1 changes are not equal and opposite. When the result is infeasible or unbounded, every check reads not run.

• Objective function: Optimal profit matches published value of $180.00 within 0.01 tolerance.
• Product quantities: Soldier production matches 20 units and Train production matches 60 units.
• Resource consumption: Finishing hours used equals 100.0 and Carpentry hours used equals 80.0.
• Demand satisfaction: Soldier demand used equals 20.0 units. The 40-unit maximum-demand row is part of the model and is not separately tested.
• Computed shadow price checks: The fetched source text does not state shadow prices, so these rows are computed, not published. For each constraint row (finishing, carpentry, then soldier demand) the notebook re-solves with that limit raised by one unit (+1) and lowered by one unit (-1). The displayed shadow price (Results, limits table) is checked against the +1 change, so an edited displayed value FAILs, and the row is confirmed only when the +1 and -1 changes are equal and opposite. Validation rows 12-14 are matched by position to the first three limit rows in solver order (Results rows 25-27), whatever those rows are named. Results rows 28-31 are not validated. On the Giapetto model:
  • Finishing: 101 hours yields $181.00 (change $1.00); 99 hours yields $179.00 (change -$1.00).
  • Carpentry: 81 hours yields $181.00 (change $1.00); 79 hours yields $179.00 (change -$1.00).
  • Soldier demand: 41 units yields $180.00 (change $0.00); 39 units yields $180.00 (change $0.00).
  On the benchmark, the expected values in the sheet are $1.00, $1.00 and $0.00. These come from the LP dual and are checked by the re-solves above, not from the source. On an edited model, the expected value is the solver’s own shadow price for that row.
• Duality gap: Evaluated via core.duality_gap. The row passes only when the gap is within \(10^{-5}\) of zero and the solution satisfies every limit. If the duality gap is unavailable, Actual and Difference publish as empty strings with status FAIL (gap not available) rather than publishing NaN.

Changelog

• 2026-10-26: Feedback round 8 fixes: rejected negative resource limits and negative maximum demands with cell-naming errors (confirming zero is accepted); rejected positive minimums below 1e-6 with a cell-naming error; made validation tolerance scenario discriminating by testing non-matching expected values with zero tolerance; removed unused Validation!A5:E15 reference from bf.inputs; prevented NaN publication in validation table when duality gap is unavailable; documented that the validation FAIL path is reachable only by solver defect, benchmark constant change or extreme-magnitude inputs (absolute tolerances) and is not exercised in test_product_mix.py.
• 2026-10-26: Feedback round 7 fixes: Validation expected values and tolerances are now fixed module-level constants in the notebook rather than read from editable sheet cells, preventing tolerance widening from masking discrepancies; negative minimum production in column I is rejected with an error naming the cell; documented that entering limits without any product raises an error state; updated duplicate-header doc to cite only the repeated header cell; and documented that Validation!B16 and A18 are not read (only A16:A17 must stay empty).
• 2026-10-26: Feedback round 6 fixes: a blank or non-numeric profit or resource coefficient is an input error naming the cell, and commas, dollar signs and text are rejected (minimum and maximum demand stay optional); a value under an unnamed resource column, or a named column with no limit, is an input error naming the cell; the displayed shadow price is checked against the +1 re-solve, so an edited value FAILs; Results rows 28-31 are labelled not validated, and rows 25-27 are checked as Validation rows 12-14; the overflow check covers Validation!A16:A17; and the Guide sheet and this page describe these rules.
• 2026-10-26: Feedback round 5 fixes: a ninth product typed into the capacity row (Model!A14) is a label error naming that cell; filled cells in the scan window Model!A1:AZ60 outside the table are input errors naming the cell (cells below row 60 and beyond column AZ are not scanned); a shadow-price row whose +1 and -1 re-solves are not equal and opposite (a degenerate vertex) reads n/a (degenerate: sensitivity is one-sided), and a row whose re-solve is not optimal reads n/a (perturbation infeasible), instead of a single one-sided value; a model with no limit, max-demand or positive-minimum row is an error; blank production bounds are documented; and the Guide sheet and this page now describe the scan window and the blank-bound rules.
• 2026-10-26: Feedback round 4 fixes: a product row with values and a blank name is an input error naming the cell (fully blank rows are still skipped); validation no longer depends on hardcoded names, so benchmark rows run only when Model equals the Giapetto benchmark and otherwise read n/a (model edited), while the shadow-price and duality-gap rows always run; a named resource column with coefficients and a blank limit is an input error naming the limit cell; any non-blank cell below the capacity row (rows 15-100) or right of column J (K-Z) is an input error naming the cell, so row insert and delete no longer shift capacity silently; the duplicate-header error cites the header cells (for example Model!E5) instead of the first table cell; the modeling rules moved to a new Guide sheet; and the default headers for unused resource columns are blank.
• 2026-10-26: Feedback round 3 fixes: shadow prices are now re-solved for every constraint row, so the last non-binding row is no longer dropped; a limit under a blank resource header is an input error instead of an unlabeled row; the capacity row is read positionally from row 14 and no longer by label; non-optimal results (infeasible or unbounded) show not run on every validation check; the Finishing, Carpentry and Soldier demand lookups match exact constraint names; resource column count and the 7-row constraint cap are shared between the notebook and workbook; the benchmark page-range citation and the “not published” shadow price claim were removed; and the test file’s unrun mutation predictions were removed.
• 2026-10-26: Feedback round 2 fixes: updated shadow price labelling to clarify they are computed and confirmed by perturbation; reported missing duality gap instead of defaulting to 0; added non-numeric input validation reporting cell coordinates; wired overflow detection for table boundaries; single-sourced resource column capacity; corrected decimal rounding note; replaced empty status with no model and neutral not run validation state; unified limit unit labels to “$ per unit of the limit”; and matched re-solve shadow prices by exact constraint name.
• 2026-10-26: Hand-crafted rebuild of the Optimization Starter template (issue boardflare/templates#240). Replaced legacy skeleton generation with field-authentic product mix layout, editable resource columns, live perturbation shadow price validation, elastic infeasibility diagnosis, and offline HiGHS verification.