I previously wrote about a Hybrid AI system that combined logical and optimization methods of problem solving to identify the best solution to an employee shift assignment problem. This implementation was notable in that a hybrid approach was used so that the optimal solution could be found, but the system could still indicate to the users why a particular assignment was, or wasn’t, included in the results. 

I recently published to GitHub a demo of a similar system. I use this demo in my presentation, Building AI Solutions that can Reason Why. The code demonstrates the hybridization of multiple AI techniques by creating a solution that iteratively applies a combinatorial optimization engine. Different results are obtained by varying the methods of applying the constraints in that model. In the final (4th) demo  method, an iterative process is used to identify what the shortcomings of the final product are, and why they are necessary.

These demos use the Conference Scheduler AI project to build a valid schedule.

There are 4 examples, each of which reside in a separate test method:

ScheduleWithNoRestrictions()

The 1st method in BasicExamplesDemo.cs shows an unconstrained model where only the hardest of constraints are excluded. That is, the only features of the schedule that are considered by the scheduler are those that are absolute must-haves.  Since there are fewer hard constraints, it is relatively easy to satisfy all the requirements of this model.

ScheduleWithHardConstraints()

The 2nd method in BasicExamplesDemo.cs shows a fully constrained model where  all constraints are considered must-haves. That is, the only schedules that will be considered for our conference are those that meet all of the scheduling criteria. As you might imagine, this can be difficult to do, in this case resulting in No Feasible Solution being found. Because we use a combinatorial optimization model, the system gives us no clues as to  which of the constraints cause the infeasibility, or what to do that might allow it to find a solution.

ScheduleWithTimePreferencesAsAnOptimization()

The 3rd method in BasicExamplesDemo.cs shows the solution when the true must-haves are considered hard constraints but preferences are not. The AI attempts to optimize the solution by satisfying as many of the soft constraints (preferences) as possible. This results in an imperfect, but possibly best case schedule, but one where we have little insight as to what preferences were not satisfied, and almost no insight as to why.

AddConstraintsDemo()

The final demo, and the only method in AddConstraintsDemo.cs, builds on the 3rd demo, where the true must-haves are considered hard constraints but preferences are not. Here however, instead of attempting to optimize the soft constraints, the AI iteratively adds the preferences as hard constraints, one at a time, re-executing the solution after each to make sure the problem has not become infeasible. If the solution has become infeasible, that fact is recorded along with what was being attempted. Then that constraint is removed and the process continues with the remaining constraints. This Hybrid process still results in an imperfect, but best-case schedule. This time however, we not only know what preferences could not be satisfied, we have a good idea as to why.

The Hybrid Process

The process of iteratively executing the optimization, adding constraints one at a time, is show in the diagram below.  It is important to remember that the order in which these constraints are added here is critical since constraining the solution in one way may limit the feasibility of the solution for future constraints.  Great care must be taken in selecting the order that constraints are added in order to obtain the best possible solution.

 

Hybrid Conference Optimization Process

The steps are as follows:

  1. Make sure we can solve the problem without any of the soft constraints.  If the problem doesn’t have any feasible solutions at the start of the process, we are certainly not going to find any by adding constraints.
  2. Add a constraint to the solution. Do so by selecting the next most important constraint in order.  In the case of our conference schedule, we are adding in speaker preferences for when they speak. These preferences are being added in the order that they were requested (first-come first-served).
  3. Verify that there is still at least 1 feasible solution to the problem after the constraint is added.  If no feasible solutions can be found:
    1. Remove the constraint.
    2. Record the details of the constraint.
    3. Record the current state of the model.
  4. Repeat steps 2 & 3 until all constraints have been tried.
  5. Publish the solution
    1. The resulting schedule
    2. The constraints that could not be added.  This tells us what preferences could not be accommodated.
    3. The state of the model at the time the failed constraints were tried.  This give us insight as to why the constraints could not be satisfied.

Note: The sample data in these demos is very loosely based on SoCalCodeCamp San Diego from the summer of 2017. While some of the presenters names and presentations come roughly from the publicly available schedule, pretty much everything else has been fictionalized to make for a compelling demo, including the appearances by some Microsoft rock stars, and the "requests" of the various presenters.

If you have any questions about this code, or about how Hybrid AIs can be used to provide more information about the solutions to problems than strictly optimization or probabilistic models, please contact me on Twitter.

Tags: , , , , , , | Categories: Event Posted by bsstahl on 10/6/2016 6:20 AM | Comments (0)

