By Eric DuBois

Back in August 2011, I was in Massachusetts preparing for my first season as a teacher at Nature’s Classroom in Colebrook, CT.  Colebrook is located in the Berkshire Mountains in the rural northwest corner of Connecticut.  To get there requires driving for about an hour on small state and local roads.  Unfortunately, at the same time as I was preparing to leave, Hurricane Irene was hitting southern New England and by the time it was over, the region was a mess.

Many of the rivers across the region were flooded.  As many of the roads in the region either follow, or at a minimum cross, rivers, they had become impassable in the aftermath of the storm.  To further complicate matters, the huge number of downed trees and powerlines added additional roadblocks to my journey.  From the outside this appears to be a fairly straightforward OR problem.  All we must do is find the new shortest path. Right?

Unfortunately, in this instance as in most real disasters, the reality does not fit the model very well.  Specifically, most shortest path problem models assume perfect knowledge of the network or at the very least a good working knowledge of the probabilities that the roads will be open.  Two things worked against that in Connecticut.

1. The ‘interdicted’ locations change over time. As the water proceeds down the mountains it floods progressively larger watercourses.  So when I first start out the major mountain streams may have flooded the local roads and the smaller rivers are beginning to flood.  By the time that I have reached the mountains, those small rivers have reached flood stage.  Worse yet, there is no guarantee that the local roads are now passable since they may have washed out or become impassible with debris left by the receding water.
2. More importantly, information is quite scarce on where the blockages are. In the actual event, the State Police could provide little more than a rough sketch of what roads outside of the suburbs were underwater and almost no information on where debris had blocked transit.  It took me over two and a half hours to find a navigable route to Colebrook and that was after checking with the police and news sources for an hour.  Other teachers were not so lucky, having not properly checked the news, and didn’t arrive until the day after.

The moral of this tale is understanding the importance and difficulty in maintaining an accurate understanding of the state of the system during a disaster.  Significant literature is now looking at the use of social media and crowd-sourced information to flesh out the details of a disaster.  Unfortunately, this information is often inaccurate and misleading.  This can arise from something as simple as the lack of characters allowed in a tweet up to a complete misunderstanding of the situation by the individuals on the ground.  Unlike state police or disaster responders, these individuals have likely had no formal training in communicating accurately or previous disaster experience to gauge the conditions by.  So while the information provided may be better than nothing, it is certainly no panacea.

I can certainly see using the information to provide a gauge to determining where infrastructure restoration is most likely needed.  However, in the eventuality that we need to route emergency vehicles around these roadblocks, probabilities and guessing is not, in my opinion, a terribly great way to go about finding the optimal choice.  As operations researchers, how do you feel we can make use of this new source of data to inform out disaster response planning?

By Suzan Afacan

In my research, I am using Lagrangian relaxation dual to solve the mixed integer problem. This week I would like to explain the basics of Lagrangian Relaxation.

One of the most useful methods to solve combinatorial optimization models, especially for larger instances, is Lagrangian relaxation. Not only can we obtain a lower bound to the original (minimizing) model, but we can also obtain a feasible solution and upper bound to the original model by using Lagrangian relaxation dual. The most important feature of Lagrangian relaxation is making a difficult problem easier by relaxing the hard constraints.

The basic steps of the relaxation are:

• Take an integer or mixed integer programming formulation,
• Attach a Lagrangian multiplier to the constraints in the formula (you need to use an educated guess or luck to find the best constraint)
• Relax these constraints into the objective function,
• Solve this resulting integer programming optimally,
• This optimal solution gives us a lower (upper) bound to the original minimization (maximization) problem.

Mathematically speaking, here is a general example:

To solve Lagrangian relaxation dual the most often used method is the Subgradient Algorithm. Here is the basic outline of the Subgradient Algorithm:

The Subgradient Algorithm requires an upper bound on the original objective as an input. We need to set the starting value for Lagrangian multiplier u, the decreasing parameter Θ to 2 and the best bound to negative infinity.

Here we can choose some of the values problem specifically. For instance,the starting value for u can be set to 0, or better starting values can be found depending on the problem. The important property for the step size is

