New answers tagged

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{...


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,...


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.


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 $$


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 ...


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 ...


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 ...


2

Most solvers will accept additional information about variables like $B(i)$. Some may be useful. Here are some examples for Gurobi, which let you influence the search: You can use the parameter BranchDir to tell Gurobi to always first explore the "up" branch. This means that non-zero values will be tried first. Unfortunately, this is a global ...


4

Consider the following tiny example. You have two factories, one warehouse and two product. Factory 1 can produce both goods in sufficient quantity to meet demand but has a very large cost coefficient. Factory 2 only produces the second product, with adequate capacity and a small cost coefficient. The optimal solution to the original problem is to ship ...


Top 50 recent answers are included