1. Liquid Victor : Media tracking and aggregation [used to assemble this presentation]
2. Prehensile Pony-Tail : A static site generator built in c#
3. TestHelperExtensions : A set of extension methods helpful when building unit tests
4. Conference Scheduler : A conference schedule optimizer
5. IntentBot : A microservices framework for creating conversational bots on top of Bot Framework
6. LiquidNun : Library of abstractions and implementations for loosely-coupled applications
7. Toastmasters Agenda : A c# library and website for generating agenda's for Toastmasters meetings
8. ProtoBuf Data Mapper : A c# library for mapping and transforming ProtoBuf messages

• Find the best values for a set of decision variables that
  • Satisfies all constraints

• Find the best values for a set of decision variables that​
  • Satisfies all constraints
  • Maximizes the features we want​
  • Minimizes the features we don’t want

• Feasible Solutions
  • 7 Mixed Fruit
  • 1 Mixed Fruit , 2 Hot Wings, 1 Sampler Plate
• Possible Optimizations
  • Minimize # of any single item
  • Maximize total # of distinct items
• Possible Relaxation
  • Offer discount to relax constraint
  • Convert = to >= resulting in more feasible solutions
  • Maximize Profit

• As an entity, constraints do 2 things

  • Verify feasibility (is there a solution that satisfies this constraint?)
  • Prune the search space (more on this coming up)

• Infeasibility

  • Solution does not satisfy 1 or more constraints
    • Previous decisions that led to this point may need to be revisited
  • Problem has no feasible solutions
    • Relaxations may be available to find a “good-enough” solution

• Inequality Constraints
  • \(X_1 <> 4.5\) or \(X_1 + 4X_2 < 24.0\)
• Integer Constraints
  • Counter-intuitively, they can be harder to find solutions for
  • \(X_1 + 4X_2 < 24 \quad\text{with}\quad X_1, X_2 \in \{1,\dots,n\}\)
• Global Constraints
  • Special “pre-defined” constraints that have a polynomial-time algorithm
    • i.e. AllDifferent Constraint
  • There are more than 400 Global Constraints known today
  • Defining these constraints using polynomial algorithms is an active research area

• Objective Function

  • Equation describing how to improve a solution
  • Specify what to minimize or maximize to produce the best result

• Specified as a goal relative to an equation

  • \(\max 3X_1 + 9X_2 \text { subject to } c_n\)
  • \(\min \sum_{i=1}^{n} A_i X_i\)

• One objective per Model

  • Combine features by creating a "score"

• Constraint Programming is about narrowing choices

  • Model the valid states of the problem
    • Variables, domains, and required conditions
  • Let constraints prune impossible choices
    • Every new constraint removes possible solutions
  • Search what remains until a feasible answer is found

• LP and MIP build on the same idea

  • Constraints still define the feasible region
  • An objective chooses the best feasible answer
  • Linear structure gives us specialized algorithms

• Clay Constraint
  • X + 4Y <= 24 ​
    • X <= 24 and Y <= 6​
• Glaze Constraint
  • X + 2Y <= 16​
    • X <=16 and Y <= 8

• \(X_{t,r}\)
  • \(t\) is the id of the timeslot
  • \(r\) is the id of the room
  • \(X_{t,r} \in \mathbb{Z}\) is the session id assigned to timeslot \(t\) in room \(r\)
    • \(\mathbb{Z}\) is the set of all session ids

• Each room/timeslot combination can have no more than 1 session
• Each session must be scheduled exactly once
• What if session 7 & 9 are the same speaker?
  • Desired rule: \(slot(7) \ne slot(9)\)
  • But \(X_{t,r}\) stores a session id, not a timeslot for a session
  • This requires a lookup: "where is session 7 scheduled?"
  • That lookup is not naturally a linear expression

• \(X_{t,r,s}\)
  • \(t\) is the id of the timeslot
  • \(r\) is the id of the room
  • \(s\) is the id of the session
  • \(X_{t,r,s}\) is \(1\) if \(s\) is the session id assigned to timeslot \(t\) in room \(r\)

• Each session must be scheduled exactly once
  • \(\sum_t \sum_r X_{t,r,s} = 1 \quad \forall s\)
• Each room/timeslot combination can have no more than 1 session
  • \(\sum_s X_{t,r,s} \le 1 \quad \forall t,r\)
• Sessions 7 and 9 cannot be scheduled in the same timeslot
  • \(\sum_r X_{t,r,7} + \sum_r X_{t,r,9} \le 1 \quad \forall t\)

Create a score that improves with the desirability of the solution

• Factors might include
  • Reduce # of different rooms in a track
  • Reduce the # of timeslot conflicts between sessions in a track
  • Reduce total steps between sessions of a track
  • Reduce distance (time & room) between multi-part sessions
  • Reduce # of different days a speaker speaks

Maximize # of sessions in the same room with Sessions 2 & 4 (a track)

• For each Room:
  • \(\max \sum_r \left(\sum_t X_{t,r,2}\right)\left(\sum_t X_{t,r,4}\right)\)
    • If they are in the same room, the total will be 1
    • If they are in different room, the total will be 0

We don't need to implement Simplex ourselves

• A solver takes the model:
  • Decision variables
  • Constraints
  • Objective function
• Chooses the algorithms needed
• Searches for the best solution
• Examples:
  • Gurobi - Commercial, high-performance optimization solver
  • Google OR-Tools - Open-source optimization toolkit
  • Others from Wikipedia's list of optimization software

• Variable Definitions

  • \(x_S\) – Number of small vases to create
  • \(x_L\) – Number of large vases to create

• Implementation

  • var xS = solver.MakeIntVar(0.0, maxSmall, "xS");
  • var xL = solver.MakeIntVar(0.0, maxLarge, "xL");

• Clay Constraint Definition

  • \(x_S + 4 x_L \ge 0\)
  • \(x_S + 4 x_L \le claySupply\)

• Similar for Glaze Constraint

• Implementation

  • var cClay = solver.MakeConstraint(0.0, claySupply);
  • cClay.SetCoefficient($x_S$, 1);
  • cClay.SetCoefficient($x_L$, 4);

\(\max \; 3 x_S + 9 x_L\)

• var obj = solver.Objective();
• obj.SetCoefficient($x_S$, 3);
• obj.SetCoefficient($x_L$, 9);
• obj.SetMaximization();

• int resultStatus = solver.Solve();
• var xSmall = xS.SolutionValue();
• var xLarge = xL.SolutionValue();