Operational Research

Work with the linear algebra a program is written in

• Given vectors in ${\mathbb{R}}^n$, the learner can add and scale them, form a linear combination, and compute a dot product, saying what each result means geometrically.
• Given a vector in ${\mathbb{R}}^n$, the learner can compute its norm, produce the unit vector with the same direction, and decide which of two vectors is longer and whether they point the same way, treating length and direction as independent properties.
• Given a matrix and a vector, the learner can compute $Ax$ and decide whether a product is defined before forming it.
• Given $Ax$, the learner can express it as a linear combination of the columns of $A$ weighted by the entries of $x$, and use that reading to decide questions about which vectors $Ax$ can reach.
• Given a system in reduced form, the learner can determine whether it has no solution, exactly one, or infinitely many, justify the verdict from the pivot structure, and for the infinite case describe the solution set rather than one member of it.
• Given $Ax=b$ with explicit coefficients, the learner can apply row operations that preserve the solution set, reach echelon form without arithmetic error, and say why each operation leaves the solutions unchanged.
• Given a linear inequality and a point, the learner can determine whether the point satisfies it, lies on the bounding hyperplane, or violates it, and can state what the bounding hyperplane is for that inequality.

State what an optimization problem is asking

• Given a described decision situation in prose, the learner can state the decision variables, the objective and its direction, and the constraints, and can distinguish a decision variable from a quantity determined by the decisions.
• Given a decision problem described in words, the learner can define decision variables with meanings and units, write the objective with its direction, write one constraint per stated restriction, and state which described quantities are data rather than variables.
• Given a set of restrictions, the learner can determine whether the feasible set is empty, non-empty and bounded, or non-empty and unbounded, and can state that the classification does not depend on the objective function.
• Given a solved or solvable optimization problem, the learner can report the optimal solution and the optimal value as distinct objects, can state when the optimal set contains more than one point, and can recognize when no optimal solution exists.

Model a decision problem as a linear program

• Given a described resource-allocation or planning problem in prose, the learner can define decision variables with explicit units, write a linear objective, and write one linear constraint per stated restriction.
• Given a linear program written in scalars, the learner can assemble $A$, $b$ and $c$ with correct shapes and write the program as $min{c}^{\mathsf{T}}x$ subject to $Ax\le b$, $x\ge 0$; and given a program in matrix form, can recover a named constraint by its row and state what a named column contributes.
• Given a decision problem described in words, the learner can name its shape as covering, packing, allocation or a stated hybrid, justify the classification from the language of the description, state the direction of the objective and of the constraints that follow, and name the terminal outcome the shape makes most likely.
• Given a situation describing supply points, demand points and unit shipping costs, the learner can write the transportation model, test the balance condition and restore balance with a dummy row or column when it fails, read a plan in both the cost-table and network forms, and say what total unimodularity does and does not guarantee about the answer.
• Given a described planning or allocation situation, the learner can decide whether a linear program models it as stated, name the specific feature that disqualifies it when one is present, and identify the class of model the situation calls for instead.
• Given a linear program stated with any mix of maximization or minimization, inequality or equality constraints, and sign-restricted or free variables, the learner can produce an equivalent standard-form program with a minimization objective, equality constraints, and all variables nonnegative, without a conversion checklist in view.
• Given a described situation or a stated program, the learner can say which variables require integrality and which do not, classify the program as pure integer, mixed-integer or binary, describe the feasible set integrality produces, and state which results about linear programs cease to apply.
• Given a situation containing yes-or-no decisions and conditions relating them, the learner can define binary variables with stated meanings, write linear constraints expressing selection counts, implications and links between decisions and quantities, choose a defensible bound for a linking constraint, and verify that each constraint forbids what it is meant to forbid.
• Given a linear program whose variables carry sign restrictions other than simple nonnegativity, the learner can select and apply the appropriate substitution for each, carry it through the objective and every constraint, account for any constant it produces, and state how an original solution is recovered from the converted one.
• Given an integer program, the learner can form its linear relaxation, state the direction of the bound its optimum provides, use the bound to judge how far a candidate integer solution can be from optimal, draw the inferences an infeasible or integral relaxation licenses, and explain why rounding is not a solution method.

