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