Shortest sequence of jobs, with dependencies, subject to capacity constraints

Suppose I have $ n$ courses, some with some prerequisites, and I can take up to $ k$ courses in a semester. I want to compute the least number of semesters needed to complete all courses, while respecting prerequisites.

Equivalently: suppose I have a dag $ G=(V,E)$ , and a positive integer $ k$ . The desired output is a sequence $ S_1,\dots,S_m$ of vertices that minimizes $ m$ , subject to the constraint that $ S_1 \cup \dots \cup S_m = V$ , $ |S_i| \le k$ for all $ k$ , and every edge goes from some set $ S_i$ to $ S_j$ where $ i<j$ (i.e., there is no edge $ v \to w$ where $ v\in S_i$ , $ w\in S_j$ , and $ i \ge j$ ).

Is there a polynomial-time algorithm for this problem?


Approaches I’ve considered:

The obvious greedy strategy is a variant of Kahn’s algorithm is: in each semester, arbitrarily pick $ k$ courses whose prerequisites have all been previously taken, and take those $ k$ courses. Unfortunately, this algorithm is not guaranteed to generate an optimal schedule. For example, in the graph with vertices $ v_1,v_2,v_3,v_4$ and the single edge $ v_1 \to v_2$ , with $ k=2$ this algorithm might generate the schedule $ \{v_3,v_4\},\{v_1\},\{v_2\}$ , which is longer than the optimal schedule $ \{v_1,v_3\},\{v_2,v_4\}$ .

The next natural idea is to modify the above approach by breaking ties in favor of vertices that are part of longer dependency chains. I’m not sure whether this works or not.

Inspired by taking school courses efficiently.

Maximizing a nonnegative linear function over adjacency matrices with node degree constraints

Suppose $ A$ is an $ n$ -by-$ n$ symmetric matrix whose entries are all nonnegative. $ A_{ii} = 0$ for all $ i$ . We want to find an $ n$ -by-$ n$ binary ($ 0/1$ valued) matrix $ X$ that maximizes

$ $ \sum_{ij} A_{ij} X_{ij}$ $

under the constraints that

  1. $ X$ is symmetric ($ X^\top = X$ );
  2. Each row of $ X$ can have at most $ k$ ones (the rest being zero);
  3. The total number of $ 1$ in $ X$ is at most $ m$ .

Here $ k \le n$ and $ m \le n^2$ . I can think of a dynamic programming solution if 2 and 3 are the only conditions. But the symmetry in condition 1 makes it much harder. Does there exist a polynomial algorithm which can achieve multiplicatively constant approximation bound (under conditions 1, 2, 3)? Ideally the constant is universal, not dependent on $ n$ , $ k$ , or $ m$ .

If not, is there any hope for the combination of conditions 1 and 2? The combination of 1 and 3 is trivial to handle.

Thank you.

Formal grammar with constraints on the number of each symbol

I have a language where each type of symbol is only allowed a particular number of times, but the order isn’t important. For example, lets say there are three symbols $ a, b, c$ , and a valid string in the language consists of at most 5 $ a$ , 3 $ b$ and 2 $ c$ characters. So $ ababbc$ is valid, $ ccbbbaaaaa$ is valid, but $ abcabcabc$ is not. I’m struggling to come up with a grammar that satisfies such constraints without resorting to enumerating each possibility. Is it possible to have a concise set of rules that encode these constraints?

algorithm for scheduling tasks based on constraints and feedback loop if possible

I have a list of recurring tasks (1k+ tasks) and I am trying to find a optimal scheduling given a shared constrained resource.

In other respects the tasks are independent of each other

Each task is configured to run recurrently at a given interval (i.e “cron” job). For instance a particular task could have been configured to run at 10 minute intervals while another task could be configured at 20 minutes etc.

The duration of tasks varies (disregarding the shared resource)

Tasks have priorities (importance).

The task interval is in respects to the completion time of the previous run.

Task interval is “soft” and can be offset to accommodate for higher priority jobs.

I can estimate based on historical evidence how many “shares” of the shared resource each task requires

+-----------+-------------+----------+--------------------+-------------------------+ | Task name |  Interval   | Priority | Estimated duration | Estimated resource      | +-----------+-------------+----------+--------------------+-------------------------+ | task1     | 30 minutes  |        1 | 10 minutes         | 10                      | | task2     | 10 minutes  |        3 | 25 minutes         | 90                      | | task3     | 60 minutes  |        4 | 5 minutes          | 25                      | | ...       |             |          |                    |                         | | task 1000 | 180 minutes |        2 | 75 minutes         | 100                     | +-----------+-------------+----------+--------------------+-------------------------+ 