The next two months are packed with tons of great technical events that I am really looking forward to.  Below are some of the events that I am involved with and will be attending between now and the end of November. I hope to run into you at these events.  If you see me, please don’t hesitate to say “hi”. I do love to talk tech.

Desert Code Camp – Phoenix AZ – October 8th 2016

Desert Code Camp makes its triumphant return from hiatus this weekend at Chandler-Gilbert Community College in the south-east valley.  I will be delivering my talk, “A Developer’s Guide to Finding Optimal Solutions” which is an introduction to combinatorial optimization designed specifically for software developers, at 9:45 am in room CHO-110.

IT/DevConnections – Las Vegas NV– October 10th-13th 2016

One of my favorite large conferences of the year is IT/DevConnections in Las Vegas.  This year marks my 4th attendance at this event, the 2nd as a speaker. I will be delivering the talk, “Dynamic Optimization – One Algorithm All Programmers Should Know”, a programmer’s introduction to Dynamic Programming, at 2:15 pm on October 13th in Brislecone 2 at the Aria Resort.

Atlanta Code Camp – Atlanta GA – October 15th 2016

This year marks my 2nd attendance at the Atlanta Code Camp.  My 1st experience there, last year when I presented on Dynamic Programming, was a big part of the inspiration for drilling deeper into the topic of combinatorial optimization. As such, I return to Atlanta this year with my new talk on the subject, “A Developer’s Guide to Finding Optimal Solutions”.

NWVDNUG & SEVDNUG – Phoenix AZ – Oct 26th and 27th

It is not yet confirmed as of this publication but I have a really great, internationally renown speaker lined-up for the Northwest Valley and Southeast Valley .NET User Groups this month.  Final arrangements are currently being made so keep an eye on meetup.com for each group for the details to be published as soon as they are finalized.

SoCalCodeCamp – Los Angeles CA, November 12th – 13th 2016

I have attended many instances of the Southern California Code camp, but this will only be my 2nd time at the Los Angeles incarnation of this event.  My 1st time there, last year, I was struck by the old-school beauty of the old school campus and facilities at USC when I presented my talk on Dynamic Programming.  This year, I will follow that up with my new, more general overview on the subject of finding optimal solutions.

NWVDNUG & SEVDNUG – Phoenix AZ – Nov 16th and 17th

Our good friend Jeremy Clark (blog, twitter) makes his annual tour of the Valley’s .NET User Groups to talk to us, once again, about many of the things you need to know about .NET and Software Engineering to make your development better. Jeremy will give a different talk each night so be sure to sign-up at the meetup sites and come to both meetings.

Tags: , | Categories: Event Posted by bsstahl on 10/26/2008 8:51 PM | Comments (0)

Next week I will be attending the Microsoft Professional Developer's Conference in Los Angeles. This will be my 6th PDC (of, I believe, 10).  I will be attempting, as I have done in the past, to blog each session that I attend, as well as other events and functions at the PDC. I will also be updating my status on Twitter (http://www.twitter.com/bsstahl) on a regular basis.

My current schedule looks like this:

Sunday, Nov. 26th:

  • 1:40 PM - US Flight 29 PHX-LAX Arrives 3:08 PM PDT
  • Hotel Check-in
  • Conference Registration

Monday, Oct 27th:

  • 8:30 AM - Keynote Address with Ray Ozzie, Amitabh Srivastava, Bob Muglia & David Thompson
  • 11:00 AM - 1 of the following sessions:
    • Microsoft Visual Studio Team System: A Lap Around VSTS 2010 with Cameron Skinner
    • A Lap around Cloud Services Part 1 with Manuvir Das
  • 12:45 PM - 1 of the following sessions:
    • Microsoft Visual C# IDE: Tips and Tricks with Dustin Campbell
    • Microsoft Expression Blend: Tips & Tricks with Peter Blois & Douglas Olson
  • 1:45 PM - The Future of C# with Anders Hejlsberg
  • 3:30 PM - 1 of the following sessions:
    • Microsoft Silverlight, WPF and the Microsoft .NET Framework: Sharing Skills and Code with Ian Ellison-Taylor
    • A Lap around Cloud Services Part 2 with John Shewchuk
  • 5:15 PM - 1 of the following sessions:
    • Framework Design Guidelines with Brad Abrams & Krzysztof Cwalina
    • Microsoft .NET Framework: Overview and Applications for Babies with Scott Hanselman
    • Agile Development with Microsoft Visual Studio with Lori Lamkin & Sunder Raman
    • IronRuby: The Right Language for the Right Job with John Lam