We want to reduce the stepsize such that it is not going to stick before finding the optimal value, but also we want to make sure that we are not shrinking the search area too quickly. Even though the formula used in the Subgradient Algorithm (Polyak’s formula) might provide a good solution for the Lagrangian relaxation dual, other choices of step size which satisfy the properties above might be better than Polyak’s formula depending on the problem.

To conclude,

Lagrangian relaxation can be used to solve difficult problems by relaxing the most difficult constraints, but you need to find the best choices for the constraints to relax on and the step size to get best Lagrangian Relaxation solution. If you can find the best choices for your problem, Lagrangian relaxation will be a great method. Even if you cannot find the best choice, Lagrangian relaxation will still give you a lower bound and it is not hard to construct a feasible solution using the Lagrangian relaxation dual solution to get an upper bound on the original problem.

 

References:

Comments on The Lagrangian Relaxation Method for Solving Integer Programming Problems. (2004). 50(12 supplement), 1872-1874.

K. Ahuja, T. L. Magnanti and J. B. Orlin. Network Flows: Theory, Algorithms, and Applications. Prentice Hall, 1993.

 

 

I recently read a paper entitled “Prioritization via Stochastic Optimization” (Koç and Morton, 2014), which was a timely read based on what we’ve been discussing in class lately. [1] The purpose of the paper is to present a new approach to solving resource-constrained activity-selection problems (RCASPs) using stochastic optimization and activity prioritization. The example application given by the authors is for the p-median model, a model with which we’re all familiar by this point. (As a quick recap, the idea of the p-median model is that there exists a set of customers located at various points and a certain maximum number p of facilities that can be built to service the customers. The objective is to minimize the total Euclidean distance any customer has to travel to reach a facility.) Formally, the p-median model can be written

When everything is deterministic, this model is relatively straightforward. Problems occur, however, when the maximum number of facilities is uncertain (which could be the result of uncertainty in the facility-building budget certain), but the decisions about where to place the facilities must be made before the uncertainty is realized. The figure below depicts optimal facility placement when the maximum number of facilities is known to be 4.

 

 

Now, we add uncertainty. If either one or two facilities could be built with equal probability, we get the first figure below. If up to three facilities or up to four facilities could be built with equal probabilities, we get the second and third figures, respectively.

We’ll formalize this model in a moment, but first I want to explicitly outline the series of events that occur in this prioritized model. First, a prioritized list of activities (facility locations) is selected without knowing the actual budget. Next, the uncertainty is realized .Finally, we make additional decisions (which facility covers each customer) depending on which scenario is encountered. Thus, perhaps the most “interesting” part of this problem is how to prioritize the activities. A priority list is a many-to-one assignment of activities to priority levels. We have two requirements for a priority list:

1. A lower priority activity cannot be selected before a higher priority one in any scenario.
2. Either all activities on priority level are selected or none are.

The first-stage problem, then, corresponds to creating a priority list. Suppose corresponds to the optimal objective value for scenario . We write the first-stage problem as

Essentially, these constraints require the priority list to be a list of subsets of the activities such that at least one activity is found in a given priority level, no activity is found in multiple priority levels, and taken together the whole list covers all the possible activities.

The second-stage problem is

where the second-to-last constraint enforces the requirement that all higher-priority activities are selected before lower priority ones and the final constraint requires either all activities or no activities on a given priority level to be selected. The rest of the constraints are the same as in the original p-median model, but the variables and parameters are scenario-dependent. Of course, the first-stage model is not a standard integer program, so we would like to find a formulation for this problem that can be solved by standard stochastic optimization techniques. Toward that end, we create additional decision variables , which are 1 if activity i has no lower priority than activity i’ and 0 otherwise. The corresponding two-stage stochastic integer model is

The first constraint ensures either activities i and i’ have the same priority level or one is higher than the other. It’s also relatively straightforward to check that the third constraint becomes the final two constraints in the previous model depending on the values of the pair  and.

Now, the activity-prioritization model isn’t particularly easy to solve in general (in fact, it’s NP-hard), but it does allow for potential stochastic or structural interdependencies between activities, which is an improvement on historical ways of looking at activity portfolios where each activity is treated as an independent entity. For more details on alternative formulations and some valid inequalities, I’ll refer you to the paper. Thanks for reading!

[1] Koç, Ali, and David P. Morton. “Prioritization via stochastic optimization.”Management Science 61.3 (2014): 586-603.

 

