In a session today at 2:00 pm in room 132B of the North Building of the Convention Center, several members will discuss how you can organize a Train the Trainers session for high school mathematics teachers. This session is based on the very successful program that Ken Chelst has run for several years. In this session, you will learn about the process for organizing a workshop for high school mathematics teachers on integrating operations research into their curricula. We will discuss the process and strategies, and we will present an abbreviated version of an active learning oriented linear programming module (and participants will have an opportunity to play with Legos!) that has been used in these workshops. I hope to see many of you their and at the general reception tonight at the Arizona Science Center.
• Michael Mark, Ecole Polytechnique F´ed´erale de Lausanne
By Zulqarnain Haider
The third joint session about the recent developments on the wild frontier between machine learning and discrete optimization was as engaging and promising as the previous two sessions. Session chair Alfredo Torrico kick started the session by inviting the first speaker, Matthew Staib of MIT, to talk about his work on distributionally robust submodular maximization. The speaker started with defining submodularity and the wide-ranging applications in combinatorial optimization, graph theory, and data mining. The talk was focused on efficient algorithms that use distributionally robust optimization (DRO) to better generalize the underlying submodular function f. The empirical results showed that DRO improves generalization to the unknown stochastic submodular function.
The second speaker, Sebastien Martin of MIT, gave a talk titled “The Benefits of Stochastic Proximal Steps.” He compared the performance of proximal point algorithm with its more famous cousin, the stochastic gradient algorithm, to solve the basic convex optimization problems. The talk emphasized that under certain conditions, proximal point algorithm can outperform the stochastic gradient algorithm. The performance of two algorithms with different minibatch sizes and proximal step approximations was compared for 1D convex quadratic optimization problem and the ordinary least squares.
The third speaker of the session was Adrian Rivera from Georgia Tech who started his talk by introducing the online convex optimization (OCO) and online saddle point (OSP) problem. He showed that the standard algorithm for OCO problem with one player fails to solve the OSP problem where two players engage in convex-concave games. He presented an algorithm that finds near-optimal bounds for OSP problems. He concluded by introducing the constrained version of the OCO problem with knapsack constraints and relating it to the OSP problem and the algorithm presented.
The fourth and final speaker of the session was Elias B. Khalil from Georgia Tech who talked about his work in learning combinatorial optimization algorithms over graphs. He introduced a realistic setting where one may need to repeatedly solve the same combinatorial graph problem with slightly different data sets. He used examples of minimum vertex cover problem, max cut problem and the travelling salesman problem. The current greedy algorithms, he emphasized, cannot exploit the distribution of problem instances and there is a need to learn better greedy heuristics. He proposed a framework based on reinforcement learning and graph embedding to address this challenge. In conclusion, he showed that the results of his approach compare favorably with standard greedy heuristics for well known graph problems.
What is Sagarmala?
Sagarmala (the ocean’s garland) is arguably the largest transport and logistics project ever undertaken in India since its political independence in 1947. Sagarmala opens up a huge opportunity for Operations Researchers, AI, and data scientists in India and around the world to bring their expertise into play and do something to positively impact the lives of 1.2 Billion people! Last year, we took a look at optimizing India’s railways, and this time, we briefly study one flower in the ocean’s garland – India’s inland waterways.
The single biggest news item that came out of India this week was this announcement by the Ministry of Shipping.
This should have been the biggest news of the week in India. For the first time since independence, a container is moving on inland vessel. PepsiCo is moving 16 containers from Kolkata to Varanasi on vessel MV RN Tagore, over river Ganga. Such a huge accomplishment!#SagarMala
— Nitin Gadkari (@nitin_gadkari) November 3, 2018
Take a look at India’s national waterways here. The picture of National Waterway #1 below shows the path to be traversed by the merchant vessel – from the timeless city of Varanasi (Kashi) to the historic city of Kolkata along the river Ganga.
Optimizing in harmony with Rta (the cosmic order)
Ganga! The name evokes respect among the Indians first and foremost. She is our Ganga Maiyya – Mother Ganga. She is part of the world’s longest poem, the Mahabharata. She is part of our sacred geography as the river is a manifestation of the divine Ganga Devi. Quite naturally, all Indians are concerned about the increasing pollution due to the toxic industrial discharge into this most sacred of waters over the last few decades. Therefore, the environmental impact of any proposed waterway through Ganga is a primary concern. Ganga flows in sync with Rta – its water levels follow the natural cycle, rising with the Monsoon rains and ebbing in winter. Navigation is challenging. The barge sizes that are feasible for travel and transportation can vary by time of year and the location, resulting in a time-and-space network. How can we ease these navigability limitations while also minimizing the environmental impact on this river and protecting its aquatic bio-diversity? A practical way to accomplish this task is not unrestrained optimization that is unsustainable, but to optimize in harmony with Rta and nature. As this World Bank Report says:
“…. the Inland Waterways Authority of India (IWAI) has sought to adopt the least intrusive methods of making the river navigable. It has therefore followed the principle of ‘working with nature’ while planning the Ganga waterway…. . Even this limited dredging will only be done when absolutely necessary and then too using modern, less intrusive technologies.”
The cost-benefit numbers have always been clear, but when nature is the most important stakeholder in the project, it requires time and great care. And hey, if real life optimization was easy, then why would we need smart Operations researchers?
The types of multi-commodity optimization problems to be solved are interesting. This supply-chain study reports that the transportation cost per metric-ton-kilometer through inland waterways is significantly lower than that possible through the rail or road mode. It is also relatively energy efficient, consuming less fuel to do the same work. Every barge through a waterway gets many trucks off the road, decongesting India’s over-stressed road network. Certain hazardous materials can be better transported through waterways, avoiding the risky drive through densely populated areas. Routing, Supply chain management, transportation, flow optimization, multi-modal network design, facility location – you name it, they are all there.
These are large-scale analytical problems and the motivation is huge. Any incremental improvement will have a significant economic and social impact.
— Ministry of Shipping (@shipmin_india) November 3, 2018
India currently has one of the highest logistics costs in the world. More than half-of-a-decade of Soviet-style planning blindly embraced by India’s Congress party nearly bankrupted the world’s largest democracy, left the infrastructure in tatters, and millions in acute poverty. Sagarmala is one attempt to rebuild key logistical and transportation infrastructure. After the Congress party was finally voted out in 2014, India’s current Prime Minister Narendra Modi realized that India literally had to start from scratch. Literally reboot. While thinking of inland waterways, he also had to come up with the world’s largest health-insurance scheme, activate the world’s biggest digital ID project, and spearhead the world’s largest toilet building spree that will improve basic sanitation and save hundreds of thousands of lives in rural India.
I have highlighted just some of the many important problems being solved in this part of the world. When the fate of such a large proportion of the world’s humanity is at stake, ideology has to take a back seat; Science and Sacred must unite to optimize decision making in harmony with Rta.
Have you ever attended a talk expecting it was going to be about something and it ends up being about something else? Well, this happened to me yesterday. Probably my fault for not reading the abstract in detail. I decided to stay anyway to see if I could learn something. Lo and behold, I did! In fact I felt a little ignorant for not having seen or thought of that before. It was referred to by the speaker as “The Lambda Question” (not sure if this is the standard name). Say you want to optimize this function:
minimize f(x)/g(x), such that x belongs to X
You can transform this problem into a feasibility problem (like Constraint Programmers do) by asking the question: for a given lambda, is there an x for which
f(x)/g(x) < lambda ?
The question above can be answered by looking for an x that satisfies
f(x) – lambda * g(x) < 0.
If you have an efficient procedure for finding such x, you can then do binary search on lambda to solve the original minimization problem. Neat little trick!
The second topic of this post is interpretability. This year, I decided to attend as many talks/tutorials about machine learning (ML) as possible. I may be a bit late for the party, but I’m interested in the combination of ML and optimization. Therefore, I figured the first step is to learn the terminology, the algorithms, and their weaknesses. I’m taking a Data Mining class at the University of Miami, which has already taught me a good deal, and I came to Phoenix determined to expand my knowledge.
I was speaking with a friend about the issue of interpretability and this anecdote came up: a neural network model was built to help doctors predict a certain outcome and the doctors refused to use it because they did not know how the prediction was obtained and couldn’t interpret the neural net’s reasoning. This led to the creation of a decision tree model for the problem, which the doctors were much more amenable to because they could literally “see” what was going on. I believe almost everyone has heard some version of this story by now. Nevertheless, the interesting take on this idea of interpretability came up during a conversation I was having with frieds last night at dinner. It started with a comment from my friend David Bergman that went more or less like this “Sure, neural nets are not interpretable, but neither are MIPs and I don’t see anyone complaining about that.”
This statement generated a very lively conversation at the table. Are these two kinds of un-interpretability the same? My first reaction was that they are not. When a MIP solver stops and gives you the answer, it doesn’t show you “why” that is the answer, but you can go back and check that the answer satisfies all the constraints and be confident that it is feasible (typically; if you ignore the delicate cases of tiny constraint violations). The bounding mechanism of branch-and-bound is what gives you the quality quarantee. On the other hand, when a (shallow/deep) neural net outputs a recommendation, there’s some degree of uncertainty there. The counter-argument was that you could trace back the path of activated neurons and see “why” that was the answer. I’m not sure. I still believe there is some intrinsic difference here, but I can’t put my finger on it. I think MIPs are more interpretable. What do you think?
Suppose for a moment, that your favorite sports team has completely adopted analytics. Your (American) football coach stops giving the inefficient running back so many carries. Your mediocre basketball center no longer dominates the ball for post-ups, instead serving as a willing passer to 3-point shooters. And your baseball team focuses itself around TTO, eschewing lower risk (but low reward) strategies such as stolen bases and bunts. Fantastic! Peak analytics has been achieved!
But, as this takeover occurs, will it be at the expense of novelty? Writing for TheRinger.com, Kevin O’Connor made some fascinating observations about novelty and sports analytics. He started wondering what happens if analytics reveals that there is only one right way to play the game, and strategy thus becomes homogeneous:
Statistics tell us this is the right way to score the most points in the most efficient way possible. But when every question has an answer, it’s not as fun to ask in the first place. If there is a right choice to make in every basketball sequence, will that kill the magic of watching a team or player offer their own solution?
For example, what if your basketball team insists on taking the first three-point shot it can on each possession because it is the most optimal solution? While this may result in more victories (at least in the short-term, before defensive adjustments), it may also result in a less excited, less engaged fandom.
So perhaps you aren’t a sports fan. Let me put it to you in a different way. Many of us have had the experience of buying an item off Amazon and then seeing ads for it on Facebook and Instagram. Big data has clearly monitored our purchase and decided that we wanted to see more of the same. And indeed, this simple logic makes a lot of sense in the abstract. But just because I had chocolate cake for dessert yesterday does not mean that I intend to embark on an all-chocolate cake diet! Instead, what would be better is if analytics could be used to guess what dessert I’d want to try next, or even that I’ll be more willing to purchase healthy food due to yesterday’s sugar guilt. Rather than merely reinforcing trend, analytics could be used to expand the customer’s tastes and options.
The point of this essay is not to say that analytics and novelty are enemies, and I’m sure many examples could be given of analytics being used to create novelty. But ORMS may be at the exciting stage where we can worry more about analytics being too important or powerful, rather than fighting for analytics acceptance. If we are at that stage, I look forward to seeing what new problems emerge as a result.
The A’s of AI: What I’ve learned and how I apply lessons and best practices of O.R., Data Science, Analytics, and Machine Learning
Many of us can all remember back to 2010 when “Big Data” was the buzzword and the “Vs of Big Data” helped characterize the ways business value was extracted from big data: volume, variety, velocity, and veracity. These dimensions provided an ontology that could be understood and more easily applied than the new and abstract concepts being introduced during Big Data’s earliest days.
We find ourselves in a similar hype cycle and edge of opportunity with Artificial Intelligence. Where we are in 2018 is not dissimilar from to the said inflection point of 2010… that breaking down the ways business can be extracted from AI will facilitate both adoption and disciplined application.
From thoughts gathered at the INFORMS Annual Meeting and across collaboration and conversation with other colleagues and friends in O.R., I suggest the following “7 As of AI” might be as follow:
- APPLIED – that APPLIED AI incorporates and applies methods by different fields such as machine learning, optimization, simulation, game theory, data analysis, statistics, data engineering, and computer science. Thus, APPLIED AI is a combination of Data Science and specialized knowledge.
- ASSISTED – that ASSISTED AI refers to remediation or controls presented to a human or decision-making system that presents scenarios, options, and richer context by a computer.
- AUGMENTED – that AUGMENTED AI superimposes information from multiple organic and non-organic systems to evaluate and depict information in a composite view.
- ACCELERATED – that ACCELERATED AI facilitates the automation, efficient designs, and technology levers to progress decision-making information more rapidly through processes.
- ADAPTED – that ADAPTED AI incorporates and applies methods to adjust strategy, technology, and other elements to satisfy unique requirements or evolving need.
- ACTIONED – that ACTIONED AI cues or launches an action based on the presentation of information. The bias for action supports the user’s preferred outcome.
- ADVANCED – that ADVANCED AI is a qualification of the system according to its examination and use of data and methods using sophisticated techniques, methods, tools, patterns, sensors, and routines to discover deeper insights, make predictions and generate recommendations.
From these, we see that the purpose of applying AI to any problem/opportunity is like what we purport and aspire to do in our fields of research and business: deliver value through the science of better.
INFORMS Data Mining Section – Thank you for the opportunity to keynote Saturday morning! Sharing thoughts on what it means and what it takes to be a practitioner and steward of “Thoughtful AI” with both young and tenured professionals and academics was great!
Just learned that i have been posting blog posts to the 2015 conference site, when I was thinking that I was getting the word out on the wonderful tutorials talks we have been having since Sunday morning… Thanks to all tutorials authors for their contributions to the volume this year!
We are wrapping up Monday’s tutorials with Linus Shrage and Suvrajeet Sen’ lectures this afternoon. The tutorial track is in North Building 229a, and you can find detailed info on the track on page 15 of the Quick Reference Guide.
Hope to see you all at the talks, but if you miss a lecture, we will be posting synch to slide recordings of the lectures, for the first time this year. The chapters are available thru the tutorials site, so please make sure to check them out!
Hope everyone is enjoying the conference, and please don’t forget to drink lots of water!
Looking forward to coaching a team during inaugural “Freestyle OR Supreme” competition at INFORMS Annual in PHX. OR/Analytics teams will formulate and present solution on the fly – with no Internet.
Join us at our to see the teams frame and solve a problem quickly, and a great showcase for any budding consultants (or hiring companies) out there. Winners will be selected by the client, with possible influence from audience applause.
November 5, 2018, 4:30 PM – 6:00 PM
North Bldg 231A