Tag Info

3

Here's one possible formulation, where $a_1,\dots, a_n$ are the values of the $n$ integers. Let binary decision variable $x_{i,j}$ indicate whether integer $i$ is assigned to subset $j\in\{1,\dots,k\}$. The problem is to maximize $z$ subject to \begin{align} \sum_j x_{i,j} &= 1 &&\text{for all $i$} \tag1\\ \sum_i a_i x_{i,j} &\ge z &&...

6

If I understand correctly, the following enforces your desired behavior: \begin{align} y_1 &= d_1 \\ y_2 &= d_2 \\ y_3 &= d_3 \\ y_4 &\ge d_1 + d_2 - 1\\ y_5 &\ge d_1 + d_2 + d_3 - 2\\ \end{align} If you also want to enforce $y_4 \implies (d_1 \land d_2)$ and $y_5 \implies (d_1 \land d_2 \land d_3)$, then include these additional ...

4

There are certainly different ways of achieving what you want. Here is how I would proceed: Start by predefining the set of all possible schedules which satisfy your constraints $2,3,4,6$. Although there are many, I believe that with your constraints, it may be not too difficult to derive them somewhat automatically. Here is a subset of them in the table ...

3

Yes, your proposal suffices. But the published second constraint is stronger, yielding a tighter formulation. You can think of it as a lifting obtained by using the first constraint.

3

I recommend extending Paul's single-commodity formulation to a multicommodity formulation with $k$ commodities. Let binary variable $z_{i,r}$ indicate whether node $i\in R \cup N$ is assigned to tree $r\in R$. The idea is to send one unit of commodity $r$ from the dummy source node $0$ to node $i$ iff $z_{i,r}=1$. The problem is to minimize $\sum_e c_e ... 2 There are flow models for the MST problem that can easily be adapted to the$k$-rooted MST. For each edge$e=(i,j)$in the graph, create a binary variable$x_e$(1 if the edge is used in a tree, 0 if not) and two nonnegative variables$y_{ij}, y_{ji}$representing flows along the edge in either direction. Connect them via the constraints$y_{ij} \le n x_e$... 2 I'm still not sure I understand the question, but I'll suggest an answer to what I think is being asked. I'm going to assume that an a priori upper bound$O$exists for$o_t$. To keep what follows somewhat compact, I'm going to assume that$\mathcal{M} = \lbrace 20, 21, 22, 23\rbrace$and$O=6$. To start, for each$t\in T$generate a random sample of$O\$ ...

Top 50 recent answers are included