Deadline: 2022-04-16 24:00

• Another known method for solving NP-complete problems is to bring the problem back to another well-known NP-complete problem. If we have an effective heuristic solver for a well-known problem, we can usually achieve better results than with brute force. In this exercise, we slightly extend the previous week's CLIQUE problem, and solve the MAXCLIQUE problem using integer linear programming tools. In CLIQUE we had to decide if a \(k\)-set of vertices is a complete subgraph in a given graph or not. In MAXCLIQUE we have to find the max value of \(k\) for which a \(k\)-clique exists. We solve the integer linear program with the PuLP Python package. Install it with the built-in package manager pip or pip3 using the command

  pip install pulp
  

• In the file pulpexample.py we give a simple example for solving the integer programming problem \begin{align*} \max\, x_0 + x_1,\\ \text{where } x_0, x_1 \in \mathbb{Z},\\ x_0 \ge 0, \\ x_1 \ge 0, \\ 2 x_0 + x_1 \le 10, \\ x_0 + 2 x_1 \le 10, \end{align*} and write out the solution to the standard output. Let's study this program! The PuLP package documentation can help you understand it.
• Let's write a program to solve the MAXCLIQUE problem!
  1. Read the input of the problem, that is the simple non-directed graph \(G\) and \(k\) from a file having the same format as in the previous exercise, although \(k\) will not be used here. As with the previous task, the program will receive the file name as a command line argument.
  2. Let's define MAXCLIQUE as an integer programming task.
  3. Program the integer programming problem with the PuLP package and call the solver.
  4. Write the size of the maximum clique and the elements of such a set to the standard output. PuLP returns the value of the objective function as a floating-point number, so round it before printing. Follow the next format:

       Size of the max clique: 4
       Vertices of a max clique: 2, 5, 7, 8
     	

  5. print(prob.solver) prints out the name of the solver. Instead of prob.solve() please use that name in the argument of this function like in prob.solve(pulp.apis.coin_api.PULP_CBC_CMD(msg=0)) to prevent messages from being displayed.
• Run the program with the inputs in the previous task. Although we are now solving a more demanding task, the integer programming is much faster than brute force.