8 Transforming data into decisions with linear programming
In a world of scarce time, budget, and talent, the chapter shows how linear programming turns prioritization into a rigorous, data-driven process. It explains constrained optimization in which a linear objective is optimized subject to linear inequalities, highlights real-world uses from logistics to manufacturing, and connects these ideas to Agile practice by scoring work items on value and effort. The essentials—linear objective and constraints, explicit decision variables, and feasibility—are clarified alongside a reminder that some problems may require non-linear methods, even though linear programming often provides an effective and interpretable first choice.
The chapter grounds these ideas in a portfolio selection problem for a fictional analytics organization (AAIM) that must choose among 20 features spread across three strategic epics. The objective is to maximize a priority score (value points divided by effort points) while respecting multiple constraints: a first-year budget cap of $700,000, a total cost cap of $1.1 million, a balanced slate of 3–4 features per epic, and an overall selection of 9–12 features. Decision variables are binary (select or not), and both the objective and constraints are expressed as linear combinations of these variables, ensuring the model satisfies linear programming requirements.
Implementation proceeds by defining the data set of features, constructing the objective from priority scores, encoding budget and epic-balance constraints, and solving with SciPy’s linprog (HiGHS). The solver returns an optimal, feasible selection of 12 features that stays within budgets and balances epics, yielding a total priority of 17.6 (about 1.47 on average per feature) and illustrative budget totals (approximately $655,000 in the first year and $1,070,000 overall). The approach is transparent, auditable, and adaptable to what‑if scenarios—such as tightening budgets or changing epic quotas—making it a practical template for transforming value-versus-effort scoring into consistent, defensible decisions.
Summary
- Linear programming is a crucial technique for efficiently allocating limited resources, such as budget, time, and materials, to achieve the best possible outcomes. It ensures that resources are utilized in the most effective way to maximize benefits or minimize costs.
- A fundamental aspect of linear programming is that both the objective function and the constraints must be linear. This means that all relationships in the model are proportional and additive, making the mathematical formulation simpler and solvable using efficient algorithms.
- The foundation of linear programming involves defining an objective function that needs to be either maximized or minimized. This function is subject to a set of linear constraints, which represent the real-world limitations and requirements, such as budget caps, resource availability, and minimum performance standards.
- One of the major strengths of linear programming is its flexibility. It allows for easy adjustments to the parameters and constraints, enabling the exploration of various "what-if" scenarios. This adaptability helps decision-makers understand the potential impacts of different strategic choices and changes in resource availability.
- Linear programming can accommodate both binary decision variables, which represent yes/no decisions (e.g., whether to undertake a project or not), and continuous decision variables, which represent quantities that can take any value within a given range. This versatility makes it suitable for a wide range of optimization problems.
- By incorporating multiple constraints, linear programming helps ensure that decisions are balanced and strategically sound. It supports comprehensive decision-making by allowing for the consideration of various objectives and priorities, ensuring that all strategic goals are advanced in a harmonious manner.
FAQ
What problem does AAIM solve with linear programming in this chapter?
AAIM needs to choose a set of features (projects) to pursue from a backlog while facing limited budget and the need to balance strategic objectives. Linear programming turns this selection into a mathematical model that maximizes value (priority scores) subject to constraints like budgets and epic balance.How is the objective function defined?
The objective is to maximize the sum of priority scores of selected features. Each feature’s priority score is value_points / effort_points. In code, the objective vectorc uses the negated ratios (because linprog minimizes): c = [-f.value_points / f.effort_points for f in features].What constraints are used, and how are they modeled?
- Budget limits: sum of first-year costs ≤ $700,000 and sum of total costs ≤ $1,100,000.- Strategic balance: each epic must contribute at least 3 and at most 4 features.
- Decision variables: bounds 0 to 1 to represent selection. These are expressed as linear inequalities using matrices
A_ub and b_ub passed to linprog.What are linear equations and inequalities, and why do they matter here?
Linear equations/inequalities express relationships as sums of constants times variables (no products of variables or nonlinear terms). Linear programming requires both the objective and all constraints to be linear so that efficient solvers can find optimal solutions.How are the epic balance constraints (3 to 4 features per epic) implemented?
For each epic, two rows are added toA_ub:- Minimum (≥ 3) is written as a ≤ inequality by multiplying coefficients by −1; the RHS becomes −3.
- Maximum (≤ 4) uses +1 coefficients with RHS 4.
This guarantees a balanced selection across the three epics.
Why are the priority scores negated in the objective vector?
linprog minimizes by default. By negating each priority score, minimizing the sum of negatives is equivalent to maximizing the original (positive) priority scores.What do result.success, result.x, and result.fun mean?
- result.success: whether the solver found a feasible optimum.-
result.x: the decision values for each feature (1 ≈ selected, 0 ≈ not). In the example, 12 features are selected.-
result.fun: the minimized objective value. Multiply by −1 to recover the maximized sum of priority scores (e.g., 17.6 total, averaging 1.47 across 12 features).Does SciPy’s linprog enforce binary (0/1) selections?
No. Bounds of (0, 1) constrain variables to that range but do not force integrality. In practice, to guarantee 0/1 decisions you need a mixed-integer linear programming (MILP) solver. Here, the relaxed LP returned 0/1 values for this instance.How are the budgets applied (first-year vs. total), and why have both?
Two separate constraints cap spending: one limits the next year’s spend (cash flow/near-term capacity), and the other caps the total lifecycle cost (overall affordability). Modeling both ensures selections are feasible in the short term and sustainable overall.How can AAIM run “what-if” scenarios?
Adjust parameters and re-solve, for example:- Change budget caps (e.g., first-year $550,000, total $850,000).
- Alter epic balance (e.g., min 2, max 3 per epic).
- Update value/effort scores or add/remove features.
The framework makes it easy to explore alternatives without rewriting core logic.
Statistics Every Programmer Needs ebook for free
