Question 1: Box Constrained Linear Program

A box-constrained linear program is a problem of the following form:

max⁡c1x1+⋯+cnxns.t.l1≤x1≤u1l2≤x2≤u2⋱ln≤xn≤unmaxs.t.​c1​x1​+⋯+cn​xn​l1​≤x1​≤u1​l2​≤x2​≤u2​⋱ln​≤xn​≤un​​

In other words, each variable xixi​ is constrained between lower limit lili​ and upper limit uiui​. Given a box constrained LP, write down a linear time $\Theta (n)$ algorithm to find its optimal solution.

Answer (Expected Length: 3 lines)

Your answer here

Question 2: Budget Allocation Problem

There are $n$ communities in a city, C1,…,CkC1​,…,Ck​, with population P1,…,PkP1​,…,Pk​. The average daily income per capita for each community is given by I1,…,IkI1​,…,Ik​. The development budget $B$ dollars of the city is to be distributed between these communities following state law which stipulates the following constraints:

• The budget as a whole must be spent (no borrowing or saving allowed).
• The fair share fraction fifi​ for a community CiCi​ is defined as Pi∑j=1kPj∑j=1k​Pj​Pi​​.
• No community may receive an allocation that exceeds 1.1fiB1.1fi​B or is lower than 0.9fiB0.9fi​B.
• Let xjxj​ be the allocation for community CjCj​. The overall allocation should be progressive to maximize the overall welfare formula given by ∑j=1nPjIjxj∑j=1n​Ij​Pj​​xj​.

Formulate the budget allocation problem as a linear program.

Write down the LP for the data below. Use your favorite solver (Excel, GLPSOL, online solver) to solve the problem for the following data:

IDC1C2C3C4C5Pj5000012000011000013000080000Ij25012520090280IDPj​Ij​​C1​50000250​C2​120000125​C3​110000200​C4​13000090​C5​80000280​​

The total budget in millions is $53$ million.

Answer 2 (Expected Length: 6 lines)

Your answer here

Question 3: 0-1 Integer Linear Programming

A 0-1 integer linear program is an optimization problem involving binary variables x1,…,xn∈{0,1}nx1​,…,xn​∈{0,1}n as follows:

max⁡c1x1+⋯+cnxns.ta11x1+⋯+a1nxn≤b1⋱am1x1+⋯+amnxn≤bmx1,…,xn∈{0,1}maxs.t​c1​x1​+⋯+cn​xn​a11​x1​+⋯+a1n​xn​⋱am1​x1​+⋯+amn​xn​x1​,…,xn​​≤b1​≤bm​∈{0,1}​

You may think of it as a linear program but with variables restricted to take on values in the set $\{0,1\}$.

The 0-1 ILP problem takes as an input (a) description of the problem (variables, objectives and constraints) and (b) limit $L$ and decides whether there exists a solution for the variables satisfying the constraints such that the objective value $\ge L$.

Show that 0-1 ILP problem is NP-Complete. (Hint Directly encode a 3-CNF-SAT clause as an inequality).

Answer (Expected Length: 10 lines)

Your answer here

Question 4: Independent Set

An independent set in a graph $G=(V,E)$ is a set of vertices $I\subseteq V$ such that each edge in $E$ is incident to at most one vertex in $I$. That is, an independent set is a set of vertices where no two vertices are adjacent.

The _$k$-independent set problem_ is to determine if a graph has an independent set of size at least $k$.

(A) Show that the $k$-independent set problem is NP-Complete by reducing from the $3$-CNF-SAT problem.

(B) Show that the $k$-independent set problem is NP-Complete by reducing from the $k$-clique problem.

Answer (Expected Length: 10 lines)

Your answer here

Testing your solutions — Do not edit code beyond this point