1/5
IB2070
Mathematical Programming II
Individual Assignment [12 CATS], 2021
Assignment Instructions
All assignments must be submitted ONLINE via my.wbs by 7pm UK time on the date displayed
against this assessment.
Please ensure that you have inserted a completed assignment coversheet, which must be included
as the first page of your script. This should include your Student ID number, but not your name.
Word Limit
1500 words
Word Count Policy
WBS has a school-wide policy on word counts. This is strictly enforced to ensure consistency across
modules and programme. You can find more information about this policy in your Student
Handbook under Academic Practice – 4i. Word count policy.
This is a strict limit not a guideline: any piece submitted with more words than the limit will result
in the excess not being marked.
Academic Practice
Please ensure you read the full guidelines for Academic Practice in the Undergraduate Handbook
and ensure you understand it. If in doubt, please seek clarification in advance of your submission.
This includes important information on:
x Cheating, plagiarism and collusion
x Correct referencing
x Using internet sources in assessments
x Academic writing
x English Language support
x Word count policy
When you submit this assignment online, you will be required to tick a declaration box indicating
that the work involved is entirely your own. Each assignment will be put through plagiarism software
to identify any collusion or inadequate referencing of materials used from different sources.
We would consider taking action if your work:
2/5
1. is too reliant on the words of particular authors (rather than presenting your ideas in your own
words), if the essay uses the ideas or words of an author without referencing them or putting their
words into quotations (plagiarism).
2. suggests that you have worked very closely with another student or students (unless explicitly
asked to do so by your Module Leader/Tutor) (collusion).
3. includes unreferenced work that you have previously submitted for any accredited course of study
(unless explicitly asked to do so by your Module Leader/Tutor) (self-plagiarism).
Extensions and Self-certification
Late submissions will incur a penalty of 5% for every 24 hour period after the due date and time, i.e.
this begins one minute after the submission deadline (beginning at 7.01pm).
Requests for specific extensions (of up to 15 days) which are typically for longer and more serious
concerns must be submitted via my.wbs ideally 72 hours BEFORE the deadline. Extensions can only
be approved if you clearly detail your circumstances and provide supporting documentation (or a
reason as to why you cannot provide the supporting documentation at the time) as set out in the
Mitigating Circumstances Policy.
Self-certification is a university-wide policy whereby you are permitted an automatic extension of 5
working days on eligible written assessed work without the need for evidence. WBS permits self-
certification for all types of written, assessed works such as essays and dissertations. It is not
permitted for exams, course tests, or presentations.
You can self-certify twice within each year of study, starting from the anniversary of your course
start date. This will cover all eligible written assessments that fall within the self-certification period,
as long as they have not previously had an extension applied. To find out further details about the
self-certification policy please see: https://my.wbs.ac.uk/-/academic/20778/item/id/1244460/.
If you wish to self-certify for an extension of 5 working days, please select ‘Self-certification’ in the
Extension Type field. If you wish to request a longer extension than 5 working days, please leave the
Extension Type as ‘Standard’.
Your assignment instructions begin below.
3/5
IB2070 Mathematical Programming II
ASSIGNMENT [12 CATS], 2021-22
x The assignment is based on the knowledge of the first four weeks of the
module. It is for individual work. Any similarity between different submitted
works will be investigated for plagiarism according to the University’s policy.
x Handwritten solutions will not be accepted. Please write your answers
clearly using LaTeX or MS Word with proper mathematical notation and with
font size 11 or 12 and then convert it to a PDF file. Make sure that each sheet
has your University ID Number and the question number(s). Your work
should NOT exceed 3 pages.
x Submit your work online (in PDF format) on or before 19:00 (UK time),
Monday, 22nd November 2021 via my.wbs. No other submission method
will be accepted. Penalty for late submissions applies automatically.
x An online forum will be open for any requests for clarification on the
assignment, but no requests will be accepted within 24 hours of the
submission deadline.
Social networks such as Facebook are very popular among young people. Friendship
connections on Facebook create huge networks and it is important to analyze the structure
of these networks. Mathematically, such a network is denoted by � = (�,�), where � is the
set of nodes (corresponding to Facebook accounts) and � is the set of edges, each of which is
a pair of nodes (corresponding to a friendship connection between the two accounts). Let
� = {1, … ,�} and each edge in � be represented by an un-ordered pair of nodes {�, �}.
Denote by � = |�|, � = |�| and � = {1, … ,�}. Let binary ��� = 1 if and only if � ∈ � is an
end node of edge � ∈ �. Denote � × � matrix � = �����.
You are provided with a Facebook network data file, SNAP_Network.xlsx, taken from the data
repository of Stanford Network Analysis Project (http://snap.stanford.edu/). Each row,
representing an edge in the network, consists of two numbers and they are the indices of the
two end nodes of the edge. There are � = 4039 nodes indexed by 0, 1, …, 4038 and � =
88234 edges. In this assignment, you only need to analyze a very small part of this given
Facebook network �̅ = (��,��): a sub-network �� = (��,��) containing 20 nodes, where
�� = {� + 1, … , � + 20} ⊆ ��, �� = {{�, �} ∈ ��: �, � ∈ ��}, � = � − �
�
���
� × 232, and � is
your Warwick Student ID number. For example, if your Warwick Student ID number is
2012345, then � = 209, and hence your network �� consists of nodes of indices 210, … , 229.
You need to complete the following three questions for general networks � or your specific
network �� as specified. Additional requirements are given at the end.
4/5
Question 1 (Connected Components: 40%)
Given network � = (�,�), we wish to find all connected components of the network. A
connected component of � is a subset � ⊆ � such that any node � ∈ � is connected to every
other node in � but not any node in � ∖ �. Node � is said to be connected to node � if there is
a path between them in the network �. In terms of Facebook network, it means you could
use friend-of-friend links to go from one account to another within a same community, a
connected component of the Facebook network.
(a) Formulate a binary integer linear programming (ILP) to find all connected components of
general � with binary variables ��� ∈ {0,1} indicating whether (1) or not (0) node � and �
are in a same connected component. Explain clearly all decision variables, all constraints
and the objective function. (Hint: Use parameters � = |�| and � = |�| for your
formulation and take into account the transitive property of the connectedness
relationship.)
(b) Present explicitly the full LP relaxation of your ILP in part (a). Give a counterexample (i.e.,
an instance of general �) or prove that your binary ILP is equivalent to its linear
programming (LP) relaxation in the sense that the LP relaxation problem has an integer
optimal solution.
(c) Find all communities in your Facebook network �� by solving the binary ILP formulated in
part (a), or its linear relaxation if possible, and describe them by listing all accounts in each
community.
Question 2 (Maximum Clique: 30%)
Given network � = (�,�), we wish to find a clique with the largest cardinality. A clique of �
is a subset � ⊆ � such that for all nodes �, � ∈ �, we have {�, �} ∈ �. The cardinality |�| of � is
the number of elements (i.e., nodes) in �. In terms of Facebook network, a clique means a
cluster, a set of members in which each member is a friend of everyone else in the cluster.
(a) Formulate a binary ILP to find a clique with the largest cardinality — maximum clique.
Explain clearly all decision variables, all constraints, and the objective function.
(b) Find the largest cluster in your Facebook network �� using the binary ILP proposed in part
(a) of the problem. What is the size of the cluster? Describe your maximum clique by listing
all its account indices.
Question 3 (Maximum Stable Set: 30%)
Given network � = (�,�) with a set of weights �� for each node � ∈ �, we wish to find a
stable set with maximum total weight — maximum stable set. A stable set is a subset � ⊆ �
such that for any pair of nodes �, � ∈ �, we have {�, �} ∉ �. The total weight of � is ∑ ���∈� . In
terms of Facebook network, a stable set is a set of representatives who can be used for
marketing purpose based on friendship influence. The influencing weight of a representative
� in this case can be defined as �� = �� + 1, where �� is the number of friends of �.
5/5
(a) Formulate a binary ILP to find a maximum stable set. Explain clearly all decision variables,
all constraints, and the objective function.
(b) Find the representative set of your Facebook network �� with the maximum total
influence weight using the binary ILP proposed in part (a) of the problem. What is the size
of the set? Describe your representative set by listing all its account indices.
Additional Requirements:
Attach an appendix, which does not count towards page limit. In the appendix, briefly explain
how you construct your own network �� = (��,��) from the given data file according to the
given instructions. Provide the value of your �, which is dependent on your Warwick Student
ID number, list the node indices in �� and list all the edges in ��. What is the total number of
edges |��| in your network ��?
As another part of the appendix, for the last part (i.e., part c, b, b, respectively) of each of the
three questions, briefly explain how you construct the ILP instances (objectives and
constraints) from input data. Describe all settings you use in Excel Solver to solve your models.
Explain clearly how you use the optimal solutions to these models to answer the questions.
(END OF ASSIGNMENT)