Problem 1- School Bus Procurement
Suppose that you are in control of purchasing new school buses for Rolla High School. In particular, the city mayor asked you to buy all electric vehicles for school bus services. There are three companies that you can buy electric-buses (E8's) and the cost and bus specifications for each company are as follows:
- Company 1: Electric-Bus (E-Bus for short) is a company based in California that produces electric buses. It sells each bus for $300,000. The buses produced by E- Bus have seating for 30 students. To be able to purchase buses from E-Bus Company, a fixed payment of $200,000 should be paid. Furthermore, E-bus Company restricts its customers to buy at least two buses and it can sell at most 10 buses.
- Company 2: Charge-the-Bus (C-Bus for short) is a company based in Michigan that produces electric buses. It sells each bus for $375,000. The buses produced by C-Bus have seating for 40 students. To be able to purchase buses from C-Bus Company, a fixed payment of 5180,000 should be paid. Furthermore, C-bus Company restricts its customers to buy at least 3 buses and it can sell at most 15 buses.
- Company 3: Zero-Emission-Bus (2-Bus) is a company based in Texas that produces electric buses. It sells each bus for $220,000. The buses produced by Z-Bus have seating for 20 students. While 2-Bus does not required fixed payment for procurement of its buses, it restricts its customers to buy at least 4 buses and it can sell at most 20 buses.
There are 1,000 students in Rolla High School; and, therefore, as the purchasing manager, you want to make sure that the total seating of the buses you purchase is at least 1,000. Also, since the school's bus parking area is restricted, you should not buy more than 35 buses. Furthermore, you want to have at least two different types of buses in the fleet, therefore, you want to buy buses from at least two different companies. As the purchasing manager, you want to decide on which companies to buy buses from and how many to buy from each company so that you satisfy the above conditions while minimizing the total cost. The total cost is equal to the fixed payments plus purchasing costs.
Formulate a mixed-integer-binary programming model for the above bus purchasing problem. Note that the model should be linear and the number of buses purchased from each company should be integer. Define your decision variables and the notation you use for the decision variables (for binary variables please make sure to explain what 1 means and what 0 means), write your objective and objective function and formulate the constraints using your decision variables. Combine everything to get the final model.
Problem 2- Payment Offices
Suppose that you are a financial consultant and you receive credit card payments from four regions of the country: West, Midwest, East, and South. The average daily value of payments mailed by customers from each region is as follows:
- $70,000 from the West region,
- $50,000 from the Midwest region,
- $60,000 from the East region,
- $40,000 from the South region.
You must now decide where the customers should mail their payments. In particular, you want to receive payments as quickly as possible because you can earn 20% annual interest by investing the revenues you gain from the payments. Because of the importance of the time to receive payments, you are considering locating offices to process payments in four different cities: Los Angeles, Chicago, New York, and Atlanta. The average number of days from the time a payment check is sent from a region until the payment check clears and you can deposit the money depends on the city to which the payment is mailed. The table below shows the average number of days from the day the payment is mailed from each region until the payment clears at each city office.
|
Average Number of Days between Mailing Check and Check is Cleared
|
|
|
City of Office
|
|
Region
|
|
Los Angeles
|
Chicago
|
New York
|
Atlanta
|
|
West
Midwest
East
South
|
2 6 8 8
|
6
|
8
|
8 5 5 2
|
|
2
|
5
|
|
5
5
|
2
5
|
For example, if a check is mailed from the West region to Atlanta office, it would take an average of 8 days before you could start earning interest on the check.
You want to determine which cities to locate an office and where each region will send the payment checks. You can locate at most one office in a city. Furthermore, each region will send the payment checks to exactly one city, where there is an office. If there is no office in a city, that office cannot receive payment checks; however, if there is an office in a city, it may receive payment checks from more than one regions.
While deciding where to locate offices and where the regions send the payment checks, you want to minimize the total annual cost. The total annual cost consists of annual office operating costs and annual lost interests. The annual office operating cost is $50,000 for an office (no matter where the office is located). The annual lost interest is the summation of the annual lost interests on the payments of the regions. For instance, the annual lost interest for the East region is calculated as follows:
- Suppose that there is an office in Chicago and the payment checks from the East region are sent to the Chicago office. On any given day, payments of 5 days from the East region will be waiting to be cleared, i.e., on any day, $60,000x5=$300,000 payments from the East region is on hold, which you could use for interest earnings. This implies that, on average, you lost 20%x$300,000 = $60,000 that you could have earned in interest. Therefore, assigning East region to an office in Chicago has an annual cost of $60,000. If there was an office in New York and you had decided to assign the payment checks from East region to the New York office instead of Chicago office, your annual cost due to interest loss from East region would be 20%x$60,000x2=$24,000.
a) Formulate a binary programming model for the above office location and payment assignment. Note that the model should be linear and you only have binary variables. Define your decision variables and the notation you use for the decision variables (for binary variables please make sure to explain what 1 means and what 0 means), write your objective and objective function and formulate the constraints using your decision variables. Combine everything to get the final model.
b) Formulate the following restrictions as mathematical linear constraints that are independent of each other and the constraints (excluding binary definitions) in the model in part a. Note that the constraints should be linear. Furthermore, the final constraint should not have any wording such as "if", "and", "not equal", "or", "then".
i. If there is an office in New York, there should be an office in Atlanta.
ii. There cannot be offices in both Chicago and Los Angeles.
iii. If there is an office in Atlanta, there should be at least one more office in other cities.
iv. If there is an office in Los Angeles, there can be an office in at most one other city.
v. If there are offices in Los Angeles and Chicago, there cannot be an office in New York.
vi. If there is an office in Chicago, it should receive checks from at least 2 regions.
vii. An office in New York should receive payment checks from at least as many regions as an
office in Chicago does.
viii. If there is an office in Atlanta, it cannot receive payment checks from both East and West
regions.
ix. An office in Los Angeles cannot receive payments only from the South region.
x. If Chicago office receives payments from South, New York office should receive payments from West.
Problem 3- The Longest Path
Suppose that you are given the following network and the cost of each arc on the table on the left.
|
Arc
|
|
Arc
|
|
From
|
To
|
Cost
|
|
0
|
1
|
52
|
|
0
|
2
|
65
|
|
1
|
3
|
77
|
|
1
|
4
|
65
|
|
2
|
3
|
70
|
|
2
|
4
|
99
|
|
2
|
5
|
60
|
|
3
|
5
|
55
|
|
4
|
5
|
62
|
Mathematically formulate a binary programming model to find the most expensive path from 0 to 5. (i) Define your decision variables, (ii) formulate the objective and the objective function in terms of your decision variables, (iii) formulate the constraints and explain why they are needed, and (iv) combine everything to have the final mathematical formulation.
Note: A path between two nodes consists a set of nodes such that each node is visited once and the path is connected. For instance, 0424445 is a path from 0 to 5 whereas 04143, 445 is not a path since it is not connected.
Problem 4- Dr. Konur's Nightmare
After eating a jar of Nutella right before sleeping, Dr. Konur had the worst nightmare about mathematical programming. The nightmare was about not only integer programming but also non-linear programming. In particular, there was an alien asking Dr. Konur questions non-stop to learn more about optimization. Please help Dr. Konur by answering the following questions and explaining the answers briefly.
a) The first set of questions the alien asked was about an integer programming model. The alien asked Dr. Konur to state whether the following claims are right or wrong and explain the answers.
i. If the objective is maximization, the optimum solution of the integer programming problem may give higher objective function value than the optimum solution of the linear relaxation problem.
ii.If the objective is minimization, the optimum solution of the integer programming problem will always give lower objective function value than the solution of the linear relaxation problem.
iii. If the objective is minimization, the optimum solution of the linear relaxation problem can give lower objective function value than the solution of the integer programming problem.
b) The second set of questions the alien asked was about non-linear optimization. The alien asked Dr. Konur to answer the following yes/no questions and explain answers very briefly.
i. Can a local maximum be a global maximum?
ii. Can a local minimum be greater than the global maximum?
iii. Is a global maximum always greater than every other local maximum?
BONUS- Suppose that you have the following binary integer programming model with two decision variables x and y.
Minimize ax+by
Subject to cx+dy>=E
x binary
y binary.
You have a software that can solve any non-linear optimization model, but this software cannot solve optimization models with binary decision variables such as the model given above. Therefore, you want to reformulate the above model by removing the binary constraints. While doing so, you will add constraints that will guarantee that x and y are still binary by adding these constraints (i.e., replacing "x binary" and "y binary" constraints with other constraints, which can be non-linear, that will still assure that x and y will be only 0 or 1). What are these two constraints? Your new model will be as follows:
Minimize ax+by
Subject to cx+dy>=E
??? ???
x>=0, y>=0