# Tag Info

9

You can add an extra binary that equals $1$ if and only if the first constraint is satisfied: \begin{align} x_1+x_2+x_3 &\ge \delta\\ x_1+x_2+x_3 &\le 3\delta\\ x_4+x_5+x_6 &\ge 1 - \delta\\ x_4+x_5+x_6 &\le 3(1 - \delta)\\ \delta &\in \{0,1\} \end{align} If $\delta=1$, the first two constraints become: $$1 \le x_1+x_2+x_3 \le 3$$ And ...

8

Indeed, for the first constraint you can use: $$x+y+z \le 2$$ For the second one, it might be easier to model the contraposition: $$z=0 \quad \Rightarrow \quad x+y \ge 2 \quad \Rightarrow \quad x=y=1$$ This yields: $$1-z \le x \\ 1-z \le y$$

8

How about $$\omega_1 + \cdots + \omega_n \le n-1$$ This way, at most all variables but one of them can take value $1$ simultaneously. In the context of knapsack problems, if each variable models the selection of a given item and that the sum of the weights of the items exceed the knapsack capacity, these inequalities are called cover inequalities.

7

@Kuifje's formulation is correct. Here's a somewhat automatic derivation via conjunctive normal form: $$\lnot \bigwedge_{i=1}^n \omega_i \\ \bigvee_{i=1}^n \lnot \omega_i \\ \sum_{i=1}^n (1 - \omega_i) \ge 1 \\ \sum_{i=1}^n \omega_i \le n-1 \\$$

5

You want to linearize $xy=1-z$. See https://or.stackexchange.com/a/473/500 for a somewhat automatic derivation of a linearization for $xy=z$ via conjunctive normal form. You can then replace $z$ with $1-z$ in the resulting constraints.

5

Introduce a supersource node $s$, a supersink node $t$, arcs from $s$ to each source, and arcs from each sink to $t$. Arc $(s,i)$ has zero cost and capacity equal to supply[i]. Arc $(i,t)$ has zero cost and capacity equal to -supply[i]. All original nodes have supply zero, $s$ has supply equal to the sum of positive supplies, and $t$ has supply equal to ...

4

your model is not feasible and that is why you get no solution. if you comment //forall(i in cD,j in DI,t in T:t==2, f in F)cb10:recievetime[i][t]+(time[i][j]+servicetime[j][t])*K[i][j][f]-Tmax*(1-K[i][j][f])<=recievetime[j][t]; then you ll get some conflicts and relaxations like 72 [0,Infinity] [-6,Infinity] delta[1][2] 72 [0,Infinity] [-10,...

3

Both might provide useful approximations, but minimizing the underestimator $Y$ is a relaxation in the sense that an optimal solution yields a lower bound on the minimum $X$. Bill Cook and his team exploit this idea to solve large TSPs when the edge costs are road distances. The number of pairs is too large to query Google for all of them, so geodetic ...

3

Such a problem is difficult to model and solve following a MILP approach as suggested above. Indeed, the resulting MILP instances will grow quadratically regarding the number of items and bins, while the linear relaxation will be weak. Your problem is closer to a job shop scheduling problem than a basic bin packing problem because of your temporal ...

2

I recommend using binary item-to-bin assignment variables $x_{i,b}$ and continuous nonnegative start time variables $s_i$. You can think of each item as having duration $1$ so that precedence constraints look like $s_i+1\le s_j$ if item $i$ must precede item $j$ and items $i$ and $j$ are assigned to the same bin. You can enforce this as follows: \begin{...

Only top voted, non community-wiki answers of a minimum length are eligible