Tag Archives: Difficulty 5

Quadratic Programming

Moving along in the Mathematical Programming section.

The problem: Quadratic Programming.  This is problem MP2 in the appendix.

The description: Given a set of pairs (\bar{x},b) of constraints, similar to those in Integer Programming, except the numbers can be rationals instead of integers.  Instead of the single objective vector \bar{c}, we’re also given a second vector \bar{d}, both of rationals.  Our objective bound B is also a rational.

Can we find a vector of rationals \bar{y} that meets all of the constraints and sets the objective function \sum_{i=1}^{m} (c_{i}*y_{i}^{2} + d_{i}*y_{i}) \geq B?

Example: I’ll again try to write a simple example in a format closer to what I think is used in practice:

Maximize 2x_{1}^{2} + 3x_{1} + 4x_{2}^{2} + 5x_{2} such that:

x_{1} \geq 0

x_{2} \geq 0

x_{1} + x_{2} \leq 2

I’m pretty sure this has a trivial solution of x_{1} = 0 and  x_{2} = 2, for an objective score of 26.

Reduction: It’s worth mentioning that this is a “Not known to be in NP” problem, I think because the range of possible rational solutions is too large to nondeterministically guess.  Sahni’s paper reduces from Sum of Subsets.  So we’re given a set S= {s_{1}..s_{n}} and a bound M.  Our QP instance will be have the following objective function: \sum_{i=1}^{n} x_{i}*(x_{i}-1) + x_{i}*s).   Our constraints will be that each x_{i} has to be between 0 and 1 (inclusive) and also \sum_{i=1}^{n} x_{i}*s_{i} \leq M.  Our bound B will be equal to M.

The first half of the objective function makes its contribution to the sum negative if x_{i} is not 0 or 1 (and 0 if it is 0 or 1).  So the only way to get the objective to exactly M is to choose 0/1 values for each x_{i}. The second half of the objective function and the summation constraint force us to create a sum that is as large as possible but not larger than B.   In this case the objective function value is the sum of the subset chosen, which is equal to B if and only if we have a SOS solution.

Difficulty: 5.  The hack to make fractional variable assignments negative is very cool, and easy to explain, but hard to find on your own.  I also think that worrying about quadratics and fractional values for your variables makes this problem harder to handle.

Job-Shop Scheduling

Are you sick of all of these flow-shop problems where we have to split up the tasks of a job into exactly one thing on each processor, progressing through the processors in the same order?  Then today’s problem is for you!

The problem: Job-Shop Scheduling.  This is problem SS18 in the appendix.

Description: We’re given a set of m processors and a set J of jobs.  Each job j in J consists of a chain of tasks, but different jobs can have different numbers of tasks.  The subtasks need to be processed in order, and each task has a processor assignment associated with it, and it’s possible that the subtasks can be assigned to the same processor multiple times, and/or skip some processors entirely.  The only requirement is that two consecutive tasks need to be on different processors (otherwise, we can just merge those tasks together). If we’re given a deadline D, can we schedule all jobs to complete all of their tasks by time D?

Example: Suppose we have three processors and 4 jobs:

  1. Job 1: 1 time on P1, then 2 time on P2, then 3 time on P3, then 2 time on P2
  2. Job 2: 2 time on P1, then 3 time on P2, then 2 time on P1
  3. Job 3: 1 time on P1, then 2 time on P3, then 3 time on P1, then 2 time on P3.
  4. Job 4: 1 time on P4, and that’s it.

Then we can get everything done by time 8 with the following schedule:

P1 1 2 2 3 3 3 2 2
P2 3 1 1 2 2 2 1 1
P3 4 3 3 1 1 1 3 3

Reduction: Garey, Johnson, and Sethi use 3-Partition.  So we’re given a set of 3n elements A, and a bound B.  The Job-Shop instance will have 2 processors and 3n+1 jobs labeled C0 through C3n.  Job C0 has 2n tasks, alternating B time on each processor (so, B time on P1, then another B time on P2, then another B time on P1, and so on).  The rest of the tasks get 0 time on P1 and a1 time on P2.  The deadline is 2nB, which is the time it takes to schedule all of C0.  The paper leaves out the “straightforward” task of showing this reduction actually solves the problem.  I believe them that it is straightforward, let’s take a closer look:

If A has a 3-Partition, then we have a collection of N sets of 3 elements that all add up to B.  Each one of these sets can fit on P2 while C0 is running on P1 (since C0 uses P1 for exactly B time for each task on P1), so we can fit all of the C tasks into the “holes” left by C0.

If we have a schedule that meets the deadline, we know that C0 must be scheduled continually, which leaves the B-sized holes on P2.  For all of the A tasks to be scheduled by the deadline, they have to fit in those holes, which gives us a partition of A.

Difficulty: 5.  The hard part, of course, is coming up with the conversion.  3-Partition isn’t the easiest problem to work with, but the nice features of it (especially that you know that any subset of A that adds to B has exactly 3 elements) make it a good fit here.

I wonder if it’s necessary to have C0 spend B time on both processors.  I understand the need to have C0 running on P2 to separate the partition sets, but wouldn’t it also work (and to my mind, be easier) if C0 took just 1 time (instead of B) each time it ran on P2?

I also wonder if there isn’t an easier reduction that goes straight from Flow-Shop Scheduling.  The reduction can take the Flow-Shop instance, and map it directly to the Job-Shop instance (just because the Job-Shop problem allows you to reuse, reorder, or skip processors with tasks, doesn’t mean it’s required).  Unless I’m missing something, this is a difficulty 2 reduction.  I think the reason they do the 3-Partition reduction in the paper is because they want to show it’s NP-Complete in the case where there are only 2 processors, and the Flow-Shop Scheduling reduction uses 3 processors.

Protected: Flow-Shop Scheduling

This content is password protected. To view it please enter your password below:

Protected: Open-Shop Scheduling

This content is password protected. To view it please enter your password below:

Protected: Linear Bounded Automaton Acceptance

This content is password protected. To view it please enter your password below:

Protected: Consistency of Database Frequency Tables

This content is password protected. To view it please enter your password below:

Protected: K-Vertex Cover

This content is password protected. To view it please enter your password below:

Protected: Consecutive Sets

This content is password protected. To view it please enter your password below:

Protected: Consecutive Ones Submatrix

This content is password protected. To view it please enter your password below:

Protected: Longest Common Subsequence

This content is password protected. To view it please enter your password below: