Mother’s Day optimization…

For my last blog post, I would like to write about Mother’s day optimizations.

While online shopping is increasing everyday, retailers try to increase it more during special days like Mother’s day, Christmas etc. Optimization is needed more and more to achieve this, especially during these kinds of days. According to the Mother’s Day Consumer Intentions and Actions Survey, the average person spends around $127 to buy a Mother’s Day gift. Hence, it has a big potential to increase profit.

I will try to list some of the ideas here:

-Searching keywords:

Since consumers will not just use their webpages to search, retailers should use appropriate keywords in their webpages to be reached from more general searches. Certain keywords will make a big difference on special days marketing. Temporarily expending keyword lists about gifts, gifts idea etc. during these days will give a chance to increase sales. For instance, 64% of Mother’s Day searches include “ideas”, “homemade”, “best”, “unique” and “cheap”.



-Optimization of voice traffic:

These special days are the busiest time for phone services also. It creates a need to optimize the voice channel usage. Call centers of online shopping and stores should consider these days separately and be ready for them. Using the previous years’ data, necessary information can be obtained to maximize the customer satisfaction and then the profit.

Generally, Erlang models are used to solve these issues.

An Erlang B Traffic model can be used to model blocked calls. Assumptions in this model:

Number of sources is infinite

  • Call arrival pattern is random
  • All blocked calls are cleared
  • Hold times are exponentially distributed

An Erlang C model can be used to find the number of agents needed for incoming call volume and the probability of delaying a call. Assumptions for this model:

  • Number of sources is infinite
  • Call arrival pattern is random
  • Blocked calls are delayed
  • Hold times are exponential distributed

-Optimization of cost and consumption strategies:

Traditional pricing systems do not have a way to reflect pricing strategies for special days. If they do not separate special days from others, there will be underestimation. For example, if they count Mother’s day as spring season, the store can underperform in terms of Mother’s day gifts. If a store has a promotion during these special days, it is important to understand the effects of that promotion on the whole store. Store managers should consider which type of customer would be happy with which kind of promotion. Scientific and data based promotion have a potential for produce more profit.

-The most important optimization:

Of course, do not forget to maximize the effects of words, which will make your mother feel like the best Mom in the entire world when you celebrate her Mother’s day.


Optimize on…




Network interdiction and Zombie attack!

In this post, I would like to write about the second paper I will present in class. I chose a paper about multicommodity flow network interdiction, since both multicommodity flow and network interdiction models are interesting topics to me.

As Amanda and Eli mentioned in their previous blog posts, network interdiction models have lots of applications especially for the military and homeland security.

In network interdiction models, we have a leader who destroys arcs to disrupt the follower’s (enemy) flows. In the paper, “Algorithms for Discrete and Continuous Multicommodity Flow Network Interdiction Problems,” the model allows for more than one supply node for each commodity and multiple demand nodes. As an objective the leader interdicts the arcs to minimize the follower’s optimal reward with the budget B. The paper considers the discrete and continuous cases for interdiction. While in the discrete case each arc can be fully destroyed or operational, in the continuous case each arc can be partially destroyed so then depending on the percentage of disruption the capacity of arc changes.

The mathematical model is as follows:


where y is follower’s decision variable and x is the leader’s decision variable. Hence x is the percentage ofarc disruption and y is the amount of flow passing through that arc. Writers present several methods to solve both the discrete and continuous interdiction models. Here I would like to focus more on one specific application area of the interdiction models….like a Zombie attack!!!

To reach a safe place from Zombie attack, we can use shortest path models and with interdiction model, we can also slow down the attack. In this context, we can consider the enemy as zombies, the leader as human, and adapt the problem to disruption of zombie attack problem, which is one of the most IMPORTANT!!! homeland security issues. Now, the objective becomes to minimize the zombie attack achievement since they want to eat human’s brains and we want to escape from them. There are some guidelines out there on how to escape from Zombie attack, but as operations researcher, we should use our tools to achieve it. We can suppose that after having the first bit of brain they would like to eat more and more… But I’m not sure – just guessing. Anyway with this network interdiction idea, we can decrease the number of our friends that get slaughtered and recruited… Here we can see how interdiction models are helping us to secure our homeland not just from bad people but also from the zombies.

TV STILL FOR TV -- DO NOT PURGE -- Walkers - The Walking Dead _ Season 5. Gallery - Photo Credit: Frank Ockenfels 3/AMC
Photo Credit: Frank Ockenfels 3/AMC


If you wonder more about Zombies, there is a whole archive at the “Punk Rock Operation Research” blog ( and even a zombie apocalypse course in the University of Michigan to teach students survival skills.

Note:  Stochastic network interdiction is also studied in the literature and there is a great source for that by Janjarassuk and Linderoth..


Lim, Churlzu, and J. Cole Smith. “Algorithms for discrete and continuous multicommodity flow network interdiction problems.” IIE Transactions 39.1 (2007): 15-26.

Janjarassuk, U. and Linderoth, J. (2008), Reformulation and sampling to solve a stochastic network interdiction problem. Networks, 52: 120–132. doi:10.1002/net.20237




Supporting station idea…

By Suzan Afacan

As the end of the semester is approaching, we will start our final presentations as a class. One of the papers I will present is “A supporting station model for reliable infrastructure location design under interdependent disruptions” by Li et al (2013).

Infrastructure systems are important for society and the economy. The definition of infrastructure systems is pretty wide including transportation, communication, energy and more. The systems have high interdependency. In the models that study infrastructure systems it is not easy to include these interdependencies. Dependency between facility failures is one such instance. Even though independent failure of the facilities can be modeled without trouble, when we want to include the connections between facility failures, it is not that easy to model all the dependent failure scenarios.

With the supporting station idea, this paper explores the network location design problem under dependent facility failure with this connected supporting stations, which have independent and identical failure probabilities.

Each supporting station has a set of facilities to support. So a facility is operational if at least one of its supporting stations does not fail.



In this example customer “i” can be served by the facilities “A”, “B” and “C” with the given distances from “i” respectively 10, 20 and 30. With the supporting station idea, this system will turn into the next figure.


This figure shows the same customer with the same possible stations to serve it, but this time supporting stations show the failure dependency between facilities. To be more specific, if supporting stations “a” and “b” fail then facility “A” cannot be operational anymore and the failure of supporting station effects failure probabilities of facility “A” and facility “B”.

The integer formulation of the model is as follows:





The objective of the model is to minimize the expected total cost of the fixed facility and supporting station investment cost in addition to the expected total transportation and penalty cost.

The paper presents a sensitivity analysis and also a case study for the model with different failure probabilities and penalty costs. For further details, I will refer you to the paper.

To conclude with, this paper has a different approach to the modeling of interdependent failure of the facilities while introducing the supporting station idea. As one of the suggested future research directions of the writer, it could be worthwhile to extend this model to other related models in the field to increase the reliability and resilience of the problems.


Li, Xiaopeng, Yanfeng Ouyang, and Fan Peng. “A supporting station model for reliable infrastructure location design under interdependent disruptions.” Transportation Research Part E: Logistics and Transportation Review 60 (2013): 80-93.

Lagrangian Relaxation..

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

Screen Shot 2016-03-28 at 11.11.53 PM

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.



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.



Driverless Cars!!!!

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…



Is there anyone who likes to wait in the line?


This week we have learned Queuing Theory in the class 823.

People are sometimes impatient and it is difficult for them to wait in line to receive services. Queuing Theory is the study of how to make waiting more enjoyable (not quite J but partially maybe). Queuing theory proposes to predict the waiting time in the line. Generally, these predictions are helpful for operations researchers as they can use them to make systems more efficient.

In class, we have talked about several negative stories in which people moved in front of someone or they did not obey the rules while waiting in the line. Unfortunately, the ends of the stories were dramatic. (Eric can tell you more about the stories).

Even though general systems are based on first come first serve, sustainability of this rule is a public issue. People get angry and frustrated and they do not want to wait even a second more. There can be priorities for some people such as individuals with disabilities, elderly, and pregnant women. Moreover, some companies prioritize their customers in service so that those customers feel like they are privileged.

I would like to share one of my personal stories on this topic. About a month ago, while I was traveling, one of my flights was cancelled. This was a connecting flight and since one of them was cancelled I needed to reschedule all of my flights. I called the airline’s help center. I tried to talk to them for a longtime as they were repeatedly checking my information and were trying to find a new flight. Eventually, I was given a new connecting flight after three hours of talking and waiting on the phone. By the way, I should thank them because I listened to their very nice music while waiting and they keep saying me “One moment, please. … Your call is important to us. …. A representative will be with you shortly.” Do you think that this is the end of the story? Of course not!

The next day, I was finally in the airplane and took my first flight. After I completed my first connecting flight, I learned that the airline had not purchased my second flight and instead just reserved it. Therefore, I needed to call them back.

The phone signal was not good at all at the airport. While I was talking with the call center person, my call was dropped… after I had told the story and they were trying to help me. I called them six times and each time the call was dropped. Each time a different person answered my call and each time, I had to tell them the whole story from the beginning.

Finally, they resolved the issue and I was ready for my next flight. However, they spent so much time to confirm my flight by the time they solve the issue, it was too late for the next flight and then I missed that. I took another flight after waiting 7 hours in the airport, but no worries at the end I reached my destination.

As can be understood, the story is not fun when it occurs to you. However, I believe that there is something that we can learn from this experience. After all, it could be good to have a kind of new calling system for companies in which they can dispatch the dropped call to the same employee who was previously talking with the costumer. By doing that, the customer will be more satisfied with the service because they will get faster help that will shorten the waiting time. Importantly, costumers will not have to tell the whole story to every airline operator.

There is a type of Queue called virtual queue, in this type of queue the caller choose to be called back when there is an available server.


One possible solution could be the virtual queue system. The virtual queue system could be adapted to these kind of cases, and if the server need more than certain threshold time, they can give you the option to call you back, when they resolve your problem with the estimated time. Hence the caller will not wait with the phone and the not need to worry about whether the call will be dropped during the waiting time.

I do not know if someone has studied this specific topic. However, according to my experience, it is worth thinking about the possibilities.

I wish there could be days in the future when no one will wait in the line…


Gisby, Doug. “Intelligent virtual queue.” U.S. Patent No. 6,002,760. 14 Dec. 1999.

Has enough research been done in the disaster operations management (DOM) area?

By Suzan Afacan

I will present the article “OR/MS research in disaster operations management” (Altay and Green III, 2006) this week in the ISyE 823. It will be good opportunity for me to give an overview of this paper in my blog post first.

Even in 20th century, disasters are still big issues for the societies and nations. One of the deadliest example is the 2004 Indian Ocean Tsunami which resulted in the lost of 225,000 people.

Altan and Green reviewed the articles in disaster operations management up to 2003.

It is really surprising that most of the studies in the area are done by researchers in the social sciences from social and psychological point of views.

Before starting to the analysis of articles, let’s take a look at the operational stages of disasters;

  • Mitigation: applications to reduce the impact of the disasters,
  • Preparedness: activities to make society better prepared for disasters,
  • Response: resources to protect the community and its property,
  • Recovery: long-term actions to recover from the impacts of the disaster.

There is a great table in which the writers summarize the statistics of the articles on Disaster Operations Managements (DOM).

Screen Shot 2016-02-14 at 2.08.00 PM

Take away from the table:

  • Authors with an affiliation to the USA published most of the articles,
  • Main-stream of DOM starts after the 1990s with one of the possible reason being the declaration of 1990s as the International Decade of Natural Disaster Reduction,
  • Mathematical programming (included heuristics) is the method most used in the research,
  • Based on the Comprehensive Emergency Management’s four-phase disaster classification: mitigation is the most widely studied, preparedness, response and recovery follow it respectively.
  • No one studied humanitarian emergencies (epidemics, war etc.),
  • Just one article studied recovery planning published in the OR/MS journals.

There is another classification paper on this topic (Denizel et al., 2003), which presents extended classification interested ones might look at that paper also.

“DOM is by nature multi-organizational.”

The writers suggest that trying to include the ethical factors of the subject in the models is worth consideration. Also, different incident specifications may need different optimality approaches since political issues might potentially hit here again.

“You can lead a horse to water, but you cannot make him drink.”

You may not able to make every stakeholder happy even though you have the best math-programming model.

We can consider the article’s resulting idea:

“More research needs to be published in academic journals to attract the attention of OR/MS researchers to the subject matter.”

Especially, between the DOM stages, recovery planning needs more attention by researchers with the understanding of the interdependencies between critical infrastructures and systems.

Managing the disasters better will help for rapidly recovering after the disasters hit, increasing the readiness level of the community and its resources, protecting society and their properties by decreasing the response time and effective usage of the potential resources.

Blogger’s Note: After I read this article, I have a better understanding of how important the recovery phase after a disaster. I think that I am in a right direction with my current research topic in which I have been modeling the interdependency between infrastructure systems and emergency services while trying to recover the systems with more effective way. Additionally, there are several articles, which I know studied the interdependency of the systems by considering the recovery phase of the disaster. (e.g., Nurre, Sarah G., et al ; 2012)


  • Altay, Nezih, and Walter G. Green. “OR/MS research in disaster operations management.” European journal of operational research 175.1 (2006): 475-493.
  • Nurre, Sarah G., et al. “Restoring infrastructure systems: An integrated network design and scheduling (INDS) problem.” European Journal of Operational Research 223.3 (2012): 794-806.
  • Denizel, Meltem, Behlul Usdiken, and Deniz Tuncalp. “Drift or shift? Continuity, change, and international variation in knowledge production in OR/MS.” Operations Research 51.5 (2003): 711-720.