Read a linear program as a region and a direction

• Given one or more linear inequalities in two variables, the learner can draw each boundary line, determine which side the inequality allows by testing a point, and shade the set satisfying all of them together, including sign restrictions.
• Given a linear objective and a direction of optimisation, the learner can draw or describe the contour family, identify the coefficient vector as the direction of increase, decide whether a proposed direction improves the objective, and state which way a contour must be pushed.
• Given a feasible region described by inequality, equality and nonnegativity constraints together with a feasible point, the learner can determine which constraints are active there, count the independent ones among them, and state what that count implies about the point's position in the region.
• Given a standard-form constraint system and a proposed set of columns, the learner can decide whether the set is a basis, construct the corresponding basic solution by setting nonbasic variables to zero and solving the square system, and state separately whether the result is feasible.

Solve a linear program by hand

• Given a small linear program in two variables, the learner can determine whether its feasible region is empty, bounded, or unbounded, and justify the classification from the constraints rather than from the objective function.
• Given a linear program in two variables, the learner can identify the feasible region from its constraints, determine which vertex or edge the objective contour last touches, compute the exact optimal solution by solving the tight constraints, and state whether the optimum is unique.
• Given a standard-form minimization program and a basic feasible solution, the learner can select an entering variable from the reduced costs, apply the minimum ratio test to find the leaving variable and the step length, and report the resulting basis and basic feasible solution, without a tableau template.
• Given a minimization program in standard form and a specified basis, the learner can compute the reduced cost of each nonbasic variable and determine whether the corresponding basic feasible solution is optimal, without a formula sheet.
• Given a standard-form minimisation and a starting basis, the learner can build the initial tableau, carry out successive pivots correctly, decide at each iteration whether to continue, and on stopping state which terminal condition fired and read the answer the tableau reports.
• Given a standard-form minimisation and a basis, the learner can compute the basis inverse and basic values, form the multipliers, price nonbasic columns to find an entering variable, compute the direction and step, report the updated basis, and account for which quantities the method stores against those a full tableau would carry.

Reason about why the method works

• Given a linear system, the learner can state it in both pictures, say what each makes visible, and use whichever one answers the question at hand.
• Given a set of vectors or the columns of a matrix, the learner can decide whether they are linearly independent, state the rank, exhibit an explicit dependence relation when one exists, and say whether a given square matrix can serve as a basis.
• Given a standard-form program and a basis, the learner can partition the columns, solve for the basic variables, express the objective in the nonbasic variables alone, and read the basic solution, the objective value and the reduced costs off the result, stating whether the basis is optimal and why.
• Given a linear program in standard form and a candidate point, the learner can determine whether the point is a basic feasible solution and justify the determination by reference to feasibility and to the linear independence of the columns associated with its positive components.
• Given the characterization of extreme points as basic feasible solutions, the learner can bound the number of extreme points of a standard-form program in terms of its dimensions, justify that bound from the characterization, and evaluate whether finiteness alone makes enumeration a practical solution method.
• Given a standard-form system and two bases, the learner can decide whether they are adjacent, compute the edge direction generated by an entering variable, determine how far the step can go before feasibility fails, and explain why moving between adjacent corners changes exactly one basis column.
• Given a basic feasible solution, the learner can decide whether it is degenerate, explain the condition both as a count of positive components and as a surplus of active constraints, identify how many bases may describe the point, and state what degeneracy implies for a simplex iteration.

Judge an answer a program reports

• Given a linear program in any representation, its constraints and objective, a plotted region, a simplex tableau, or a solver report, the learner can determine which of the four terminal outcomes holds, name the evidence that decides it, and distinguish it from the outcome it is most often confused with.
• Given a model and a reported solution, a status, a point and an objective value, the learner can test primal feasibility against the original constraints, recompute the objective, judge whether the status is credible, and identify which class of fault a discrepancy indicates.
• Given a formulated linear program and a named solver, the learner can convert it into that tool's expected argument form, state what each array position means, invoke it, and translate the reported status, point and objective value back into the terms of the original model.