This time right after the spring break (and with no class material additionally covered therefore), I would like to try bringing a very casual topic to the post – a board game about disaster management, more specifically, Pandemic.

It is one of the most popular cooperative board game, published by Z-Man Games in 2007. (I guess many of you might already have played this before.) Four diseases have broken out in the world, and players acting as CDC agents work cooperatively to stop the spread and discover all cures before diseases wipe out the world.

I am bringing this as a topic because the framework of this game is really well-suited to the optimization models. The game board is a world map, which is exactly a network with 48 big cities as nodes and arcs connecting nodes with equal distance, as you can see in the picture. Arrivals of the disease to the city as well as contagion outbreaks are probablistic events, implemented as the frequency in the card deck. Moreover, since this is a co-op game, we can say that there is only one stakeholder, which is a setting welcomed by operation researchers.

There exist many kinds of strategic decisions players can make, and one of the main decision is locating the research centers so that players can access all cities easily from the research centers. This can be considered as either a maximal covering or a p-median facility location problem. Actually, some people already studied this problem using basic network analysis. Quick spoiler: when we locate 3 research centers, Atlanta/Hong Kong/Cairo minimizes average distance. To read more about the list of ‘optimal placement’ decision they figured out, you can view Optimal Placement of Research Centers in Pandemic and Overanalyzing Board Games: Network Analysis and Pandemic.

Some say that there’s no fun if we attempt to break everything down into efficient mathematical equations. But I’d rather claim that it is always interesting to see how our intuitive decisions works compared to a computed ‘optimal’ one, or study why the discrepancy between the model and reality is happening. And we know that we can’t do so without doing the math.

Have fun!

Soovin

 

Today’s topic is submodularity! This special structure allows a whole new mathematical toolbox to be used in the never-ending fight to improve formulations and reach optimal solutions faster.

Let be a finite ground set. A submodular function  is a set-defined function that exhibits a “diminishing returns” property. That is, adding an element to a small set results in a greater impact on the function than adding that element to a larger set. There are multiple equivalent ways to define a submodular function. Perhaps the most intuitive of these is below.

Let with . is submodular if for every , we have . Here,  represents the marginal increase in the set function when element is added to a smaller subset of , . This marginal increase must be at least as large as the marginal increase obtained by adding to a larger subset of that contains .

An equivalent definition is as follows. Let . is submodular if .

It should also be noted that under certain conditions, optimizing submodular functions can be very easy.

Let’s examine a few places in public sector operations research that submodularity could arise.

Example 1: Path interdiction

Let be a path in a network. In my previous blog post, we discussed basic maximum-reliability network interdiction. In the same vein, let be the probability of traversing arc undetected when arc is not interdicted. Let be the probability of traversing arc undetected when the arc is interdicted. Naturally,  for all . Let be the set of path arcs that we choose to inderdict. Let the function be the probability of an attacker traversing the entire path undetected. This function can be written as

.

Then  is supermodular. A supermodular function simply reverses the inequalities above: i.e. holds for  with  and every . The proof is obtained by directly applying the definition of supermodularity. The fact that is supermodular is very intuitive; the more arcs that we interdict, the less of a reduction (not increase!) we notice in the attacker’s traversal probability.

It follows that  is submodular.

Example 2: Radio tower coverage

Imagine we were to give up our lives of fortune as operations researchers and pursue a humbler existence in the radio entertainment industry. We wish to select a subset of radio towers from which to broadcast our station. The broadcast ranges of these towers overlap.

Our goal is to cover as much surface area as possible. Let be the set of towers. For a subset of selected towers , let  be the surface area covered by those towers. Then is submodular. Below are a few pictures to illustrate the point.

Suppose we have potential radio towers to use for coverage. Suppose also that want to use the second radio tower, because the cost of doing so is negligible.

What happens if we choose to also use the third radio tower? Naturally, our covered surface will increase. Note that the marginal increase in surface area is the strictly-blue region.

Cool! Now, suppose that we initially choose to utilize the first and second radio stations.

When both of these radio stations are selected, what happens to the marginal increase in surface area when we include the third tower in our broadcast coverage?

