代写EBS2043程序设计、代做Software编程语言、c++，Java程序代写代写

日期：2021-01-21 11:59

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:

1. 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,

2. 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

2 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)

1 10.5 14.4 2.2 2.4 32.40

2 8.3 12.6 9.5 3.1 39.80

3 10.2 14.2 5.6 4.2 37.75

4 7.2 10.5 7.5 5.0 34.80

5 12.3 10.1 8.3 6.3 38.20

6 9.2 7.8 6.9 5.1 27.35

Available funds ($1000) 60 70 35 20

1. Formulate the problem as a linear problem, and determine the optimal project mix

that maximizes the total return. Ignore the time value of money.

2. 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?

3. 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 -1.00 0.50 0.30 1.80 1.20

2 -1.00 0.60 0.20 1.50 1.30

3 0.00 -1.00 0.80 1.90 0.80

4 -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.

1. 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.

2. 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)?

3. 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.

1. 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.

2. 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.

3. In the new development the triple and quadruple units together account for at least

25 % of the total. Single units must be at least 20 % of all units and double units

at least 10 %.

4. The tax levied per unit for single, double, triple, and quadruple units is $1000,

$1900, $2700 and $3400, respectively.

5. 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?

1. 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.

2. 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 $)

3 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.

1. 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.

2. 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)

1. 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).

2. 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?

1. Write down an integer linear programming formulation for this problem.

2. Solve it using CPLEX. Describe the optimal solution and interpret it in the context.

What is the optimal value of this solution?

3. 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,

5 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.

1. Write the linear programming model of this problem that would determine the

optimal production planning.

2. Solve it using CPLEX. Describe the optimal solution and interpret it in the context.

What is the optimal value of this solution?

3. 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

000 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.

1. Write the problem as a linear program.

2. Determine the strategy that the firm must apply in order to minimize its costs using

CPLEX.

3. 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:

1. Develop an integer linear program for the given problem. Then, implement it using

CPLEX.

2. For each of the five instances, find the optimal integer solution.

3. 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.

4. For each of the five instances, measure the running times needed to solve both

versions.

5. 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|

6. 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:

1. Present your ILP or algorithm to solve the shortest path.

2. For your specific assignment, find the name of this type of problem in the literature.

Provide the reference(s) you used.

3. Develop an integer linear program for the given assignment. Then, implement it

using CPLEX.

4. For each of the five instances, find the optimal integer solution and provide the

running time (without the time to compute the distance matrix).

5. 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 11x11 grid, together with three possible shapes. Each shape covers

3 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

23 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:

1. One of the regions 1, 11, 21, 31, 41 has been painted black.

2. One of the regions 2, 12, 22, 32, 42 has been painted black.

3. One of the regions 3, 13, 23, 33, 43 has been painted black.

4. One of the regions 4, 14, 24, 34, 44 has been painted black.

5. One of the regions 5, 15, 25, 35 has been painted black.

6. One of the regions 6, 16, 26, 36 has been painted black.

7. One of the regions 7, 17, 27, 37 has been painted black.

8. One of the regions 8, 18, 28, 38 has been painted black.

9. One of the regions 9, 19, 29, 39 has been painted black.

10. 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

2

Introduction to Software in OR / EBS2043 2019–2020 Page 28

Possible answers:

10. Apparently, Sasha made a mistake. The given Sudoku cannot be

solved without ambiguity.

3