conceptually the architecture should be:

                                                                              +------------+   task list                                                                   |            | +-------------+                                                               | Task x     | |             |                       +-----------+                           |            | |    Task1    |                       |           |      running  tasks------>+            +----------+      +-----------------+ |    Task2    |    choose tasks       |           |               |           |            |          |      |                 | |    Task3    +----------------------->  Scheduler+---------------+           |            |          |      |                 | |    ....     |                       |           |               |           +------------+          |      |                 | |    Task_N   |                       |           |               |               .                   +----->+                 | |             |                       |           |               |               .                          | constrained resource |             |                       +-----------+               |               Many tasks                 |                 | |             |                                                   |               .                   +------>                 | +-------------+                                                   |               .                   |      |                 |                                                                   |           +------------+          |      |                 |                                                                   |           |            |          |      |                 |                                                                   |           | Task z     |          |      +-----------------+                                                                   +----------->            +----------+                                                                               |            |                                                                               |            |                                                                               |            |                                                                               +------------+ 

Optimization Problem to Maximize Points Given Cost Constraints

I have 2 groups of items: A and B. Each item has an associated cost c i and points p i. I need to choose 3 items from group A, and 2 items from group B such that the sum of points of those 5 items is maximized. There is a constraint where I have limited funds to choose those 5 items. Suppose I have $ 500 to work with, then my constraint is:

$ $ 0 \leq 500 – C_{A1} – C_{A2} – C_{A3} – C_{B1} – C_{B2}$ $

and I want to maximize the sum of their points:

$ $ max = P_{A1} + P_{A2} – P_{A3} – P_{B1} – P_{B2}$ $

For some A1, A2, A3, B1, and B2 provide the maximum # of points. I have the data representing the costs and points for each item.

Thanks in advance.

LP – given m constraints for 2 variables find maximal radius of cycle

Given $ m$ constraints for 2 variables $ x_1,x_2$ :

$ d_ix_1 + e_ix_2 \leq b_i$ for $ i = 1,…m$

need to create a linear program that finds the maximal radius of a cycle such that all the points inside the cycle are in the feasible range of the above constraints.

so I know the formula for distance between some $ (x,y)$ and some $ ax +by + c = 0$

then I have tried –

  • $ Maximal$ $ R$ s.t
  • $ d_ix_1 + e_ix_2 \leq b_i$ for every $ i$
  • $ R \leq |d_ix_1 + e_ix_2 – b_i| / {\sqrt{{e_i}^2 +{d_i}^2}}$ for every $ i$
  • $ R \geq 0$

I know the standard linear program doesn’t get absolute value function but obviously we can just have 2 inequalities to get rid of it.

what do you think? and how eventually I can the relevant $ (x_0,y_0)$ that will be the centre of the cycle which $ R$ is its radius are they going to be the specific $ x_1,x_2$ that will makes R maximal I guess?

Encoding set of At-Most-One constraints as a MAX-SAT problem

Assume a set of variable $ V$ = $ \{v_1,…,v_m\}$ .

Given total $ n$ at-most-one (AMO) constraints (at most one element in a given set is true) set [of the below form], over the variable set $ V$ ,

$ $ AMO \, (v_1, v4, \neg v_6, v_{10}) \ … \ AMO \, (v_2, \neg v3, v_7)$ $

Problem: Find an assignment to $  V$   that maximize          the number of satisfiable AMO constraint set.  

I’m unable to represent it as MAX-SAT problem.

Tried so far (Attempt 1): Using hard constraint for each of At-Most-One constraint. This will not work as encoding of $ AMO (v_i,…,v_w)$ will have multiple clauses for each $ AMO$ and all of them have assigned same weight (top weight). A solution to this set may not be the maximal one.

Attempt (2): To fix the above problem, I tried relative clause weight; i.e., for each clause assign weight proportional to size of the clause. This will give preference of assigning satisfying shorter clause. But this do not work in extreme situations like if all clause have same length.

I have experience with SAT solvers but this is my first MAX-SAT problem attempt.

Adding constraints in grammar for Grammatical Evolution

I’m trying to use Grammatical Evolution for creating trading strategies. Each sentence in the grammar when evaluated gives a weight matrix of size n x p . (n is the length of backtesting period and p is the total number of stocks in portfolio)

BNF form of Grammar

<expr>  ::= (<foptr>(<expr>,<expr>,<day>))|          (<fopbi>(<expr>,<day>))|          (<fopun>(<expr>))|          (<expr><matbi><expr>)  |         <var> <foptr> ::= corr | covariance <fopbi> ::= mean |                 sma|             ema <fopun> ::= rank| -1* | 1/  <matbi> ::= + | - | * | / <var> ::= Open|High|Low|Close|Volume <day> ::=  5 | 10 | 15 | 20 

The problem is some expressions in this grammar do not make sense. For example, we cannot have a strategy like $ Volume/Volume$ or $ Low-Low$ , etc. And some of the strategies do not have any physical significance, for example, the strategy $ Volume+Close$ is not valid as the units of volume and close are different. Any suggestions/references on how to add these constraints to the grammar or circumventing this issue in genetic algorithms will be helpful.