Again, the strictly-blue region represents the surface area we added to our network by including the third radio tower. This blue area is much smaller than it was when we included the second tower and not the first. Looking at the definition of submodularity, we expect this marginal increase to be smaller! Mathematically, we have .

Conforti, Michele, Gérard Cornuéjols, and Giacomo Zambelli. Integer programming. Vol. 271. Berlin: Springer, 2014.

Way back in my first blog post, I talked about how there are several areas where operations research would likely be useful within the State of Wisconsin, and one of the areas I highlighted was the State’s interdepartmental mail transportation system. Over the last few months, I’ve been working to model this system with Professor Linderoth, and I figured it’d be worth discussing here since it’s technically a public sector OR problem.

To provide some context for this problem, here’s the basic setup. There are 57 locations in Madison that require mail deliveries each day, and five trucks are available to make these deliveries. Each truck is assigned a total of four routes (one for each time period), and these routes all start and end at the “depot” where the mail is sorted and prepared for the next delivery. Some locations require multiple stops throughout the day, but otherwise there are very few additional complexities. As a result, this problem can be represented using a set-covering model where the objective is to choose a set of routes that minimizes the total distance the trucks have to travel each day.

This model can be seen below:

Unfortunately, despite the simple mathematical formulation, developing a reasonable solution to this problem is quite challenging because of how many possible routes there are. Even when the number of locations on each route is restricted to 15, there are still more than 2.88e+25 routes that could be taken [1]. That’s a lot of routes, so generating and including all of them in the model simply isn’t practical.

Instead, a more reasonable approach is to create a small set of “good” routes that could be used to find a heuristic solution. While there are a number of sophisticated techniques that exist for this purpose, I originally started with an extremely simple approach and added additional complexity over time. At first, this consisted of randomly generating a large number of routes and throwing out any that exceeded a “high cost” threshold. Building off of this basic structure, I then improved the process by creating routes using location “clusters” to increase the likelihood of generating a good route each time. These routes then served as a starting point for the iterative, column-generation scheme that I’ve been working on most recently, which is something I’ll probably describe in more detail in a future blog post. Although these are fairly crude approaches to route generation, they’ve already resulted in a 15-20% reduction in total travel time when compared to the current state, and that number can only improve as further refinements are made.

[1] Expressed mathematically, this is 57!/(57-15)! since there are 57 locations, the order of stops along a route matters, and each location can only be visited once per route.

Happy week-before-spring-break! In less than a month, I am going to be presenting a paper entitled “Interdicting a Nuclear-Weapons Project,” by Brown et al., written in 2009. While I will obviously be getting into more of the gritty details in my presentation, I wanted to give you a little flavor of what the problem looks like. In particular, I’d like to briefly introduce the concept of bilevel programming and how it relates to nuclear weapon project interdiction.

A bilevel problem can be thought as a “game” between two decision makers. One decision maker makes an decision based on a set of constraints and some objective that benefits them, and then a second decision maker with a different (often contrasting) objective takes action that benefits them. In [2], the authors present the general form of the bilevel programming problem as follows:

.

In this general form, the first decision maker tries to guess how the second decision maker will minimize their objective and acts accordingly, counteracting the expected actions of the second decision maker. Then the second decision maker takes action after seeing what the first decision maker chose to do, which affects their feasible set of actions. Of course, further restrictions can be imposed, such as requiring certain variables to be integer. Many bilevel problems are nonconvex, so they can be incredibly difficult to solve.

The interdiction problem is a good example of a bilevel programming problem. With nuclear weapon proliferation, specifically, the proliferator would like to quickly produce (and possibly disseminate) a batch of weapons, whereas the interdictor would like to delay the production as much as possible. The underlying assumption is that the proliferator can see any action done by the interdictor and thus can act to inhibit or avoid any such action. The objective used in the nuclear weapon interdiction paper is

where S is the earliest start time of the final task that must be completed by the proliferator, and x and y are the decisions made by the interdictor and the proliferator, respectively.

The nuclear weapons interdiction problem also has many constraints and multiple decisions to be made, so it is a complex problem. I’ll get into the details of the model and the algorithms used to solve it in my presentation, and probably in a future blog post as well, but for the time being I wanted to set up the idea of bilevel programming and how nuclear weapons proliferation can be viewed as a bilevel program.

