Description
INSTRUCTIONS
All homeworks will have many problems, both theoretical and practical.
Programming exercises need to be submitted via CANVAS by uploading the les.
Other methods of submission without prior approval will receive zero points.
Write legibly preferably using word processing if your handwriting 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.

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


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 pairwise 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?



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.


A vertexcover 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 nds 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 jSj jMj. In particular show that
maxfjMj : M is a matching of Gg minfjSj : S is a vertexcover of Gg:
HINT: How many vertices do you need to cover just the edges of M?

Give an example of an Integer Linear program which has no feasible integer solutions, but its LP relaxation has a feasible set in R^{2} of area at least 100.

Given a graph G = (V; E) representing say the cities of California connected by highways, we wish to nd 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?

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.

Computer PROJECT 1: Directed graphs are important for deciding order of activities: A di
rected 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 y_{i} to each vertex such that for every arc ij then y_{i} y_{j} + 1.


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.



A UC Davis student in major X (say Applied Math) has to take certain courses that have prerequisites. 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 prerequisite to b. How big is this graph? Let’s call this the Mathcourse graph M athC



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 prerequisites, in which to take their math courses and graduate in minimum amount of time. Can you nd at least two good orders in each of the majors? Make some comments about the structure of the M athC graph.


Computer PROJECT 2: Automatically solving SUDOKU puzzles, predicting di culty 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 A_{1}; A_{2}; : : : ; A_{9}. A few entries are lled 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 A_{1} contains every number from 1 to 9 exactly once.
Formulate the problem of nding a solution for Sudoku as a discrete model. (HINT: Think of the assignment model, but use variables with 3 indices x_{i;j;k} that takes value 1 or 0, depending on whether entry A_{i;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 ll the SUDOKU).