Tuesday, Oct 28th:

  • 8:30 AM - Keynote Address with Ray Ozzie, Steven Sinofsky, Scott Guthrie & David Treadwell
  • 11:00 AM - Keynote Address with Chris Anderson & Don Box
  • 12:00 PM - AZ PDC Lunch Meet-Up at the Microsoft Store
  • 12:45 PM - 1 of the following sessions:
    • Building Search-Driven Portals with Microsoft Office SharePoint Server 2007 and Microsoft Silverlight with Stein Danielsen & Jan Helge Sageflat
    • Windows Presentation Foundation Animation, YouTube, iTunes, Twitter, and Nintendo's Wiimote with Dan Fernandez, Scott Hanselman, Brian Peek & Clint Rutkas
    • Visual Studio Debugger Tips & Tricks with John Cunningham
  • 1:45 PM - 1 of the following sessions:
    • Developing Applications Using Data Services with Mike Flasko
    • A Lap around the Live Framework and Mesh Services with Ori Amiga
    • Project "Velocity": A First Look with Murali Krishnaprasad
    • A Lap around "Oslo" with Douglas Purdy & Vijaye Raji
  • 3:30 PM - 1 of the following sessions:
    • Microsoft Silverlight Futures: Building Business Focused Applications with Jamie Cool
    • Microsoft Silverlight 2 for Mobile: Developing for Mobile Devices with Amit Chopra & Giorgio Sardo
    • Live Services: Making your Application More Social with Angus Logan
  • 5:15 PM - 1 of the following sessions:
    • Entity Framework Futures with Tim Mallalieu
    • Developing Connected Home Applications and Services for Windows Home Server with CJ Saretto & Fabian Uhse
    • Live Services: Building Applications with the Live Framework with Raymond Endres
  • 7:00 PM - Attendee party at Universal Studios

Wednesday, Oct 29th:

  • 8:30 AM - Keynote
  • 10:30 AM - 1 of the following sessions:
    • Live Services: Live Framework Programming Model Architecture and Insights with Dharma Shukla
    • Exposing Connected Home Services to the Internet via Windows Home Server with Brendan Grant & CJ Saretto
    • Panel: The Future of Programming Languages with Gilad Bracha, Douglas Crockford, Anders Hejlsberg, Erik Meijer, Wolfram Schulte & Jeremy Siek
  • 12:00 PM - Silverlight Controls Roadmap with Shawn Burke
  • 1:15 PM - 1 of the following sessions:
    • SQL Server 2008: New and Future T-SQL Programmability with Michael Wang
    • Improving .NET Application Performance and Scalability with Steve Carroll & Ed Glas
  • 3:00 PM - 1 of the following sessions:
    • Live Services: Mesh Services Architecture and Concepts with Abolade Gbadegesin
    • "Dublin": Hosting and Managing Workflows and Services in Windows Application Server with Dan Eshner
    • Offline-Enabled Data Services and Desktop Applications with Pablo Castro
  • 4:45 PM - Live Services: Building Mesh-Enabled Web Applications Using the Live Framework with Arash Ghanaie-Sichanie
  • 6:00 PM - Ask-the-Experts

Thursday, Oct 30th:

  • 8:30 AM - 1 of the following sessions:
    • SharePoint 2007: Creating SharePoint Applications using Visual Studio 2008 with Chris Johnson
    • Microsoft Visual Studio Team System Team Foundation Server: How We Use It at Microsoft with Stephanie Saad
    • Research: Contract Checking and Automated Test Generation using Pex with Mike Barnett & Nikolai Tillmann
  • 10:15 AM - 1 of the following sessions:
    • Live Services: The Future of the Device Mesh with Jeremy Mazner
    • Microsoft Silverlight 2: Control Model with Karen Corby
  • 12:00 PM - 1 of the following sessions:
    • Live Services: Notifications, Awareness, and Communications with John Macintyre
    • Services Symposium: Cloud or No Cloud, the Laws of Physics Still Apply with Gianpaolo Carraro
  • 1:45 PM - An Introduction to Microsoft F# with Luca Bolognese
  • 4:20 PM - US Flight 152 LAX-PHX Arrives 5:40 PM MST
  • 6:00 PM - Collapse in an exhausted heap on my bed

All of this, of course, is subject to significant change...