共计 28078 个字符，预计需要花费 71 分钟才能阅读完成。
Assignments
EBS2043
Introduction to Software in Econometrics and Operations
Research
Operations Research Part
Academic Year: 2020/2021
Period: 3
School of Business and Economics
Bachelor
©Academic year 2019–2020 Maastricht University School of Business and Economics
Nothing in this publication may be reproduced and/or made public by means of printing, offset, photocopy
or microfilm or in any digital, electronic, optical or any other form without the prior written permission
of the owner of the copyright.
Introduction to Software in OR / EBS2043 2019–2020 Page 2
Contents
1 General Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 3
1.1 Assignments & Deliverables . . . . . . . . . . . . . . . . . . . . . . . . 3
1.2 Grading . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4
2 Assignments . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 6
2.1 Part A: Linear Programming . . . . . . . . . . . . . . . . . . . . . . . . 6
2.2 Part B: Integer Linear Programming in Logistics . . . . . . . . . . . . . 10
2.3 Part C: Combinatorial Optimization . . . . . . . . . . . . . . . . . . . 15
2.4 Part D: Discrete Network Location Models . . . . . . . . . . . . . . . . 17
2.5 Part E: Logic Puzzles . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22
Introduction to Software in OR / EBS2043 2019–2020 Page 3
1 General Information
1.1 Assignments & Deliverables
For this course you have to model, implement, and solve four optimization problems from
different domains.
• Part A: non-integer Linear Programming and economic interpretations
• Part B: Integer Linear Programming in logistic context
• Part C: Combinatorial Optimization problems
• Part D: Discrete Network Location models
• Part E: Logic Puzzles
Parts A-D each contain four different problems. The problems you have to solve depend
on your student ID. Here is how you find out which problems you have to solve:
• Consider the last four digits of your student ID.
• Replace each digit by the remainder when it is divided by four.
• The obtained sequence of four numbers shows you which problem you have to solve
from Parts A-D.
Here is an example: your student ID is i6214235. The last four digits are 4235. When
each digit is divided by four, the remainders are 0231. Hence you’d have to solve problems
A0, B2, C3, and D1. If you are not sure which problems you have to solve, please let me
know.
If you like logic puzzles, you can replace your assigned problem from part A or B by a
puzzle problem of your choice from Part E (be aware: they may be harder than they look
like).
For each problem you have to submit:
- a written report containing
(a) the description of your LP/ILP model and the answers to the questions of the
assignment (if any),
(b) the solutions and the objective values to the problems with the given data, - the source files of your implementation.
Introduction to Software in OR / EBS2043 2019–2020 Page 4
Important: please adhere to the following conventions:
• name all files that you submit beginning with FirstNameLastName,
e.g. AndreBerger Solutions.pdf, AndreBerger Submission.zip.
• All your written ILP formulations as well as their explanation and the solutions
to the given instances should be written into one pdf document (one section per
assignment).
• the source files should be organized in folders, one for each problem that you submit
• each source file should contain your name and the number of the assignment at the
top as a comment
• At the end, compress all your files in a single .zip folder (no tar, rar or other
compressing formats!).
As a conclusion, you should have a .zip folder containing one pdf document and four
subfolders, each holding the source files of one problem.
The deadline to submit your solutions in Canvas is Thursday, January 21st, 2021, at
23:59pm.
In addition to your submission an individual meeting will be scheduled on Friday, January
22nd, 2021, or on Monday”
January 25th, 2021, where you briefly have to explain one of
your solutions.
1.2 Grading
For each of the four assignments that you submit you can get a maximum number of 25
points (13 points for the report including the model and solutions, and 12 points for the
source code of your implementation).
You need at least 55 points in total to pass this skills course.
• If you have at least 55 points, then your overall grade is the total number of points
divided by 10, rounded to the nearest half integer.
• If you do not have at least 55 points, then you will take the resit: another set of
problems will then be provided to you, and will have to model, implement, and solve
four new problems, as well as comment your results and draw some conclusions.
Introduction to Software in OR / EBS2043 2019–2020 Page 5
1.2.1 Report assessment
The report should be clearly written and structured. More precisely, please be sure that
• the (I)LP is understandable: describe your parameters, variables, objective function,
and constraints in a clear way (check the summation indices if any, etc.); explain
briefly the objective function and the constraints as done in academic papers,
• you answer the questions regarding the interpretation (if any),
• you can also make some comments about your choice for the models or about your
results.
1.2.2 Implementation assessment
Here are some remarks to help you to assess your implementation.
A sufficient implementation
• compiles and runs without errors,
• implements the correct LP or ILP model,
• returns the correct solution, and
• has a human readable source code.
A nice implementation earning more points
• has a clearly readable and understandable source code, i.e.
– the source code is well structured (makes appropriate use of methods and
classes)
– is well commented,
– has reasonable and understandable variable names and method names, and
– avoids unnecessary overhead (unused variables, other warnings, etc.),
• separates the model and the data, i.e. it can also easily be used for the same problem
if some of the data change (preferably by reading the data from a file or through a
user interface), and
• is as memory and run time efficient as possible, and
• outputs the solution in a nice way, preferably it writes the solution to a file if there
are many information.
Introduction to Software in OR / EBS2043 2019–2020 Page 6 - Assignments
2.1 Part A: Linear Programming
Deliverables: a written report with your LP formulation of the problem and the answers
to the questions, an optimal solution to the given instance, and your source codes.
2.1.1 Assignment A0: Investment Plan I
Fox Enterprises is considering six projects for possible construction over the next four
years. The expected returns and cash outlays for the projects are given below. Fox can
undertake any of the projects partially or completely, during the whole 4-year period. A
partial undertaking of a project will prorate both the return and cash outlays proportionally.
Cash outlay ($1000)
Project Year 1 Year 2 Year 3 Year 4 Return ($1000) - 10.5 14.4 2.2 2.4 32.40
- 8.3 12.6 9.5 3.1 39.80
- 10.2 14.2 5.6 4.2 37.75
- 7.2 10.5 7.5 5.0 34.80
- 12.3 10.1 8.3 6.3 38.20
- 9.2 7.8 6.9 5.1 27.35
Available funds ($1000) 60 70 35 20 - Formulate the problem as a linear problem, and determine the optimal project mix
that maximizes the total return. Ignore the time value of money. - Use CPLEX to get the information needed to answer the following questions. For
each question, explain which piece of information enables you to answer.
(a) What are the binding constraints?
(b) What would you gain if the RHS of one of those binding constraints increased
of one unit?
(c) To what extend could the return of project 6 be increased without changing
the optimal solution? - How would you modify your linear formulation to take into account the following
additional features:
Suppose that if a portion of project 2 is undertaken then at least an equal portion of
project 6 must be undertaken. Suppose that any funds left at the end of a year are
used in the next year.
What is the impact of those two new characteristics on your first optimal solution?
Introduction to Software in OR / EBS2043 2019–2020 Page 7
2.1.2 Assignment A1: Investment Plan II
Investor Doe has $10 000 to invest in four projects. The following table gives the cash
flow for the four investments.
Cash flow ($1000) at the start of
Project Year 1 Year 2 Year 3 Year 4 Year 5 - -1.00 0.50 0.30 1.80 1.20
- -1.00 0.60 0.20 1.50 1.30
- 0.00 -1.00 0.80 1.90 0.80
- -1.00 0.40 0.60 1.80 0.95
The information in the table can be interpreted as follows. For project 1, $1.00 invested
at the start of year 1 will yield $0.50 at the start of year 2, $0.30 at the start of year 3,
$1.80 at the start of year 4, and $1.20 at the start of year 5. The remaining entries can be
interpreted similarly. The entry 0.00 indicates that no transaction is taking place. Each
year, Doe has the additional option of investing in a bank account that earns 6.5% annual
profit. All funds accumulated at the end of one year can be reinvested in the following
year. Doe can invest in projects 1, 2, and 4 only at the start of year 1. He can invest in
project 3 only at the start of year 2. However, investing in the bank account is possible
at the start of years 1, 2, 3, and 4. - Formulate the problem as a linear program to maximize the total earned money
at the start of year 5. Implement your mathematical program to get the optimal
solution and optimal value. - Use CPLEX to get the information needed to answer the following questions. For
each question, explain which piece of information enables you to answer.
(a) What are the binding constraints?
(b) What would you gain if the RHS of one of those binding constraints increased
of one unit (without re-running the model)? - How would you modify your linear formulation to take into account the following
additional feature:
Suppose that if an investment is made in project 2, then an amount at least as large
should be invested in project 4.
What is the impact of this new characteristic on your first optimal solution?
Introduction to Software in OR / EBS2043 2019–2020 Page 8
2.1.3 Assignment A2: Erstville
The city of Erstville is faced with severe budget shortage. Seeking a long-term solution, the
city council votes to improve the tax base by condemning an inner-city housing area and
replacing it with a modern development. The project involves two phases: (1) demolishing
substandard houses to provide land for the new development, and (2) building the new
development. The following is a summary of the situation. - As many as 300 substandard houses can be demolished. Each house occupies a
0.25-acre lot. The cost of demolishing a condemned house is $2000. - Lot sizes for new single-, double-, triple-, and quadruple-family homes (units) are
0.18, 0.28, 0.4 and 0.5 acre, respectively. Streets, open space, and utility easements
account for 15 % of available acreage. - In the new development the triple and quadruple units together account for at least
- % of the total. Single units must be at least 20 % of all units and double units
at least 10 %. - The tax levied per unit for single, double, triple, and quadruple units is $1000,
$1900, $2700 and $3400, respectively. - The construction cost per unit for single-, double-, triple-, and quadruple- family
homes is $50000, $70000, $130000, $160000, respectively. Financing through a local
bank can amount to a maximum of $15 million.
Assume that if you get a fractional number of units you can round it up to the closest
integer. How many units of each type should be constructed to maximize tax collection? - Formulate the problem as a linear program to maximize the tax collection. Implement
your mathematical program in CPLEX to get the optimal solution and
optimal value. - Use CPLEX to get the information needed to answer the following questions. For
each question, explain which piece of information enables you to answer.
(a) What are the binding constraints?
(b) What should be the minimum tax levied per unit for the quadruple houses to
become profitable enough?
(c) What would you gain if the loan can be extended until $15.5 million (without
re-running the model)?
Introduction to Software in OR / EBS2043 2019–2020 Page 9
2.1.4 Assignment A3: Urban Renewal
A city will undertake four urban renewal housing projects over the next five years. Each
project has a different starting year and a different duration. The following table provides
the basic data of the situation.
Year 1 Year 2 Year 3 Year 4 Year 5 Cost Annual income
(million $) (million $)
Project 1 Start End 5 0.05
Project 2 Start End 8 0.07
Project 3 Start End 15 0.15
Project 4 Start End 1.2 0.02
Budget
(million $) - 6 7 7 7
Projects 1 and 4 must be finished completely within their durations. The remaining two
projects can be finished partially within their durations, if necessary. Each project must
be at least 25% completed within its duration. At the end of each year, the completed
section of a project is immediately occupied by tenants and a proportional amount of
income is realized. For example, if 40% of project 1 is completed in year 1 and 60% in
year 3, the associated income over the five-year planning horizon is:
0.4 × $50000(for year 2) + 0.4 × $50000(for year 3) + (0.4 + 0.6) × $50000(for year 4)
+(0.4 + 0.6) × $50000((for year 5) = (4 × 0.4 + 2 × 0.6) × $50000.
What is the optimal schedule for the projects that will maximize the total income over
the five-year horizon?
For simplicity, disregard the time value of money. - Formulate the problem as a linear program to maximize the total income over the
five-year horizon. Implement your mathematical program in CPLEX to get the
optimal solution and optimal value. - Use CPLEX to get the information needed to answer the following questions. For
each question, explain which piece of information enables you to answer.
(a) What are the binding constraints?
(b) What would you loose if the budget of year 2 was reduced of 1 million $(without
re-running the model)?
Introduction to Software in OR / EBS2043 2019–2020 Page 10
2.2 Part B: Integer Linear Programming in Logistics
Deliverables: a written report with your ILP formulation of the problem an optimal
solution to the given instance, and your source codes.
2.2.1 Assignment B0: capacitated facility location I
TrendCoats is a manufacturer of jeans and sells its products on the North America market.
Actually, the firm has a plant in Denver with a capacity of 1500 thousands of units, two
warehouses: one in Chicago and one in Salt Lake City, each with a capacity of 1000
thousands of units, and serves markets in Seattle, Sacramento, Houston, Toronto, Miami
and Detroit. The market demand and the transportation costs are shown below:
Transportation Cost Seattle Sacramento Houston Toronto Miami Detroit
per thousand units ($)
Chicago 165 183 124 86 132 67
Salt Lake City 110 75 132 210 153 195
Demand 190 150 90 200 240 130
(thousand units)
The transportation cost of one thousand units between the plant in Denver and the
warehouse in Chicago is $105 and from the plant in Denver to the warehouse in Salt Lake
City is $68. Assume that the jeans are packed in boxes of one thousand units and that
they cannot be split.
The demand is growing dramatically. In order to satisfy this demand, the managers of
TrendCoats have decided to change their network design, several options are studied:
• A new plant can be opened in Wichita (in addition to the low capacity plant already
existing in Denver) or the capacity of the plant in Denver can be increased (a high
capacity plant would take the place of the low capacity one).
• The capacity of the warehouse in Chicago and/or Salt Lake City can be increased
to 2000 thousands of units if needed.
Introduction to Software in OR / EBS2043 2019–2020 Page 11
Plant capacities, market demand, fixed costs incurred by the transformations and transportation
costs are shown below:
Transportation Cost Chicago Salt Lake City Capacity Fixed Cost
per thousand units ($) (thousand units) (thousand $)
Wichita 87 75 1500 2000
Denver (low capacity) 105 68 1500 0
Denver (high capacity) 105 68 2500 1500
Transportation Cost Seattle Sacramento Houston Toronto Miami Detroit Fixed Cost
per thousand units ($) (thousand $)
Chicago 165 183 124 86 132 67 0
(low cap.)
Chicago 165 183 124 86 132 67 250
(high cap.)
Salt Lake City 110 75 132 210 153 195 0
(low cap.)
Salt Lake City 110 75 132 210 153 195 200
(high cap.)
Demand 480 420 220 500 450 320
(thousand units) - Write down the mixed integer linear programming formulation that would minimize
the total transportation and fixed cost of TrendCoats (taking the best decisions
among the propositions above). - Solve the formulation with CPLEX. Describe the optimal solution and interpret
the value of the variables in the context. Give the optimal value associated to this
solution.
Introduction to Software in OR / EBS2043 2019–2020 Page 12
2.2.2 Assignment B1: capacitated facility location II
SC Consulting, a supply chain consulting firm, must decide on the location of its home
offices. Its clients are located primarily in the 16 states listed in the table below. There
are four potential sites for home offices : Los Angeles, Tulsa, Denver and Seattle. The
annual fixed cost of locating an office in Los Angeles is $165428, in Tulsa it is $131 230,
in Denver it is $140 000, and in Seattle it is $145 000. The expected number of trips to
each state and the travel costs per trip from each potential site to each state are shown
in the table below.
State Los Angeles Tulsa Denver Seattle Number of trips
Washington 150 250 200 25 40
Oregon 150 250 200 75 35
California 75 200 150 125 100
Idaho 150 200 125 125 25
Nevada 100 200 125 150 40
Montana 175 175 125 125 25
Wyoming 150 175 100 150 50
Utah 150 150 100 200 30
Arizona 75 200 100 250 50
Colorado 150 125 25 250 65
New Mexico 125 125 75 300 40
North Dakota 300 200 150 200 30
South Dakota 300 175 125 200 20
Nebraska 250 100 125 250 30
Kansas 250 75 75 300 40
Oklahoma 250 25 125 300 55
Each consultant is expected to take at most 25 trips each year. If there are no restrictions
on the number of consultants at a site and the goal is to minimize costs, where should
the home offices be located and how many consultants should be assigned to each office ?
What is the annual cost in terms of facility and travel? - Write down an integer linear programming formulation for this problem.
- Solve it using CPLEX. Describe the optimal solution and interpret it in the context.
What is the optimal value of this solution? - If, at most, 10 consultants are to be assigned to a home office, where should the
offices be set up? How many consultants should be assigned to each office? What
is the annual cost of this network?
Introduction to Software in OR / EBS2043 2019–2020 Page 13
2.2.3 Assignment B2: Production planning I
A vacuum cleaner manufacturer tries to plan ahead in order to effectively address the
seasonal variation appearing in the annual demand of its products. A planning horizon
of 6 months is used. The demand forecast for the next six months along the number of
working days are as in Table 1.
Month Demand Forecast No. of Working Days
Jan. 1800 22
Feb. 1500 19
March 1100 21
April 900 21
May 1100 22
June 1600 20
Table 1: Demand forecast and number of working days per month
The associated cost break-down is as described in Table 2.
Item Cost
Material $50 per unit
Inventory Holding $5 per unit per month
Cost of Subcontracting $120 per unit
Hiring and Training $1000 per worker
Layoff $1500 per worker
Regular Labor cost per hour $15 per employee per hour
Overtime labor cost per hour $20 per employee per hour
Table 2: Costs
At the end of December, the company has an inventory of 400 units and 38 workers, each
of whom works 8 hours of non-overtime per day. In order to produce one vacuum cleaner, - hours of labor work are required. At the end of each month, the company wants to have
a minimum inventory level of a quarter of the corresponding demand. - Write the linear programming model of this problem that would determine the
optimal production planning. - Solve it using CPLEX. Describe the optimal solution and interpret it in the context.
What is the optimal value of this solution? - Currently, backorders are allowed. All stock-outs are backlogged and supplied from
the following months’production. The backorder cost is $7 per unit and per month.
However, assume that at the end of the sixth months, all the demands are satisfied.
Adapt the previous model to consider the possible backorders and determine the
optimal production planning. What are the costs over the 6 months in this case?
Introduction to Software in OR / EBS2043 2019–2020 Page 14
2.2.4 Assignment B3: Production Planning II
A local canning company sells canned vegetables to a supermarket chain in the Minneapolis
area. A typical case of canned vegetables requires an average of 0.2 day of labor to
produce. The aggregate inventory on hand at the end of June is 800 cases. The demand
for the vegetables can be accurately predicted for about 18 months based on orders received
by the firm. The predicted demands (in hundreds of cases) for the next 18 months
are as follows :
Month Demands workdays Month Demands workdays
July 23 21 April 29 20
August 28 14 May 33 22
September 42 20 June 31 21
October 26 23 July 20 18
November 29 18 August 16 14
December 58 10 September 33 20
January 19 20 October 35 23
February 17 14 November 28 18
March 25 20 December 50 10
The firm currently has 25 workers. The cost of hiring and training a new worker is $1 - and the cost to lay off one worker is $1 500. An employee works 8 hours per day and
is paid $10 per hour. The firm estimates a cost of $2.8 to store a case of vegetables for a
month. The material to built one case of vegetables costs $0.5. The firm can also choose
to subcontract the production for $24 per case. They would like to have 1 500 cases in
inventory at the end of the 18-month planning horizon. - Write the problem as a linear program.
- Determine the strategy that the firm must apply in order to minimize its costs using
CPLEX. - Analyze how the number of units subcontracted changes when the price of subcontracting
increases or decreases. Show this relation on a chart in the written
report. Determine the limit price above which it is not interesting to subcontract
the production and the limit for which it is more interesting to subcontract only.
Introduction to Software in OR / EBS2043 2019–2020 Page 15
2.3 Part C: Combinatorial Optimization
For your assignment, you are provided with five instances that you have to solve. You are
supposed to: - Develop an integer linear program for the given problem. Then, implement it using
CPLEX. - For each of the five instances, find the optimal integer solution.
- For each of the five instances, find the optimal solution to the corresponding linear
programming relaxation, i.e. when all integer/binary variables are relaxed to take
non–negative real values. - For each of the five instances, measure the running times needed to solve both
versions. - For each of the five instances, determine the GAP of the solution of the relaxation
compared to the optimal integer solution. The GAP is defined as the ratio between
the difference of the best bound (provided by the relaxation in this case) and the best
integer solution value over the best integer solution value. The GAP is expressed in
percentages and measures how good a solution is (the closer to 0, the better):
|best relaxation value − best integer value|
|best integer value| - For one of the five instance, describe the optimal solution in the context (= in
words).
Deliverables: a written ILP formulation of the problem, the following table (filled with
values), a brief description of the results in the table, the description of one optimal
solution in the context of the assignment, and your source codes.
Instance Optimal Run time Optimal Run time GAP
value (ILP) ILP (ms) value (LP) LP (ms)
1
2
3
4
5
Introduction to Software in OR / EBS2043 2019–2020 Page 16
2.3.1 Assignment C0 – The Bin Packing Problem
Given a set of items I = {1, . . . , n}, each having a size si ∈ [0, 1] for i ∈ I, determine an
allocation of items to bins of size 1, that minimizes the number of bins used.
2.3.2 Assignment C1 – The Knapsack problem
Given a set of items I = {1, . . . , n}, each having a required space si
in cm2
, a duration
di
in minutes, and a value vi ∈ R - for i ∈ I. The plant has an available space of 300
cm2 and a workforce working 8 hours. Select the items such that the value of the selected
items is maximized.
2.3.3 Assignment C2 – Minimizing weighted completion times
Given a set J = {1, . . . , n} of jobs, each having a processing time pj ∈ R - and a weight
wj ∈ R
+, determine an allocation of the jobs to a single machine that minimizes the
weighted sum of completions times of the jobs, i.e. P
j∈J wjCj
, where Cj
is the time that
job j is finished.
Hint: you have to declare as a decision whether a job precedes another one.
2.3.4 Assignment C3 – The Scheduling Parallel Machines Problem
Given a number m of machines, and a set J = {1, . . . , n} of jobs, each having a processing
time pj ∈ R
+, determine an allocation of the jobs to the machines that minimizes the
makespan of the schedule, i.e. the finish time of the last machine.
Introduction to Software in OR / EBS2043 2019–2020 Page 17
2.4 Part D: Discrete Network Location Models
For the assignment, you need first to be able to solve the shortest path problem:
Given an undirected graph G = (V, A), arc weights w : A → R
+, a source s ∈ V and
a destination t ∈ V , determine the shortest path in G between s and t. Then, use this
algorithm to determine the shortest distance between any pair of vertices in V . Present
your results as a distance matrix.
Using this as a tool to compute a distance matrix, four location problems are then presented.
For your assignment, you are provided with five instances that you have to solve. You are
supposed to: - Present your ILP or algorithm to solve the shortest path.
- For your specific assignment, find the name of this type of problem in the literature.
Provide the reference(s) you used. - Develop an integer linear program for the given assignment. Then, implement it
using CPLEX. - For each of the five instances, find the optimal integer solution and provide the
running time (without the time to compute the distance matrix). - For one of the five instances, interpret the solutions in the actual context.
Deliverables: a written report with all the above elements, and your source codes.
Introduction to Software in OR / EBS2043 2019–2020 Page 18
2.4.1 Assignment D0 – Facility location
The customers and the potential facilities of a country have been aggregated in n regions.
Some of the regions are connected to each others through a set of m arcs.
A company would like to open p facilities among these regions to supply all the customers
in minimizing the total distance to travel.
We assume that all the facilities have the same fixed cost to get opened and that they
have an infinite capacity. A customer can be supplied by only one facility.
Write down a linear model for this problem. Solve it with p = 2, 3, 4. Include the following
table filled in in your report. Comment the results.
Optimal value Run time (ms)
Introduction to Software in OR / EBS2043 2019–2020 Page 19
2.4.2 Assignment D1 – Hospital location
Inhabitants have been grouped in n regions. Some of the regions are connected to each
others through a set of m arcs. We want to locate new hospitals in some regions such
that each person in each region can reach at least one of them in less than a maximum
distance M. Determine the minimum number of hospitals to build.
Write down a linear model for this problem. Solve it with M = 3, 5, 10. Include the
following table filled in in your report. Comment the results.
Optimal value Run time (ms)
Introduction to Software in OR / EBS2043 2019–2020 Page 20
2.4.3 Assignment D2
CareFor is a well-known supermarket chain. The managing director is aware that most
people will go shopping in the closest supermarket. Having this policy in mind, he wants
to minimize the maximal distance that a customer from any region have to travel to find
a CareFor supermarket. Help him to determine where to locate p CareFor supermarkets.
Write down a linear model for this problem. Solve it with p = 2, 3, 4. Include the following
table filled in in your report. Comment the results.
Optimal value Run time (ms)
Introduction to Software in OR / EBS2043 2019–2020 Page 21
2.4.4 Assignment D3
Suppose that you have 2 franchise outlets to locate in this same country. To reduce
cannibalization among stores you want to maximize the minimum distance between any
pair of facilities.
Write down a linear model for this problem. Solve it with p = 2, 3, 4. Include the following
table filled in in your report. Comment the results.
Optimal value Run time (ms)
Introduction to Software in OR / EBS2043 2019–2020 Page 22
2.5 Part E: Logic Puzzles
This section contains puzzles, which can be solved using integer linear programmes. In
this section you can work on the problem of your choice. All problems are challenges
previously posted on the math calendar (www.mathekalender.de).
2.5.1 Assignment E0 – Color the areas
Use integer linear programming to solve problem 23 Mondrian of the math calendar
(shown at the end of this document).
2.5.2 Assignment E1 – Midoku
Use integer linear programming to solve problem Midoku of the math calendar (shown at
the end of this document).
Introduction to Software in OR / EBS2043 2019–2020 Page 23
2.5.3 Assignment E2 – Fill the grid
Below you can see an 11×11 grid, together with three possible shapes. Each shape covers - or 4 cells of the grid.
A feasible solution for this problem is an arrangement of the shapes on the grid, such that
each cell is covered exactly once. All shapes can be rotated by multiples of 90 degrees or
mirrored vertically or horizontally (thus there are actually nine different shapes). Obviously,
for an NxN grid with even N, it is sufficient to use only the square shape. For odd
N, the triangle shape has to be used as well. It is not allowed to use a shape in a way,
such that one of the corners lies outside of the grid.
For odd N, the goal of the optimization problem is to find a cover of the NxN grid with
as few of the triangle shapes as possible.
Develop and implement an integer linear program to solve this problem for odd N.
Deliverables: a written ILP formulation of the problem, a print of the solution for N = 11,
your source codes.
In addition, you can try to find out whether there is a formula for the optimal value as a
function of N.
Introduction to Software in OR / EBS2043 2019–2020 Page 24 - Mondrian
Authors: Hajo Broersma (Universiteit Twente), Cor Hurkens (TU Eindhoven)
Challenge
Mondrian the painter-elf has designed a new Christmas card, which he has
subdivided into 44 regions. Mondrian calls two regions adjacent if they share
a horizontal or a vertical edge. (For instance: Region 2 is adjacent to regions
1, 10, 13, 14 and 3. But region 2 is not adjacent to region 15, as these two
regions only share a single point.)
Mondrian paints each of the regions with one of the four colors red, blue,
yellow, and black so that no two adjacent regions have the same color. Mondrian
starts by painting one of the regions black and thereby depletes his
black color pencil. Hence the remaining 43 regions are painted red, blue, and
yellow. It turns out that in the end the total red area, the total blue area,
and the total yellow area all are equally large.
1
Introduction to Software in OR / EBS2043 2019–2020 Page 25
We want to know: Which of the regions has been painted black?
Artwork: Friederike Hofmann
Possible answers: - One of the regions 1, 11, 21, 31, 41 has been painted black.
- One of the regions 2, 12, 22, 32, 42 has been painted black.
- One of the regions 3, 13, 23, 33, 43 has been painted black.
- One of the regions 4, 14, 24, 34, 44 has been painted black.
- One of the regions 5, 15, 25, 35 has been painted black.
- One of the regions 6, 16, 26, 36 has been painted black.
- One of the regions 7, 17, 27, 37 has been painted black.
- One of the regions 8, 18, 28, 38 has been painted black.
- One of the regions 9, 19, 29, 39 has been painted black.
- One of the regions 10, 20, 30, 40 has been painted black.
2
Introduction to Software in OR / EBS2043 2019–2020 Page 26
MATH
KALENDER
Midoku
Author: Ariane Beier (MATH+ School Activities)
Challenge
Last year, directly after Christmas, elf Sasha was given a Sudoku puzzle by
her friend Alex. The puzzle was intended to entertain her on the long train
ride from the North Pole to her home town. But, as soon as she sat down in
the comfortable train seat and the coach started moving soothingly, she fell
asleep—after all, she just had worked her way through a very exhausting
Christmas season—and woke up only shortly before arriving at her destination.
Thus, Sasha did not even attempt to solve the puzzle.
Back home, Sasha forgot to empty her pants’pockets before putting them
into the washing machine. When she hung the pants up to dry, she pulled
out a piece of paper with only the following on it:
Introduction to Software in OR / EBS2043 2019–2020 Page 27
Although Sasha was pretty sure that there were more digits given on the
Sudoku grid before its involuntary bath and roller coaster ride in the washing
machine, she was not able to recollect them. However, she did remember
the rules of this special Sudoku:
(i) The normal Sudoku rules apply, i. e. every row, every column, and
every 3 by 3 subgrid contains the digits from 1 to 9 exactly once.
(ii) Any two cells separated by a knight’s (see Fig. 1(a)) or king’s (chess)
move (see Fig. 1(b)) cannot contain the same digit.
(iii) Any two orthogonally adjacent cells (see Fig. 1(c)) cannot contain
consecutive digits (e. g. not 1 & 2 or 5 & 6).
(c) Every y is orthogonally
adjacent to the x.
Figure 1: Special rules of the given Sudoku.
Always tempted by a tricky challenge, Sasha whipped out her pencil and
started to ponder. After 25 minutes of heavy thinking, she was able to finish
the Sudoku.
What digit did Sasha write down in the uppermost right corner?
Artwork: Friederike Hofmann
正文完
