# Tag Info

Accepted

### How to linearize the product of two binary variables?

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

### How to linearize the product of a binary and a non-negative continuous variable?

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

### How to formulate (linearize) a maximum function in a constraint?

(I'm going to change $c$ to $x$ in my answer, since $c$ is usually used for cost coefficients, not decision variables.) We want a set of constraints that enforces $X = \max\{x_1,x_2\}$. Define a new ...
• 12.6k
Accepted

• 2,244

### How to linearize the product of two continuous variables?

Unlike cases where one or both of the $x$ and $y$ are binary, you won't be able to truly (i.e. exactly) linearize this. https://stackoverflow.com/questions/49021401/how-to-linearize-the-product-of-...
• 2,237

### MILP Penalty Function Only for Negative Values

You do not need to introduce an indicator variable. Suppose $x$ is your free variable. Introduce nonnegative variables $x^+$ and $x^-$, replace $x$ with $x^+-x^-$ throughout, and penalize $x^-$ ...
• 22.2k
Accepted

### Linearizing this absolute difference objective function $\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$

As you are minimizing $y_{ij}$, it is sufficient to use $$y_{ij} \geq x_i - x_j \quad \forall i, j \\ y_{ij} \geq x_j - x_i \quad \forall i, j$$

### Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?

I recommend Formulating Integer Linear Programs: A Rogues' Gallery: The article[1] is very accessible, clear, and has multiple examples of using binary variables to achieve logical constraints. Full ...
• 1,816
Accepted

### How to linearize a constraint with a maximum or minimum in the right-hand-side?

Basically the condition is saying, $z$ must be between $x$ and $y$, regardless of whether $x \le y$ or $y \le x$. Here's a method that involves a new binary variable and a big-$M$. Let $w$ a binary ...
• 12.6k
Accepted

• 1,452

### The effect of choosing big M properly

The bigger the big-M is, more likely the numerical issues will happen with solvers. If you have right hand sides around $10^{10}$ and objective function coefficients in the range of $10^{-2}$, then ...
• 201

• 1,307

### Is there a heuristic approach to the MILP problem?

You can solve the LP relaxation and round the resulting solution $x^*$, being careful to preserve the equality constraint. Then take $t=\max_c |\sum_n B_{n,c} x_n - d_c|$. There are lots of choices ...
• 22.2k

### Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint

Assuming that the $c_i$ and $q$ are all positive you may add one binary variable $y_i$ for every $i=1,\cdots,n$ then you may do \begin{align}c_i x_i &\geq q y_i \quad\forall i\\\sum_i y_i &\...
• 1,509
Accepted

### Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint

You can do this with no new variables. Let $S=\{k:c_k \ge q\}$ and add the constraint $\sum_{k\in S}x_k \ge 1$.
• 29.6k