Homework 2 Write an integer programming model

Homework 2

INSTRUCTIONS
All homeworks will have many problems, both theoretical and practical.
Programming exercises need to be submitted via CANVAS by uploading the files.
Other methods of submission without prior approval will receive zero points.
Write legibly preferably using word processing if your hand-writing is unclear. Be
organized and use the notation appropriately. Show your work on every problem.
Correct answers with no support work will not receive full credit.
1. Write an integer programming model for the following problems (HINT: Think of the problem we
discuss of making a party for people that may hate each other).
(a) The city of SIVAD in the state of AINROFILAC has a problem with very predictable criminals.
The city has n criminals and when k of the criminals all know each other (pairwise acquaintances) they try to form a gang. Assuming that the police knows each pair-wise friendship
for each of the possible pairs of criminals (say these are given e.g., by an undirected network
whose nodes represent criminals, edges represent criminals that know each other), how can the
police decide the maximum possible size that a gang in town?
(b) The police has decided to pay some informants from among the members of the criminal group.
If each bad guy can only report to the police about those criminals he/she is acquainted with,
write an integer program that can help the police compute the minimum number of criminals
they need to be employed as informants.
2. A vertex-cover of a graph G is a set S of vertices of G such that each edge of G is incident with
at least one vertex of S. Formulate a discrete model that given a graph finds a vertex cover with
smallest number of vertices. Explain the reasoning on your variables and constraints. Show that if
M is a matching and S is some vertex cover |S| ≥ |M|. In particular show that
max{|M| : M is a matching of G} ≤ min{|S| : S is a vertex-cover of G}.
HINT: How many vertices do you need to cover just the edges of M?
3. Give an example of an Integer Linear program which has no feasible integer solutions, but its LP
relaxation has a feasible set in R2 of area at least 100.
4. Given a graph G = (V, E) representing say the cities of California connected by highways, we wish to
find out whether there is a tour of the vertices of G (a cycle visiting each vertex exactly once) which
only uses the existing edges in E. Suppose you have a powerful software that solves the Traveling
salesman problem. How would you use that algorithm for the TSP to answer that question? What
costs should you pick on arcs?
5. Modeling an Advertising problem. A company wants to promote its newly developed product
by launching an advertising campaign. There are four advertising options to choose from: TV
Spot, Newspaper, Radio (prime time), and Radio (afternoon); these options are labelled T, N, P, A
respectively. The table below provides, for each type of advertising, the audience reached, the cost
and maximum number of ads per week. The company has a budget of 8000 dolars per week and
seeks to maximize audience reached. However, the company also wants 5 or more radio spots per
week and cannot spend more than 1800 dollars on radio per week. Let T, N, P, A be the decision
variables corresponding to the numbers of ads chosen weekly by the company. Formulate this as a
linear integer programming problem in SCIP making sure to incorporate all the constraints in the
formulation! Solve the problem using SCIP.
6. Computer PROJECT 1: Directed graphs are important for deciding order of activities: A directed graph G = (V, A) can be used to represent the order of actions to be take in a project (task
a needs to be done before b, if there is an arc from a to b. A topological ordering of the vertices is
assignment of the value yi to each vertex such that for every arc ij then yi ≥ yj + 1.
(a) Show that a directed graph has a topological ordering, then there is no directed cycle. Write
a simple discrete model to detect whether a directed graph has a cycle.
(b) A UC Davis student in major X (say Applied Math) has to take certain courses that have
pre-requisites. Create a directed graph whose nodes are all possible Math courses in each of
the majors and there is an arc from course a to course b if course a is a pre-requisite to b. How
big is this graph? Let’s call this the Math-course graph M athC
(c) Write a SCIP model that, given any of the 3 majors of the UC Davis mathematics department,
tells the students at least one good order, one that does not skip pre-requisites, in which to
take their math courses and graduate in minimum amount of time. Can you find at least two
good orders in each of the majors? Make some comments about the structure of the M athC
graph.
7. Computer PROJECT 2: Automatically solving SUDOKU puzzles, predicting difficulty of Sudoku’s:
You probably know the famous sudoku puzzles, but just in case you do not, it consists of a A 9 × 9
matrix A is partitioned into nine 3 × 3 denoted A1, A2, . . . , A9. A few entries are filled in advanced,
then a solution to the sudoku game is an assignment of integers from 1 to 9 to each (unassigned)
entry of the matrix such that each row of A, each column of A and each A1 contains every number
from 1 to 9 exactly once.
• Formulate the problem of finding a solution for Sudoku as a discrete model. (HINT: Think of
the assignment model, but use variables with 3 indices xi,j,k that takes value 1 or 0, depending
on whether entry Ai,j is assigned the number k. )
• Implement the model in ZIMPL/SCIP and use it to solve the following three SUDOKU puzzles,
which one took longer?
• Not all SUDOKU puzzles have a unique solution. If one is not careful when building one,
there may be many solutions. Demonstrate how to you use your model to decide whether the
following SUDOKU has a single solution. Come up with a “bad” SUDOKU that has more
than one solution (i.e., at least two ways to complete the clues given to fill the SUDOKU).