0

I'm studying computer programming. Our lecturer in one of the courses gave us the following assignment and told us to learn the material needed to solve it. I'm not a mathematician and would like to minimize effort. How can I solve this problem? Or, rather, what are the steps?

Given a nonnegative $c$, a vector of $1$'s $b$, I need to minimize $c^Tx$ under the following constraints:

  1. $Ax\geq b$
  2. $x_j\in \left\{0,1 \right\}$

Here $A$ is a matrix of $0$s and $1$s such that each row has at most $k$ sequences of $1$s, with $k$ given in advance.

Find a $k$ approximate.

user417105
  • 11
  • 5
    I'm going to minimize my effort and suggest you get a textbook. – Paul Feb 16 '17 at 21:16
  • 1
    There is not single procedure. There exist different methods for solving a linear programming problem, and the selection and customization of a method for a particular problem is rather an art than a science.

    Furthermore, your restriction $x \in {0, 1}$ makes the problem a 0-1 Linear Program (a special case of Integer programming), and the parameter $k$ does not appear anywhere in your problem statement.

    This problem is in the field of Combinatorial Optimization, which is a difficult area of research in and of itself. See the book by Papadimitriou and Steiglitz for known methods.

     – avs Feb 16 '17 at 21:18
  • As a broad sketch, one puts a linear program in standard form (if not already so) by certain steps, creating a tableau similar to how a linear system of equations is represented by an augmented matrix. Then further steps are made (similar to elementary row operations) that drive the tableau to a state where the solution can be read off by inspection (much as the reduced row echelon form of an augmented matrix tells us the solutions of the original linear system). – hardmath Feb 16 '17 at 21:20
  • 1
    @avs there might be a polynomial approximation scheme for this particular case. – Vincent Feb 16 '17 at 21:24
  • 1
    Is there something omitted in the last sentence? "Find a $k$ approximate" doesn't sound to me like an actionable request. – hardmath Feb 16 '17 at 21:26
  • @Vincent, I'd be interested to learn more about that. – avs Feb 16 '17 at 21:29
  • @avs if I understand the question right, this is not general 0-1 programming. If $k=1$ then $A $ verifies the consecutive ones property and is totally unimodular – Vincent Feb 16 '17 at 21:33
  • @Vincent, I think the question still contains a typo: "at most $k$ sequences" should be "at most $k$ instances". If so, you are right about this being a special case. – avs Feb 16 '17 at 21:38
  • @avs sequences looks alright to me. – Vincent Feb 16 '17 at 21:46

1 Answers1

0

First, calculate a solution $x$ of the relaxed problem ($x_i \in [0,1]$) of cost $c^*$ thanks to the simplex method. This solution has a cost smaller than the cost of the $\{0,1\}$ optimal solution.

Initiate $x'=0$

Then, for each row, consider the sequence of ones $S_j$ such that $\sum_{i \in S} x_i $ is maximal. Its value is at least $\frac {1}{k}$ (according to the pigeon hole principle).

If $\exists i \in S, x_i=1$, set $x'_i$ to $1$. Otherwise, round up the $x'_i $ with the smallest cost function to $1$.

By construction, you have $cx'\leq k c^*$

You can also think about a more elaborate version of this. For instance, after each time you round up an $x_i$, you can calculate a new relaxed solution with this particular $x_i $ fixed to 1.

Following comment : since $\{x \in \{0,1\}^n|Ax\leq b \} \subset \{x \in [0,1]^n|Ax\leq b \}$, we have

$\min \{cx| x \in \{0,1\}^n,Ax\leq b \} \geq \min \{cx | x \in [0,1]^n,Ax\leq b \}$

Vincent
  • 2,318
  • Thank you very very much! I'm having trouble following your solution and would very much appreciate additional details. I will try to fill in the gaps in the upcoming few hours, but if you have time later - much appreciated. – user417105 Feb 16 '17 at 22:55
  • You minimise something on a larger set. This is why the solution of the relaxed problem is always lower than the solution of the integer problem. – Vincent Feb 17 '17 at 14:02
  • Its look fantastic,but yet i think i miss something. Just for better understanding cx' is the approximation returned value. But why can we assume that OPT≤cx' ? while OPT is the cost of the orig problem(with the binary constraints ). we started with smaller cost function(c) by the solution of the relaxed problem so its seems crucial to show that OPT≤cx' . I understood that by construction, i have cx′≤kc≤kOPT. Vincent thanks :) its really helpful ! – user417105 Feb 17 '17 at 14:24