Optimization Applications

Some applications of optimization using linear, binary, and integer programming, plus a couple of dynamic-programming problems. Each directory is a self-contained problem.

Contents

linear programs/

• zerosum.mod / zerosum.dat / zerosum.run — Solves a two-player zero-sum game (rock–paper–scissors) as a linear program. The LP finds the column player's optimal mixed strategy y by minimizing the game value v subject to v >= (payoff row r) · y for every row r and sum(y) = 1. By LP duality this is the minimax strategy. Reference: Vanderbei, Lecture 8.
• portfolio-matching.R — A mixed-integer program (via GLPK) that rebalances two investors' portfolios toward target allocations across 15 assets. Deviations from target are split into positive/negative slack variables that are penalized in the objective, binary variables select which assets are held, a cardinality constraint caps the number of positions, and "already invested" constraints pin existing holdings. Three target models are solved for each investor; the script also solves the LP relaxation to produce duals and sensitivity analysis.

mixed integer programs/

• warehouse_planning.mod / warehouse_planning.run — A facility-location problem: choose which of 6 candidate warehouses to build to serve 10 stores, minimizing construction cost plus five-year supply cost, with each store assigned to exactly one open warehouse. Formulated as a binary program with quadratic (product-of-binaries) terms: b_i opens warehouse i, b_ij assigns store j to warehouse i, and the constraints sum_i b_i * b_ij = 1 force each store to be served by exactly one open warehouse.

dynamic programming/

• machine_replacement.cs — Backward-induction DP for the classic machine replacement problem: over 7 stages, given a machine of age 0–3, decide each period whether to keep paying (age-dependent) maintenance or to trade the machine in and buy a new one. Prints the full cost-to-go table.
• ProjectChoice.cs — Memoized DP for a sequential investment problem (a repeated secretary-problem variant): over 36 monthly stages, decide whether to commit to each project as it arrives, targeting a portfolio of 14–16 investments with maximal average anticipated return, with a 4% penalty per project short of 14. The state is (stage, number of projects taken, average return so far, current project's return).

Running

AMPL models (.mod / .run)

Requires AMPL with the CPLEX solver (or edit option solver in the .run file to any solver you have):

cd "linear programs"        && ampl zerosum.run
cd "mixed integer programs" && ampl warehouse_planning.run

Note: warehouse_planning.mod has products of binary variables, so it needs a solver that accepts quadratic/binary-product terms (e.g. CPLEX).

R (portfolio-matching.R)

Requires R with the dplyr and glpkAPI packages (glpkAPI needs the GLPK library installed):

cd "linear programs" && Rscript portfolio-matching.R

Solution and sensitivity-analysis files are written to the working directory.

C# (dynamic programming/)

Each .cs file is a standalone program with its own Main, so compile/run them one at a time, e.g. with the .NET SDK:

cd "dynamic programming"
mkdir machine-replacement && cd machine-replacement
dotnet new console
cp ../machine_replacement.cs Program.cs
dotnet run

(or paste a file into any C# scratchpad such as dotnetfiddle.net).