10
Your constraint is equivalent to
$$x_i \le f(x_j) \quad \text{for $j<i$},$$
so it is linear if $f$ is linear.
9
Here's another single-solve solution. Replace each original variable $x_n$ with a sum of two variables, $x_n=y_n + z_n$, where $y_n$ is integer-valued and $z_n\in [0,1]$. Now define $\lbrace z_1,\dots, z_n\rbrace$ to be a type 1 special ordered set (SOS1). Assuming the solver supports SOS1 constraints, you'll end up with a solution in which at least $n-1$ of ...
8
An alternative approach that requires only one solve and no modification of the model is to modify branch and bound to prune by integrality when at most one integer variable takes a fractional value (rather than the usual requirement that all integer variables are integer-valued). You would also need to disable any presolve/cut routines that assume ...
4
Try adding valid constraints
$$
y_{i,j} \le \sum_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,k} \quad\text{for $(i,j)$ such that $\hat{y}_i = 0$ and $j \in \tilde{V}\setminus\{i\}$}
$$
that enforce the logical implications
$$(y_{i,j} \land \lnot\hat{y}_i \land [j \in \tilde{V} \setminus\{i\}]) \implies \bigvee_{(i,k): k \in \tilde{V} \setminus \{j\}} y_{i,...
4
Let us introduce binary variables $y_{ij}$ along with the constraint $y_{ij} + y_{ji} \le 1$ for all $i\neq j$. Add the constraints $$x_j - x_i \le My_{ij}\quad \forall i\neq j,$$ where $M$ is an upper bound on the difference between largest and smallest $x$ value. This ensures that $y_{ij}=1$ if $x_j > x_i$. The question does not indicate whether ties in ...
4
If you are looking for a way to ensure (in a MILP model) that a graph with $p$ nodes is connected, a common approach is to treat each edge as a pair of directed edges (adding flow variables $x_{ij}$ and $x_{ji}$ for each edge $(i,j)$, choose one node arbitrarily to have supply $p-1$ of a phantom commodity, and assign a demand of $1$ to every other node. You ...
3
Extending Robs answer slightly, taking into account that you asked about ILP (which I interpret as mixed-integer linear program), the constraint is MILP-representable as long as $f$ is MILP-representable (thus allowing you to have piecewise affine functions such as min/max/abs/general pwa etc)
1
Your question prompted me to suggest multiple answers, if you would like me to elaborate on one of them please tell me which one in a comment.
Would be fine with $A_{ij}$ matrix which tells you if $x_i$ is before $x_j$
or otherwise, that would be a lot simpler to implement.
If you don't have individual constraints on $x_1$, $x_2$ (they can be
any employee, ...
Only top voted, non community-wiki answers of a minimum length are eligible