CO 370 - Deterministic Operations Research Models

Info

Final

Thursday December 19th at 7:30pm (evening), DC 1351.

Practice final. For some questions, several variants are given to provide additional practice (for example, Question 3 has variants 3.1, 3.2, 3.3 and 3.4). Aside from that, the final exam will have the same length and structure as the practice final.

Midterm

Tuesday October 29th at 10am, AL 113: solutions.

Practice problems

Assignments

Lectures:

Course structure:

1. Linear optimization
   • Definition and simple models
   • Example 1: Chemical equation
   • Example 2: Blending problem
   • Example 3: Multiperiod investment problem
   • Max s-t flow problem
     • Refresher: directed graphs
     • Max s-t flow problem statement and formulation
     • Integer solutions property
     • Bipartite matchings
   • Min-cost flow problem
     • Min-cost flow problem statement and formulation
     • Application example: transshipment problem
     • Integer solutions property
     • Application example: Bus scheduling
2. Integer optimization
   • Example 1: knapsack problem
   • Example 2: bin packing problem
   • IP modeling tricks (part I)
   • Example 3: Sports scheduling problem
   • IP modeling tricks (part II)
     • Discrete-valued variables
     • Piecewise-linear functions
     • Union of polyhedra
3. Solving LPs
   1. Standard equality form
   2. Finding a solution to Ax = b
   3. Solving min {c^Tx : Ax = b, x ≥ 0}
      • Definitions (basis)
      • Theorem: Existence of optimal basic feasible solutions
      • Theorem: Basic feasible solutions correspond to vertices
      • Naive algorithm for LP
      • Observations (O1, O2, O3)
      • Simplex tableau
      • Pivots
      • Simplex method
   4. Duality
   5. Bases and duality
   6. Sensitivity analysis
      • Changes to right-hand sides
      • Changes to costs
      • Changes to coefficients
   7. Dual simplex method
4. Solving IPs
   • Branching
   • Branch and bound
   • Totally unimodular matrices
     • Theorem 1 (Laplace expansion)
     • Theorem 2 (Cramer’s rule)
     • Theorem 3 (Square linear systems with unimodular matrices)
     • Theorem 4 (SEF with unimodular m × m submatrices)
     • Theorem 5 (Operations that preserve total unimodularity)
     • Theorem 6 (LPs in inequality form with a TU matrix)
     • Theorem 7 (Special class of TU matrices: at most one +1/-1 per column)
     • Theorem 8 (Min-cost flow formulation has a TU matrix)
     • Theorem 9 (Max flow formulation has a TU matrix)
5. Other types of problems
   • Satisfiability (SAT)
     • Definitions (Boolean variable, Boolean formula, assignment, (un)satisfiable formula, SAT problem)
     • Example (wedding dinner)
     • Boolean reformulations (Boolean identities)
     • Conjunctive normal form (CNF)
     • Backtracking
     • Reformulating a SAT problem as an IP
     • Variants of SAT: constraint programming (CP), satisfiability modulo theories (SMT)
   • Nonlinear optimization
     • Black-box / oracle model
     • Definitions (global and local minimizers, gradient)
     • Gradient descent
   • Application: Classification / labeling problem
     • Problem statement
     • Neural network (NN) approach
     • Training a neural network
     • Cost function
     • Differentiation
     • Efficient training of a neural network (differentiation for layered NN, stochastic gradient descent, learning rate)

Installing Julia

Here are a few pointers to help you get started with Julia.

First, you need to download and install Julia. I use the current stable release (v1.2.0). You should preferably get the 64-bit version for your operating system (Windows, MacOS or Linux).

Once Julia is installed, you need the JuMP package, which provides the mathematical programming facilities in the Julia language. Execute Julia, and from the Julia command line, run the following commands:

import Pkg
Pkg.add("JuMP")
Pkg.add("Cbc")

Note that these commands will download packages from the internet and compile them, which will take several minutes. Moreover, Julia will also be slow the first time you use the JuMP package, but it should get faster after that.

See the JuMP documentation for more details on the installation process.

In most cases, it is easier to write models in a file rather than type them line-by-line into the Julia command line. In class, I am using the Atom editor, with the Juno development environment. You can find directions on how to install them here. However, any text editor will do just fine.

Learning Julia

In class, we start most implementations from an empty model, which you can download here, then we fill in the gaps. When it is ready, we try the model by running:

include("model-empty.jl")

where “model-empty.jl” is replaced by the name we are giving to our current model. For most problems, the examples covered in class should be enough to show you how to write your own models. However, in case of necessity, you are encouraged to consult the JuMP documentation. If you are using more advanced features of the Julia language itself, its documentation can be found here.