[1] Brown, Gerald G., et al. “Interdicting a nuclear-weapons project.” Operations Research 57.4 (2009): 866-877.

[2] Bard, Jonathan F. “An algorithm for solving the general bilevel programming problem.” Mathematics of Operations Research 8.2 (1983): 260-272.

By Eric DuBois

Anyone that knows me at all or has spent at least two minutes in my office during NCAA hockey season knows that I am a huge hockey fan- especially women’s hockey.  This is partly from self-interest.  One of my alma maters, Clarkson, won the NCAA championships back in 2014. Further, if you look at Wisconsin, the women’s hockey team here has been consistently outstanding of late, the men’s team, not so much.  Both Clarkson and Wisconsin are in the Frozen Four again this year and it should be a great weekend for hockey.

One of the consistent problems facing women’s hockey is the same problem facing a lot of other women’s sports: namely, it is not considered ‘as good’ as men’s hockey and therefore, gets little attention from the NCAA.  So it came as no great surprise this year when the tournament bracket came out and it was a pretty sad farce of a thing showing very little commitment from the NCAA.  Really I get to see Clarkson play Quinnipiac again?  Didn’t we just play them less than a week ago in the ECAC tournament?  And I’m sure Boston College was just as pleased to see that they get to play Northeastern for the umpteenth time.  Real crowd pleasers there…

This reminded me of Eli’s post earlier in the year about his role modeling for the Center for Athletic Scheduling at UW- Stevens Point.  One of the benefits of scheduling with a model is that you can maximize the fan’s enjoyment of new matchups and not have to resort to replaying the same old games.  More to the point, though, operations research allows us to get a more objective solution than anything that can be produced by hand.

I think this is a benefit that is often ignored.  Rather, we tend to focus on the faults that can originate from basing our system on finding the best or most efficient solution.  However, given the variety of different groups that can be affected by public policy, it is worth considering the benefit of having an objective solution to the problem, especially if that solution has been constrained to provide a reasonably equitable solution.

Whether we like it or not, we all have unintended biases that affect what we would consider to be a reasonable.  I personally recommend looking at Project Implicit if this interests you.  I have little doubt that if I were to make the NCAA bracket, I would be highly susceptible to team pairings that would annoy many people as well.

In a similar way, in planning disaster response, I am sure that personal biases would get in the way.  For proof of this in action, look no further than what happened to the original San Francisco Chinatown during the 1906 earthquake.  For those not aware, Chinatown originally looked the same as the rest of the city.  It was only after the earthquake and in a bid to win white approval, that they sought to make it look ‘Oriental.’  That was mainly because the white controlled emergency response decided Chinatown was worth losing in its entirety to save the affluent neighborhoods nearby.

So while we may be worried about the inequalities that arise from looking only at efficiency, humans are hardly good arbiters of fairness.  Do you think the objectivity of operations research gives it an edge in producing good public policy solutions?

By Suzan Afacan

 

Donald Norman, the director of the Design Lab at the University of California, San Diego, said, “The real problem is that the car is too safe” and continued “They have to learn to be aggressive in the right amount, and the right amount depends on the culture”.

I believe the driving culture is even different between the cities or states of a country. It is really hard to consider these details, since it is also heavily changes in terms of individuals. Additionally, not just the driving culture but also the pedestrian culture should be considered in the coding of driverless cars. Since the consequences of crashes may be paid in human life, these studies are really sensitive. As a result “the right amount” is pretty hard to decide.

Another different aspect is that a driver ‘s behavior could depend on their mood (e.g. they can be in a rush for work, tired, or unhappy) and the traffic congestion.

In addition to all these parts, now people also play with their cell phones (texting, talking, etc.). This will add extra difficulty since their attention to the road, other vehicles and pedestrians will decrease.

Should “…the right amount” include the cell phone factor as well? Here engineers should try to include human mistakes in their modeling. But how do we guarantee that they will certainly make these mistakes in the scenario based circumstances.

These reminds me of the blog post “crime modeling” (by Eli Towle) talking about predicting an individual’s crime based on the pattern similarities with other offenders. This system’s biggest problem is punishing the people forthe potential crime, which they would not commit.

Likewise here, you need to predict possible human mistakes. What will be the consequences, if there is an accident? (Since 2009, the driverless cars have been in 16 car accidents). How does the justice system will work?

