# Tag Info

6

If you want $z=\max(a_1,\dots,a_n)$, you can first enforce $z\ge\max(a_1,\dots,a_n)$ via linear constraints: \begin{align} z &\ge a_i &&\text{for all $i$} \tag1 \end{align} If you cannot rely on the objective to also enforce $z\le\max(a_1,\dots,a_n)$, let $M$ be a small constant upper bound on $z$, let $\ell_i$ be a constant lower bound on $a_i$, ...

5

I actually have quite a few points. As usual, things are not as clear cut. I use advanced bases for LPs very often and they are surprisingly effective and tolerant of quite a few changes in the model. For large problems, often a good strategy is to use the barrier method for the first problem (solved from scratch) and the simplex for subsequent related ...

5

With the natural binary decision variables $x_{s,u}$, $y_{u,g}$, and $z_{s,g}$ you had defined earlier, the problem is to maximize $\sum_u q_u$ subject to \begin{align} q_u &= \frac{\sum_s h_{s,u} x_{s,u}}{\sum_s h_{s,u} (1-x_{s,u})} &&\text{for all $u$} \tag1 \\ \sum_g y_{u,g} &= 1 &&\text{for all $u$} \tag2 \\ \sum_g z_{s,g} &= ...

5

Your constraint matrix is changing with each new problem, so it might not be easy to warm-start ... and it might not be worthwhile, even if you could. One nice thing (among several) about transportation problems is that the origin is feasible, meaning the simplex method has an obvious starting basis. Warm-starting would require you to massage the previous ...

4

Suppose we know an upper bound $M$ for $y$ such that $|y| \leq M$, we can linearize this constraint as follows. First, we introduce a new variable $h \in \mathbb{R}$ with $h = b y$. Then we need to model that $h$ equals $y$ if $b = 1$ and equals $0$ if $b = 0$. For this purpose we add the following linear constraints:  \begin{align} h &\leq b M \tag{1} ...

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

You could try fudging the objective function by replacing any zero cost with a cost of $\epsilon > 0$, where $\epsilon$ is chosen small enough not to cause the selection of a suboptimal solution but large enough that $\epsilon * (z-\max_i a_i)$ does not look like rounding error to the solver. Selecting $\epsilon$ is a bit of an art form, but if this works ...

3

For sake of completeness: An alternative to using an additional binary variable and a big M would be to use an SOS constraint. An SOS constraint specifies a set of variables, at most one of which may be non-zero.

1

Warm starting is used predominantly when solving problems that are only slightly different, and typically when only some coefficients have changed. The idea is that many of the feasible polyhedrons' vertices are shared between the two problems, therefore starting at a vertex that was good at a previous problem will save us pivot operations. If the problems ...

1

Some modeling languages allow max and then you do not need to use big M. With CPLEX in OPL you can write int nbKids=300; {int} buses={30,40,50}; dvar int+ nbBus[buses]; dvar int maxNbOfBusesGivenSize; minimize maxNbOfBusesGivenSize; subject to { maxNbOfBusesGivenSize==max(i in buses) nbBus[i]; sum(i in buses) i*nbBus[i]>=nbKids; } execute ...

1

Based on what you mentioned, you have two jobs with three operations for each. As you do not determine which processing time goes on the specific machine, I assume that each job is processed sequentially on the machines. For minimizing the tardiness of all jobs, one possible schedule is as follows: (Solution with $C_{max} = 11$, $T_{max} = 4$ and \$\sum{T_{i}...

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