Tag Info

11

I'm not sure if this is the most elegant modelling way. However, this is exactly how integer numbers are represented in the computer: Let's consider one integer variable $x \in \mathbb{Z}$ with $L \leq x \leq U$ and $L \geq 0$, i.e. $x$ is not negative. By introducing $M$ binary variables (bits) $b_0, \ldots, b_{M-1}$, we have the representation of $x$ in ...

10

Presumably you have binary decision variables like $x_{ik} = 1$ if marble #$i$ is in slot #$k$. Then you can write a constraint like $$x_{ik} \le 1 - x_{jl} \qquad \forall \text{i < j and k > l}$$ In other words, if $i < j$ and $j$ is in slot $l$, then $i$ cannot be in any slot $k$ that comes after $l$.

10

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$, but that is nonlinear. If your solver supports indicator constraints, you can write the desired implications directly, without specifying big-M: \begin{align} y ...

8

If I understand correctly, you can obtain the desired linear constraints via conjunctive normal form. Explicitly, suppose $f(\bar{x}_1,\dots,\bar{x}_n)=1$, and let $S_0 = \{j\in\{1,\dots,n\}:\bar{x}_j = 0\}$ and $S_1 = \{j\in\{1,\dots,n\}:\bar{x}_j = 1\}$. You want to enforce $$\left[\left(\bigwedge_{j\in S_0} \lnot x_j\right) \bigwedge \left(\bigwedge_{j\... 8 @Kuifje's formulation is correct. Here's a somewhat automatic derivation via conjunctive normal form:$$ \lnot \bigwedge_{i=1}^n \omega_i \\ \bigvee_{i=1}^n \lnot \omega_i \\ \sum_{i=1}^n (1 - \omega_i) \ge 1 \\ \sum_{i=1}^n \omega_i \le n-1 \\ $$8 How about$$\omega_1 + \cdots + \omega_n \le n-1 $$This way, at most all variables but one of them can take value 1 simultaneously. In the context of knapsack problems, if each variable models the selection of a given item and that the sum of the weights of the items exceed the knapsack capacity, these inequalities are called cover inequalities. 8 You can stay in base 10 with a similar approach as @joni: introduce m=U-L+1 binary variables y_i, one for each integer value in the range [L,U], and write x as follows:$$ x= L y_1 + (L+1)y_2 +...+(U-1)y_{m-1} + Uy_m $$Then, make sure only one of these values is selected:$$ \sum_{i=1}^m y_i = 1 $$Of course this yields more than \lceil \log_2(U+... 8 Constraining a variable to be binary could be expressed as a quadratic constraint:$$ x\in\{0,1\} \iff x(1-x)=0 $$This is often mentioned in non-convex QCQP articles to present non-convex QCQP is a somehow more general problem class.$$ \{\mbox{MILP}\}\subset\{\mbox{non-convex QCQP}\} There are some off-the-shelf non-convex QCQP (global) solvers, like ... 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 ... 7 If I understand correctly, the following enforces your desired behavior: \begin{align} y_1 &= d_1 \\ y_2 &= d_2 \\ y_3 &= d_3 \\ y_4 &\ge d_1 + d_2 - 1\\ y_5 &\ge d_1 + d_2 + d_3 - 2\\ \end{align} If you also want to enforce y_4 \implies (d_1 \land d_2) and y_5 \implies (d_1 \land d_2 \land d_3), then include these additional ... 7 @user3680510 gave the correct answer in a comment. Here's a way to derive it via conjunctive normal form: i \not= j \\ (i \implies \lnot j) \land (\lnot i \implies j) \\ (\lnot i \lor \lnot j) \land (i \lor j) \\ (1 - i + 1 - j \ge 1) \land (i + j \ge 1) \\ (i + j \le 1) \land (i + j \ge 1) \\ i + j = 1 $$To prevent both to be 1 at the same time:$$ \...

6

As per the answer by @LarrySnyder610, we can use position-based variable $x_{ik}$ to model such scenarios. Note that we also need the following constraints to ensure that each $i$ is assigned to exactly one position $k$: $$\sum_{k}x_{ik}=1 ~~~~~~~~ \forall i$$ If $n$ is the total number of possible $i$ or $k$, then this method requires $\mathcal{O}(n^4)$ ...

5

Many state-of-art real-world large-scale combinatorial optimization problems are based on heuristics that use some sort of local search in them. Although not stated directly as a QUBO, many of these local search moves are based on solving a QUBO (with no "tricks" of penalizing the constraints). For example in the Travelling Salesman Problem, the ...

5

Consider the following tiny example. You have two factories, one warehouse and two product. Factory 1 can produce both goods in sufficient quantity to meet demand but has a very large cost coefficient. Factory 2 only produces the second product, with adequate capacity and a small cost coefficient. The optimal solution to the original problem is to ship ...

4

Your constraint is equivalent to "if P=0 then t>0" which involves strict inequality. Strict inequality is not something that can be handled by a MIP solver without using some sort of epsilon. But can t actually be arbitrarily small but non-zero in your case? Maybe it is possible/acceptable to find a small enough epsilon to model your constraint ...

4

Suppose we know an upper bound $M$ for $y$ such that $|y| \leq M$, we can linearize this constraint as follows. First, we introduce a new variable $h \in \mathbb{R}$ with $h = b y$. Then we need to model that $h$ equals $y$ if $b = 1$ and equals $0$ if $b = 0$. For this purpose we add the following linear constraints: \begin{align} h &\leq b M \tag{1} ... 4 Enforcing b_t to take value 1 when x_t is positive is done with x_t \le b_t, assuming x_t \le 1. For the second part, quoting @MarkL.Stone: You will have to choose a tolerance as to how close to zero should be considered zero Let \epsilon be this tolerance. So you want to enforce x_t < \epsilon\implies b_t = 0 Now referring to this ... 4 I'm only aware of a mechanism that works if there is an upper bound for the continuous variable. \begin{align}x_{t, \max}\cdot b_t &\geq x_t\\ m\cdot x_t &\geq b_t\end{align} I used this in answering this question. I'm not aware of a way to solve it for unbounded x_t, unless the solver handles floating points infinities correctly. This would need ... 3 You are not going to be able to add these logs and quadratic terms to the model via simple double-sided big-M constraints, as they generate non-convex use of convex quadratics and logs, and CVX does not support that. The use of the squared log is not possible either. I don't think it supports automatic modelling of nonconvex use of abs operator either. Most ... 3 In order to query the GRB_DoubleAttr_UnbdRay attribute, you need to optimize the problem with the InfUnbdInfo parameter set to 1. 3 To enforce x = 1 \implies y = 1 for binary variables x and y, impose linear constraint x \le y. You can derive this constraint via conjunctive normal form: x \implies y \\ \lnot x \lor y \\ (1 - x) + y \ge 1 \\ x \le y $$3 You can use conjunctive normal form to derive the desired constraints. The first one is:$$a \ge b \implies a\ge c\\ (b \implies a) \implies (c \implies a)\\ \lnot(\lnot b \lor a) \lor (\lnot c \lor a)\\ (b \land \lnot a) \lor (\lnot c \lor a)\\ (b \lor \lnot c \lor a) \land (\lnot a \lor \lnot c \lor a)\\ (b \lor \lnot c \lor a)\\ b+ 1- c +a \ge 1\\ a+b \...

3

According to the equality constraint (the equal to 4 one), at least two of the $x_{?}$ are 1. Therefore, the slack for the 1st constraint is at most 3. According to the equality constraint, the worst case is $x_1$, $x_4$, $x_5$ are 1 while other xs are 0. The slack is 6 in that case for the 3rd constraint. Alternatively, we can approximate the bound of the ...

3

\begin{align}\text{diff}^2&=c^2+4\left(\left(\sum s_jx_j\right)^2-c\sum s_jx_j\right)\\&=c^2+4\left(\sum s_j^2x_j^2+\sum_{\rm cyc}s_ks_\ell x_kx_\ell-c\sum s_jx_j\right)\\&=c^2+4\left(\sum x_j\boldsymbol{s_j(s_j-c)}x_j+\sum_{\rm cyc}x_k\boldsymbol{s_ks_\ell}x_\ell\right)\\ &=c^2+4x^\top Qx\end{align}

3

Following is a possible way of its implementation: First, you define a function that takes an OD matrix, solves the GUROBI model, and returns the optimal locations. FUNCTION OPTIMAL_LOCATION(OD): // This part will prepare the gurobi model and change the parameters related to OD matrix // Solve the model and return locations END FUNCTION ...

2

You could define a binary variable $\delta \in \{0,1\}$ that takes value $1$ if and only if $t=0$: \begin{align*} 0\le t &\le H(1-\delta) \\ 1-\delta &\le M t \end{align*} Then, enforce $$\delta \le P$$ Note that choosing the right value for $M$ may be as tricky as finding the right $\epsilon$. You need $M$ big enough such that if $t=\epsilon$, $M\... 2 In computer science, "integer" data types are generally a fixed-length array of bits. In earlier languages, those lengths were generally 16 or 32 bits, but later languages tend towards 64. This type of implementation does have drawbacks. For instance, they aren't really integers, in the mathematical sense, as they are members of a finite set. The ... 2 If I am not mistaken the answer is NO unless$P=NP$. We can reduce Exactly-1 3-satisfiability to your problem. For a proof of 1-IN-3SAT is NP-complete see NP-Completeness of 3SAT, 1-IN-3SAT and MAX 2SAT. Given an instance$I$of the Exactly-1 3-satisfiability problem. For each variable$x_i$check whether there is a solution setting it to$1$and$0$. This ... 2 Considering you have a set of n variables (elements)$p_1, p_2, …, p_n$to be sorted in ascending order so that$p_{[1]}, p_{[2]}, …, p_{[n]}$where$p_{[1]} \leq p_{[2]} \leq …\leq p_{[n]}$, you can introduce$n^2$binary decision variable$ x_{i,j}$and$n$variables$A_i$.$ x_{i,j}=1$if$i-th$element is assigned to$j-th$position.$ min \left \{ \...

2

I don't know whether this is the reason, but the documentation says that InfUnbdInfo is for LP only. So we might have to work with the LP. Two thoughts: x = 0, u = 0 is a feasible solution for the MIP. As x is bounded, x will not be part of the ray. Thus, any ray for the LP should also be a ray for the MIP. So if Gurobi decides your problem is unbounded, ...

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