Skip to content

README.md

Latest commit

 

History

History
155 lines (122 loc) · 11.8 KB

README.md

File metadata and controls

155 lines (122 loc) · 11.8 KB
Raw

Example Optimization Code: course examples in Julia (JuMP) and Python

This folder holds worked examples from Laurent Lessard's Introduction to Optimization course (https://laurentlessard.com/teaching/524-intro-to-optimization/). The three Julia folders hold the course's JuMP scripts; the README.txt files in Julia 1 - 7 and Julia 8 - 16 say the code was converted from Julia 0.6 to Julia 1.10. The Python folder holds ports of many of the same examples, grouped into linear, convex, and nonconvex/combinatorial models, written with PuLP (and its bundled CBC solver), CVXPY and GEKKO. Each script stands alone: it builds one small model from data written in the file, solves it, and prints or plots the result. Author (git history): EricKellerRE (Julia folders, 2024); Philipellon (Python scripts, 2024; one ReadMe.txt edit in 2025); jsnodgrass2 (folder set-up commit, 2024).

Files

Julia 1 - 7: linear programs (Clp)

Folder note: Julia 1 - 7/README.txt

File What it does
Top Brass.jl Top Brass trophy LP (football and soccer trophies, wood and plaque limits); prints the plan.
Top Brass 2.jl Same model with dictionaries and @expression; prints profit, wood and plaques used.
Top Brass 3.jl Same model with a NamedArray recipe matrix over four ingredients.
Top Brass Trophy Problem (Ex 5-1 in Rardin'98).jl Primal LP with the constraint duals, then the explicit dual LP.
Building a house (Harvard Business Review, 1963) v1.jl Project scheduling LP: 24 tasks with precedence constraints; minimizes total duration.
Chebyshev Center.jl Meant as the Chebyshev-centre LP (largest ball inside a polyhedron); prints a centre and radius. The constraints are not written correctly; see Known issues.
Lumber Transportation Problem (J. Reeb and S. Leavengood).jl Transportation LP from 3 sites to 3 mills.
SailCo Problem.jl Four-month boat production and inventory LP.
Standard Form Conversion.jl Small LP (minimize p + q) used for the standard-form example.
Swim Relay Problem (Van Roy and Mason).jl Assignment LP of 5 swimmers to 4 strokes. The result is stored in assignment and not printed.

Julia 8 - 16: least squares, norms and regularization

Folder note: Julia 8 - 16/README.txt

File What it does
Hovercraft 1-D.jl 50-step hovercraft thrust problem (Gurobi): minimum-energy solution, then a second model with 1-norm and infinity-norm terms (case = :inf_one); bar plot of the thrust.
Hovercraft.jl 2-D hovercraft with four waypoints (Gurobi). Only the first waypoint is a constraint; the mismatch at all waypoints is weighted by λ in the objective. Plots the path and a Pareto curve over 30 values of λ.
Moving Average.jl Moving-average model fitted by least squares (backslash, no solver) to uy_data.csv; plots the fit and the error for window sizes 1-40.
Norm of 1-D Datasets.jl Fits one value to 9 random points under the 2-, 1- and infinity-norms (Gurobi); computes the mean, median and mid-range for comparison as bare expressions, which are not printed when the file is run as a script.
Polynomial Regression v0.jl Cubic least-squares fit to 9 points (Gurobi); plots points and curve.
Regression.jl Same cubic fit with Ipopt (prints the coefficients), then a second model meant as a norm-constrained fit. See Known issues.
Structural Optimization.jl Truss (bridge) design LP on a 15 x 7 node grid with one point load, solved with Ipopt; plots the members with nonzero area.
uy_data.csv 100 rows of (u, y) data for the moving-average examples; no header row.

Julia 17 - 25: integer programs

Folder note: Julia 17 - 25/README.txt

File What it does
ClothCo.jl Fixed-charge production MILP (shirts, shorts, pants) with Cbc.
Knapsack Problem.jl 0-1 knapsack written twice (literal coefficients, then data vectors), Cbc.
Uncapacitated Facility Location problem.jl 50 x 50 facility location MILP with Cbc, then a timing study with GLPK (binary x, continuous y) over sizes 5-50 and 50 random seeds; plots solve times and saves solver_comparison.pdf. Only the GLPK timings are filled in; the Cbc, Mosek and Gurobi series stay at zero.

Python

Folder note: Python/ReadMe.txt

Linear Programming (PuLP unless noted; folder note README):

File What it does
House.py House-building scheduling LP (port of the Julia example).
Millco.py Transportation LP from an incidence matrix (same data as the Julia lumber problem).
Sailco.py Boat production and inventory LP.
Standard Form.py Minimize p + q (standard-form example).
Top Brass Dual Minimal.py Top Brass primal LP; prints the plan when the status is optimal. No duals are computed.
Top Brass Dual Problem.py Dual LP of Top Brass (four λ variables).
Top_Brass3.py Prints the recipe data, then solves Top Brass with a recipe dictionary over four ingredients.
chebyshev center.py Chebyshev centre with CVXPY (default solver).
swim relay.py Swim relay assignment with binary variables; prints the assignment table with tabulate.

Convex Programming (folder note README):

File What it does
Data Norms.py Fits one value to 9 random points by minimizing the square of the sum of squares (CVXPY with Gurobi); prints the mean for comparison.
data Norms1.py 1-norm fit (CVXPY with Gurobi); prints the median.
data_norms2.py Infinity-norm fit to 9 fixed values (default CVXPY solver). See Known issues.
Regression1.py Plots the 9 regression data points only (no model).
moving_average1.py Plots the u and y series from uy_data.csv.
moving_average2.py Width-3 moving-average fit by least squares (numpy.linalg.lstsq); plots it and prints the error norm.
moving_average3.py Fit error for window sizes 1-40.
portfolio1.py Random data: one sample versus the average of 16 samples (plots only).
portfolio2.py Standard deviation and expected return per asset from folio_mean.csv and folio_cov.csv (plots).
portfolio3.py Correlation-matrix heat map of the same assets.
portfolio4.py Scatter of expected return against standard deviation.

Nonconvex and combinatorial models (the folder README is empty):

File What it does
ClothCo (1).py, clothco.py Fixed-charge clothing MILP (PuLP/CBC). The two files differ only by a final newline.
knapsack.py 0-1 knapsack (PuLP/CBC).
op1 (1).py Top Brass LP with variable bounds (PuLP).
op2.py Top Brass with integer variables (PuLP).
Standard Form.py Identical to Linear Programming/Standard Form.py.
SOS1.py Four variables bounded 0-5 with sum(x) <= 5 in place of an SOS1 constraint (an LP; no binary variables).
SOS2.py SOS2-style linking of x to weights z with sum(z) == 1. z is continuous, so this is the LP relaxation.
SOS3.py Binary indicators allow at most two nonzero x (the four indicators sum to 2).
QAP.py Quadratic assignment of 4 stores to 4 locations, linearized with binary product variables (PuLP/CBC).
TSP3.py 10-airport travelling salesman problem with Miller-Tucker-Zemlin subtour constraints (PuLP/CBC); prints tour length and tours.
Cutting Pipe.py Cutting-stock integer program (GEKKO, local solver): pieces of length 4, 5 and 6 from stock of length 19, demands 12, 15 and 22; minimizes stock pipes used. Prints only the solver log. See Known issues.
Tires1.py Nonlinear tyre-compound blend (rubber, oil, carbon) at minimum cost (GEKKO).
Tires2.py Two-variable version (oil, carbon) of the same blend problem (GEKKO).
polygon.py Largest-area hexagon inside the unit circle in polar coordinates (GEKKO); plots the shape.
polygon2.py Same problem in Cartesian coordinates with IPOPT (m.options.SOLVER = 3) from a random, unseeded start.
Navigation1.py Plots five beacons and the true position (no model).
Navigation2.py Contour plot of the range-measurement least-squares cost over a grid.
Navigation3.py 3-D surface and contour plot of the same cost.

Known issues

  • Python/Convex Programming/moving_average1.py, moving_average2.py and moving_average3.py read C:/Users/Owner/Downloads/uy_data.csv. Point them to Julia 8 - 16/uy_data.csv.
  • uy_data.csv has no header row. pd.read_csv and CSV.File both treat its first row as column names by default, so the first (u, y) pair is not used.
  • portfolio2.py, portfolio3.py and portfolio4.py read folio_mean.csv and folio_cov.csv, which are not in the repository.
  • Julia 8 - 16/Regression.jl uses uopt on line 34 before it is assigned (line 68), so running the whole file stops with an UndefVarError. The second model (line 64) applies normalize! to the residual vector; normalize! returns a unit vector, not the norm, so that model is not the intended norm constraint.
  • Julia 1 - 7/Chebyshev Center.jl writes its constraints as A[i,:]'.*x .+ r.*normalize!(A[i,:]) .<= b[i]. The element-wise product gives a 3 x 3 block of constraints per row, and normalize! returns a unit vector, not the norm, so the script does not solve the Chebyshev-centre LP. Python/Linear Programming/chebyshev center.py uses the standard form A[i, :] @ x + r * np.linalg.norm(A[i, :]) <= b[i].
  • Python/Nonconvex and combinatorial models/Cutting Pipe.py declares integer variables but keeps GEKKO's default solver setting, IPOPT (SOLVER = 3), which treats integer variables as continuous. Add m.options.SOLVER = 1 (APOPT) before m.solve for an integer solution. (GEKKO's local Linux build has no IPOPT and falls back to APOPT on its own.)
  • data_norms2.py prints (y[0] + (len(y) - 1))/2 as the comparison value; the mid-range is (y[0] + y[-1])/2.
  • The pip line in Python/ReadMe.txt separates names with commas and includes mpl_toolkits, which is not a PyPI package (it ships with matplotlib). Use the root requirements.txt instead.

