New answers tagged integer-programming
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
