It is worth noting that this formulation can be derived somewhat automatically by writing the logical proposition in conjunctive normal form: \begin{align*} & z \iff x \wedge y \\ & \left(z \...

QSopt-Exact by Applegate, Cook, Dash, and Espinoza

Search for orienteering problem or prize-collecting TSP.

First, some special cases: If $S=\{c\}$, fix $x=c$. If $S=\{0,1\}$, declare $x$ to be binary. If $S=\{a,b\}\not=\{0,1\}$, introduce binary variable $y$ and impose linear constraint $x=a(1-y)+by$. If $... View answer Accepted answer 16 votes Derivation via conjunctive normal form: \begin{equation} x_1 \implies \underset{i=2}{\overset n{\lor}} x_i \\ \neg x_1 \bigvee \underset{i=2}{\overset n{\lor}} x_i \\ 1 - x_1 + \sum_{i=2}^n x_i \ge 1 \... View answer Accepted answer 14 votes Here is a simpler symmetry-less formulation based on the one proposed by @RenaudM. For$i \le j$, let binary variable$r_{i,j}$indicate that the bin represented by item$i$contains item$j$. (Here,... View answer Accepted answer 13 votes It is a cutting plane, but it is implied by$x_2+x_4\le 1$and$x_3\le 1so not very useful. View answer Accepted answer 12 votes Version (1) arises from conjunctive normal form as follows: $$y \implies (x_1 \land x_2 \land x_3) \\ \lnot y \lor (x_1 \land x_2 \land x_3) \\ (\lnot y \lor x_1) \land (\lnot y \lor x_2) \land (\... View answer Accepted answer 12 votes For strictly increasing CDFs, you can invert:$$x \le \Phi^{-1}(b)View answer 11 votes Equivalently, you want to remove the smallest number of constraints so that the resulting problem is feasible. You can do this implicitly, without enumerating all Irreducible Infeasible Sets, by ... View answer Accepted answer 11 votes This is called the budgeted maximum coverage problem. View answer 11 votes Let x_{p,\ell} be the continuous variables in your table. Introduce integer variables y_{p,\ell} and binary variables z_{p,\ell}, and impose linear constraints \begin{align} -z_{p,\ell} \le x_{... View answer Accepted answer 11 votes You can model the logical implicationCx < d \implies \bigvee_{i=1}^m \left(a_i^T x \ge b_i\right)by introducing m+1 binary variables y_i, where i\in\{0,\dots,m\}, and linear constraints ... View answer Accepted answer 11 votes Rather than solving this directly as MIQCQP, you might consider linearizing the products y_{ij} x_{ij}, as shown here, yielding instead an MILP problem. View answer Accepted answer 11 votes Let binary decision variable x_{i,g} indicate whether node i\in\{1,\dots,N\} appears in group g\in\{1,\dots,N\}, and let binary decision variable y_{i,j,g} indicate whether edge (i,j) ... View answer Accepted answer 11 votes I recommend a third approach, similar to yours but linear: \begin{align} x + 1 - y &\le M_1 z \tag1 \\ y + 1 - x &\le M_2 (1-z) \tag2 \\ \end{align} Constraint (1) enforces z=0 \implies x + ... View answer Accepted answer 11 votes Daniel Freund, Shane G. Henderson, Eoin O'Mahony, and David B. Shmoys won the 2018 Wagner Prize for their work on this problem. This link gives lots of info, including a video presentation: https://... View answer Accepted answer 11 votes You can strengthen your "conflict" constraint to a "clique" constraint:\sum_j x_r^j \le 1$$for all r. There are fewer of these, and they dominate the conflict constraints. View answer Accepted answer 11 votes Your second if-then statement is always true because Y is binary. For your first if-then statement, rewrite as its contrapositive Y=0 \implies tS \ge \epsilon. The following big-M constraint ... View answer Accepted answer 11 votes Let b_n be a binary indicator variable, and let integer variable y be the common value of the positive x_n. Then you want to enforce x_n=b_n y, which you can linearize using the formulation ... View answer Accepted answer 11 votes x_i \le y for i\in I \setminus \tilde{I} View answer Accepted answer 11 votes Let P be the set of (i,j) pairs. Here’s a derivation via conjunctive normal form: \begin{equation} \bigvee_{(i,j)\in P} \left(x_i \implies x_j\right) \\ \bigvee_{(i,j)\in P} \left(\neg x_i \vee ... View answer 11 votes A straightforward formulation that suffices is to impose conflict constraints of the form$$s_{j_1,t_1}+s_{j_2,t_2}\le 1$$if t_1+d_1>t_2, but you can strengthen that to$$\sum_{t\ge t_1}s_{j_1,t}... View answer 11 votes If the integer feasible set is finite and the LP polyhedron is bounded (a polytope), you could compare the volumes of the integer hull and this polytope. View answer Accepted answer 10 votes Your constraint is equivalent to $$x_i \le f(x_j) \quad \text{for j<i},$$ so it is linear iff$is linear. View answer Accepted answer 10 votes Introduce binary variable$Zand linear constraints \begin{align} X - \epsilon &\le (\bar{X} - \epsilon) Z \tag1 \\ Y - X &\le (\bar{Y} - 0) (1-Z) \tag2 \\ \end{align} Constraint(1)$... View answer Accepted answer 10 votes They are equivalent except when$x_{i,g}=x_{j,g}=0$, in which case the second linearization incorrectly contributes$-d_{ij}$to the objective. Assuming$d_{ij} \ge 0$, I recommend a third ... View answer Accepted answer 10 votes Consider the only two possible cases: If$x_i=0$for all$i$, then$(1)$and$(3)$both reduce to$\sum_j a_j y_j \le b$. If$x_i=1$for some$i$, then$(2)$implies that$x_k=0$for all other$k \...

Let $w_o$ denote the weight of object $o$, and let $c_b$ denote the capacity of bin $b$. You can interpret this as a job shop scheduling problem. The correspondence is that each object is a job, with ...
The big-M values need not be the same. You should choose $M_1$ in $(1)$ to be a small upper bound on $q$ and $M_2$ in $(2)$ to be a small upper bound on $p$. An alternative formulation is $p q = 0$, ...