40

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


28

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


17

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


16

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.


9

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


9

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


9

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

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

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 \\ $$


7

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


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


6

To complete @Marco Lübbecke said, There are many scheduling problems which use binary and continuous variables to represent the interval of time. For instance, machine scheduling problems use such a method to calculate the intervals. (start time or compilation time.) If you are interested to develop a MIP formulation, I recommended some references like: A)...


6

The vehicle routing problem with time windows is the first problem that comes to my mind, well researched, highly applicable. There are usually continuous variables that represent the visit (or start of service) time of a vehicle at a customer; that time must fall into a time window, which is an interval.


6

To transform an MILP into LP, you need to use an exponential number of variables: Check the book: Optimization over Integers, by Bertsimas and Weismantel. Chapter 4 contains different ways to convert binary linear programming (BLP) into linear programming (LP). The first step: $$s_n=\sum_{m=1}^{M} z_{n,m}q_{n}=q_{n}\sum_{m=1}^{M} z_{n,m}$$ bacause the ...


6

While this class of problems is still hard to solve (see the other answers for details), one speciality is that it has a trivial feasible solution $x=0$, which is not the case in general integer programming.


6

The following constraint should be correct: $$\sum_{c}(X_p{_w}_{cj}+X_{p+1}{_{w'}}_{cj+1})\leq T_w{_{w'}}_{,jj+1} +1 \ \ \ \forall w,w',p,p+1,j,j+1$$ Because if in your machine layout allocation, the process flows from machine $w$ to machine $w'$ then $X_{pwcj}$ and $X_{p+1w'cj+1}$ both should be $1$. Otherwise, either $T_{ww',jj+1}=0$ that means one of ...


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