46

This scenario can be linearized by introducing a new binary variable $z$ which represents the value of $x y$. Notice that the product of $x$ and $y$ can only be non-zero if both of them equal one, thus $x = 0$ and/or $y = 0$ implies that $z$ must equal zero. $$z \leq x\\z \leq y$$ The only thing left is to force $z$ to equal one if the product of $x$ and $...


31

Suppose we can give a finite upper bound for $y$ called $M$. Then this constraint can easily be linearized by using the so-called big $M$ method. We introduce a new variable $z$ that should take the same value as the product $x y$. Notice that the product which we model by $z$ equals zero if $x = 0$ but $z$ can take any value between $0$ and $M$ if $x = 1$. ...


19

I learned very early (this may not be generally true) that I should always prefer binary over integer variables. A reason is that from binary values you can infer logical information, branching on a binary variable fixes its value (=reduces the model) etc. I would go even further. It may be better to have more variables. Why? Of course, this depends on the ...


19

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 \implies (x \wedge y)\right) \bigwedge \left((x \wedge y) \implies z\right) \\ & \left(\neg z \vee (x \wedge y)\right) \bigwedge \left(\neg(x \wedge y) \vee z\...


13

In general no, these problems are hard. BUT: You might want to look into totally unimodular matrices and total dual integrality but this requires additional assumptions on the matrix or the problem respectively. If you are lucky, then your problem has these properties and you can solve it efficiently. Totally Unimodular Matrices A totally unimodular ...


13

First of all, I would say that "fast solvable in practice" is possible also when your remaining problem still is NP-hard. But since you ask specifically for polytime solvability, there are some cases. Most well-known is probably "TU-ness" of your matrix. When you solve a MIP $$\min\{c^tx \mid Ax\geq b, x\in Z^n\times Q^q\}$$ then you will obtain an integer ...


11

Instead of $$\frac{\textrm{Total school income}}{\textrm{Number of areas}} \ge \$ 85000$$ you could have a constraint $$\textrm{Total school income} \ge \$ 85000 \times \textrm{Number of areas}.$$ In this case, you won't have any problems when the number of areas is zero. It also makes the model linear instead of non-linear, which is usually a good thing. ...


11

$x_i \le y$ for $i\in I \setminus \tilde{I}$


11

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 enforces that: $$\epsilon - tS \le MY$$ This is equivalent to what you tried. Note that $(tS,Y)=(\epsilon,0)$ is feasible, so if the solver always returns it, ...


11

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.


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 ...


9

Same idea, but typically formulated as $$\sum_j x_r^j \leq 1, \: \forall r$$ For binary $x$


8

These conflict constraints can be replaced with clique constraints of the form $$\sum_{n\in C} z_{n,m}\le 1 \quad \text{for all $m$},$$ where each $C$ is a clique in the graph with nodes $1,\dots,N$ and edges determined by $A$.


8

As LarrySnyder610 said, you cannot do exactly what you want when $x_i$ is continuous. (You can if it is an integer variable.) I discussed how to model this particular issue here: Flagging a Specific Variable Value.


8

With binary $b$, it is called a set packing problem: https://en.m.wikipedia.org/wiki/Set_packing With integer $b$, it is called a generalized set packing problem.


8

Kevin Dalmeijer's answer is correct for the general case. Since $A$ is symmetric, there may be a method that involves fewer constraints. As suggested by Kevin's comment, I'm going to represent a typical equation with the simpler notation $x^T A x = 0$ (mostly to save typing). A square matrix $A$ may have a square root $B$, such that $BB=A$. In some cases, ...


8

The constraints $${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$$ can be rewritten as $$\sum_{i=1}^N \sum_{j=1}^N A(i,j) U(i,m)U(j,m)=0,m=1,2,\cdots,M.$$ Next, you can linearize each of the $U(i,m)U(j,m)$ terms as explained here.


8

1QBit published a white paper "Optimal feature selection in credit scoring and classification using a quantum annealer". The authors compare their feature selecting QUBO model to mainstream recursive feature elimination (RFE) methods. http://qbit.wpengine.com/wp-content/uploads/2017/04/1QBit_-Optimal-Feature-Selection-in-Credit-Scoring-and-Classification-...


8

Multiply both sides of your $d_k \ge$ constraint by the denominator and then linearize $d_k y_{ijk}^+$ and $d_k y_{ijk}^-$ as described in this thread.


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

@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

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

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

In chapter 10 of his dissertation [1], Gabriel Tavares, talked about some real-world applications of QUBO. He also proposed a new approach to solve QUBOs by modifying some of the previously existed methods. Authors in [2], listed a wide range of important optimization problems that the QUBO model encompasses: Quadratic Assignment Problems Capital Budgeting ...


7

First question: Yes, your algebraic formulation is correct. Second question: I would lean toward using the algebraic formulation, for two reasons. First, it is not solver-specific. Second, a reader not familiar with indicator constraints will find interpreting the algebraic formulation a bit easier, while a reader familiar with indicators is not likely to ...


7

There is no single entity in MIP modeling that is a direct analog of an interval variable. The general MIP approach is as follows: discretize the time domain (which is inherent in CP models using interval variables); in lieu of a single interval variable, create a binary variable for each possible starting time and add a constraint setting the sum of those ...


7

You could simply write $$y(i) - y(i - 1) \ge 0, \qquad i=2,...,N$$


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