It seems there is a long way to go before we the driverless cars around. If someday all these issues could be solved, I strongly believe it will improve the other area of human-machine interaction needed. In our technological world, involving the human factor is a big issue for most of the projects.

Even though a recent study shows that an estimated 21,700 fewer people would die on roads, this assumes that 90% of vehicles are driverless. Achieving this 90%is also big issue when we consider the poverty level in the world.

Despite these problems, according to the news agencies, several car companies will make driverless vehicles available on the market by 2020(you may not able to drive them everywhere, though). By 2025, driverless cars will be used all over the world. Even UBER is considering making their fleet driverless by 2030.

It seems 1956’s Motorola’s “Key to the Future” film will become true.

I am pretty excited to see those days, with have some hesitations though.

Drive Safely…

SA

 

The class material  of the last week covered the hypercube queuing model, approximation and some variations. As an extension, I am going talk more about variations of the hypercube model in this post.

exact model and approximation model
These were covered in the class in detail. See Larson(1974) for the exact model. The approximation model treat servers identical to reduce the state space from 2^n to 2n. See Larson(1975).

customer-dependent service rates
Jarvis(1985) provides a procedure for approximating the equilibrium behavior of multi-server loss systems with distinguishable servers and multiple customer types. Instead of using a fixed value of mean service time, the mean service time is approximated at the end of each iteration using weighted sum of dispatch probabilities and customer-dependent service rates. We’ve covered this iterative procedure in the class. But there are exact models with customer-dependent service rates too. Atkinson et al(2008) considers a queuing system describing EMS with distinct geographical zones. Their exact hypercube model has 3^n states, so for computational tractability they propose two heuristic methods and a simulation approach for approximating the steady-state probabilities.

modeling co-located servers and dispatch ties
It is assumed that the servers are dispatched according to a fixed preference dispatching scheme(which is frequent in hypercube family of queuing models). When servers are co-located in the same station, these equally preferred servers generate ties in the dispatch preference lists. In order to break the tie and distribute workload, Burwell et al(1992) use a method called stacking, which is to split the call type with tied preferred servers into multiple copies. This problem of co-located servers is solved in Budge et al(2009) by other approach. They explicitly allows multiple vehicles per station by providing an extended iterative hypercube approximation procedure.

partial backup hypercube queuing model for EMS on highways
Iannoni et al (2007) considers an EMS on highways that only certain servers in the system can service calls in a given region(partial backup). Calls are of different types and the servers are distinct. Multiple(1-3 servers for a call) dispatch is also considered here.

I myself is also studying some kind of variations, which is to apply a hypercube approximation model to analyze cutoff priority queue. In the cutoff priority queue scheme, low priority customers are served only when the system is relatively idle. When the number of busy servers is above ‘cutoff number’, a low priority call is put in a queue(or lost if queue is out of capacity) instead of being served immediately. As a result, the system keeps servers in hand most of the time so that it can better be ready to serve future high priority customers.

Before I finish the post, let me stress that this is NOT a comprehensive summary of all hypercube queuing model variations. There are vast literatures related to hypercube queuing mode, and I am introducing just a small subset of it. So I expect we may share more information as any of us see other interesting variations of hypercube queuing model later.

Soovin

References
Atkinson JB, Kovalenko IN, Kuznetsov N, Mykhalevych KV (2008) A hypercube queuing loss model with customer-dependent service rates. Eur. J. Oper. Res.
Budge S, Ingolfsson A, Erkut E (2009) Approximating vehicle dispatch probabilities for emergency service systems with location-specific service times and multiple units per location. Oper. Res.
Burwell TH, Jarvis JP, McKnew MA (1993) Modeling co-located servers and dispatch ties in the hypercube model. Comput. Oper. Res.
Iannoni AP, Morabito R (2007) A multiple dispatch and partial backup hypercube queuing model to analyze emergency medical systems on highways. Transportation Res.
Jarvis JP (1985) Approximating the equilibrium behavior of multi-server loss systems. Management Sci.
Larson RC (1974) A hypercube queuing model for facility location and redistricting in urban emergency services. Comput. Oper. Res.
Larson RC (1975) Approximating the Performance of Urban Emergency Service Systems. Oper. Res.