Setup

  1. Python packages: from the repository root, pip install -r requirements.txt (see the root README).

  2. Julia packages used in each folder (install with Pkg.add):

    • Julia 1 - 7: JuMP, Clp, NamedArrays
    • Julia 8 - 16: JuMP, Gurobi, Ipopt, HiGHS, ECOS, SCS, NonlinearSolve, StaticArrays, CSV, DataFrames, PyPlot
    • Julia 17 - 25: JuMP, Cbc, GLPK, Ipopt, PyPlot

    LinearAlgebra, Random and Statistics are standard libraries. PyPlot.jl needs Python matplotlib through PyCall.

  3. Gurobi, installed and licensed, for Hovercraft 1-D.jl, Hovercraft.jl, Norm of 1-D Datasets.jl and Polynomial Regression v0.jl. Data Norms.py and data Norms1.py need only pip install gurobipy; its bundled size-limited licence covers these small models.

  4. Edit the pd.read_csv path in moving_average1-3.py, and put folio_mean.csv and folio_cov.csv in the working folder before running portfolio2-4.py.

Running

Run each script from its own folder. Julia:

cd "Example Optimization Code\Julia 17 - 25"
julia "Knapsack Problem.jl"

For scripts that plot with PyPlot, use the Julia REPL so the figures are shown:

julia> cd("Example Optimization Code/Julia 8 - 16")
julia> include("Moving Average.jl")

Python:

cd "Example Optimization Code\Python\Nonconvex and combinatorial models"
python TSP3.py

Inputs and outputs

  • Inputs: data written in each script, plus uy_data.csv (moving-average examples) and folio_mean.csv / folio_cov.csv (portfolio examples, not included).
  • Outputs: solutions printed to the console and matplotlib or PyPlot figures. Uncapacitated Facility Location problem.jl saves solver_comparison.pdf in the working folder. No other files are written.