15
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 $S=\{a,a+c,a+2c,\dots,a+kc\}$, introduce integer variable $y\in[0,k]$ and impose linear constraint $x=a+cy$. (The previous bullet is the special case $c=b-a$ ...
7
Introduce binary variables $z_1$, $z_2$, and $z_3$, and impose linear constraints
\begin{align}
z_1+z_2 +z_3&= 1 \tag1\\
1z_1+bz_2+(b+1)z_3 \le y &\le (b-1)z_1+bz_2+Uz_3 \tag2\\
z_2&\le x\tag3
\end{align}
Constraints $(1)$ and $(2)$ enforce the three disjoint cases $y<b$, $y=b$, and $y>b$. Constraint $(3)$ enforces $x=0\implies z_2=0$, and $...
6
Yes it is possible, but it may not be as efficient as the other methods listed in that PDF file. In fact, I'm still not sure there's any problem for which QUBO is the best way to solve it (see this: What are some real-world applications of QUBO?, and if interested in this area you may also find this one interesting: Are there any real-world problems where ...
5
Forum users are invited to post their suggestions for tighter/better formulations of mixed integer linear programming models here. The emphasis is on getting solutions (and closing the gap) efficiently, as opposed to model expressiveness (ease of users to see what is going on in the model).
General
Logical constraints
For "big M" models, smaller ...
4
Introduce linear constraints:
$$\sum_{\text{h}} z[\text{h}][\text{driver}] \le 1 \quad\text{for each driver}$$
4
The log-likelihood function $L$ is continuous while QUBO is discrete. If you really wanted to formulate it as a QUBO, this is how I would do it. In summary, the steps would be as follows:
$L \to \text{ Discrete-}L \to \text{ Binary-} L \to \text{Higher-Order-Binary-} L \to \text{ QUBO } L$
$L \to \text{ Discrete-}L$
This step would simply be restricting ...
4
It looks like your first constraint should instead be
$$0b_1 + a_1 b_2 + a_2 b_3 - d \le 0$$
With this change, the logical implications are
\begin{align}
b_1 = 1 &\implies 0 \le d \le a_1 \\
b_2 = 1 &\implies a_1 \le d \le a_2 \\
b_3 = 1 &\implies a_2 \le d \le a_3
\end{align}
To avoid ambiguous borders, introduce a small tolerance $\epsilon>...
3
Luckily in this case, the exponential can be treated in a way very similar to how we're already familiar. If we use the example that I chose in my answer to your recent question, we would have, where your $\vec{r}$ is just $(s_1,s_2)$:
$$\tag{1}
Z=\sum_{s_1,s_2} e^{\left(\mathcal{J}s_1s_2 + hs_1\right)}.
$$
If $\mathcal{J}=2.5$ and $h=3$, then we would have:
...
2
You can do something like this:
possible_values = [10, 15]
# add binary variables
b = m.addVars(len(possible_values), vtype="B")
# b[0] + b[1] == 1
m.addConstr(b.sum() == 1)
# add indicator constraints:
for i, val in enumerate(possible_values):
# if b[i] == 1, then x.prod(f) == val
m.addConstr((b[i] == 1) >> (x.prod(f) == val))
...
2
This sounds like the inventory routing problem.
2
As an approximation, suppose that the number $x$ of requests per trip does need to be an integer. Then $x$ needs to be at most $Q/q$ and divide $N$. For each fixed
$$x\in\{1,\dots,\min(N,\lfloor Q/q \rfloor): x \mid N\},$$
minimize $\sum_{i\in V} y_i$ subject to linear constraints
\begin{align}
(ax+b)n_i &\le T y_i &&\text{for $i\in V$} \\
x \...
1
I think the "drayage scheduling problem " might open a window for you.
1
The large instance is very hard to solve. I need to spend some time on it, but I lack ideas and time.
The flags part is problematic with jupyter notebook. We will fix those.
To print intermediate solution, you need a callback. See this code sample
1
I have added a more general question and answer that address the modeling aspect, independent of solver:
How to linearize membership in a finite set
You can apply this with $S=\{0,3,5\}$, $S=\{0,1,3,5\}$, and so on.
Only top voted, non community-wiki answers of a minimum length are eligible
