# Tag Info

11

Here are two ideas: Minimize $\max_g T_g$. This will naturally even out the productivities of each group. To do this you can minimize a variable $z$ and add the constraint $z \ge T_g \; \forall g$. Add constraints $T_{min} \le T_g \le T_{max}$ where $T_{min}$ and $T_{max}$ are lower and upper bounds on $T_g$, respectively. You will have to determine a "...

8

Since $W$ is a binary variable, it follows that $$\sum_k \delta_k \le W \le 1$$ And so you are in the presence of a clique constraint. @RobPratt shows how to strengthen the second group of constraints in this case, yielding the first constraint. A simple example : take $\delta_k = 0.9$ for every $k$. It is easy to see that such a solution is valid with the ...

7

This is similar to the well known Zebra Puzzle. You can solve it using integer programming techniques as follows: Define binary variables $x_{p,n}^h$ that take value $1$ if and only if player $p\in \{Bill,...,Tony\}$ has nickname $n \in \{Slats,...,Tree\}$ and height $h \in \{6,...,6'6 \}$. So $x_{p,n}^h=1$ if and only if combination $(p,n,h)$ is valid. ...

7

Something like: \begin{align} & c_i \le x_i + M(1-y_i)\\ & c_i \le My_i \end{align} $M$ can be interpreted as an upperbound on $c_i$. If you don't like the big-$M$'s, consider using indicator constraints. See the comments below for some improvements on this!

6

By request, here's the SAS code I used for three different objectives (the first two are commented out with /* and */ delimiters): proc optmodel; num numMachines = 21; num groupSize = 3; set MACHINES = 1..numMachines; set GROUPS = 1..numMachines/groupSize; call streaminit(1); num p {MACHINES} = rand('INTEGER',0,10); print p; var X {...

6

This is a well-known problem with existing heuristics: https://en.wikipedia.org/wiki/Multiway_number_partitioning Edit: For partitioning into groups of limited sizes (eg. $S_{max} \le M/G+1$) see https://en.wikipedia.org/wiki/Balanced_number_partitioning and in the special case of partitioning into groups of $S \le 3$ see: https://en.wikipedia.org/wiki/...

5

Minimize the greatest $T_g$: \begin{align}\min&\quad T_\text{max}\\&\quad T_g \le T_\text{max} \qquad \forall g\end{align} The drawback is that it will minimize $T_g$, and maybe it is not what you want As @RobPratt suggested in the comments, minimize the difference between the greatest and the smallest $T_g$: \begin{align}\min&\quad T_\text{...

5

You can enforce "no more than $w$ workdays in any consecutive $d$-day period" via linear constraints $$\sum_{i=t}^{t+d-1} x_i \le w \quad \text{for all t}$$

5

This problem can be elegantly formulated through Constraint Programming (CP). This problem does not have an objective function: it's a Constraint Satisfaction Problem, not a Constraint Optimization Problem. CP would be a natural choice for this problem, since CP, similar to how humans would solve this problem, relies on a technique called 'inference'. In CP, ...

4

Let $\overline{P}$ be the average (mean) productivity of all machines. The average productivity of a group will be $S\overline{P}$. Let $y_g$ be nonnegative variables defined by the constraints $$y_g \ge T_g - S\overline{P}$$ and $$y_g \ge S\overline{P} - T_g$$ for all $g$. In the solution, $y_g$ will be $\vert T_g - S\overline{P}\vert$. You can minimize $\... 4 I assume that$y$is constrained to the interval$[0,1]$. (You did not state this explicitly.) Let's assume that you have selected values$r_i$such that$0=r_1 < r_2 < \dots < r_n = 1.$If your solver supports SOS2 constraints, you can make$w_1, \dots, w_n$nonnegative variables with the constraint$\sum_i w_i = 1$and declare$\lbrace w_1,\dots,...

4

Adding the last constraint is required to guarantee that only one of the $r_i$ values is selected for $y$. However, you need an additional constraint to make the relationship between $y$, its piecewise linearisation variables and the remaining of the problem constraints (especially $y=f(x)$), such as: $$y = \sum_{i=1}^{n} r_i \times w_i$$

4

You can solve this using a constraint satisfaction/constraint programming (CP) solver (and possibly modeling language). In R, you might use the rminizinc package package, which links to the open-source MiniZinc language, which comes with a number of solvers. CP models (which can be optimization models but are often just constraint satisfaction models) can be ...

3

If you cannot enforce a specific maximum days policy as Rob Pratt suggests, another possibility is to penalize the lumpiness of the work distribution. Pick a window size $d$ (Rob's "$d$-day period"), and add two new variables $y$ and $z$ along with the constraints $$y \ge \sum_{i=t}^{t+d-1} x_i \quad \forall t \in \lbrace1,\dots,D-d+1\rbrace$$and $$... 3 z_{j} \in \{0,1\} equals 1 represents variable b belongs to interval j. You can linearize interval relation as follows:$$ A_{j-1} \cdot z_{j} + \epsilon \cdot z_{j} \le b_{j} \le A_{j} \cdot z_{j} \quad \forall j \in {1,2,3,4}  Here, this leads to 4 binary variables $z_{j}$ and values of ${A_0}$,${A_1}$,${A_2}$,${A_3}$,${A_4}$ are $0$, $a$, $2a$, $... 3 Without the entire problem description it is hard to provide a complete answer, but you will probably need a variable$x_t \in \mathbb{N}$for the number of operators hired at time period$t$. With these variables, and taking into account the fact that once an operator is hired, he is hired for the entire time period, the extra cost at a given time$t\$ ...

2

Optional decision variables are part of the building block of scheduling within CPLEX CPOptimizer. For instance using CP; dvar interval s size 1; dvar interval e size 1; dvar interval itvs optional size 7; maximize presenceOf(itvs); subject to { startOf(s)==1; startOf(e)==8; startBeforeStart(itvs,s); startBeforeEnd(e,itvs); } int isPresent=...

1

If the original problem was feasible, the Benders master problem should never become infeasible. You may have a formulation error in the Benders decomposition, or you may be generating the cuts incorrectly. If you can identify a feasible (not necessarily good) solution to the problem by solving the original formulation, you can use that to locate any errors ...

1

Maybe you could approach it from the opposite direction? Instead of imposing a penalty on uneven distributions, first generate a set of highly even candidate work schedules. Then if the optimizer fails to find a solution, iteratively generate and add less evenly distributed work schedules. This method would allow you to use whatever metric you like for "...

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