Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
259
questions
36
votes
3
answers
17k
views
How to linearize the product of two binary variables?
Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?
- 2,521
36
votes
2
answers
12k
views
How to linearize the product of a binary and a non-negative continuous variable?
Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
- 2,521
33
votes
8
answers
2k
views
Modeling floor function exactly
Suppose we want to enforce a constraint
$$
y=\lfloor{x}\rfloor
$$
where $x$ is some continuous variable. One option is to use
$$
x-1\leq{y}\leq{x},\quad y\in\mathbb{Z},
$$
which fails on the edge case ...
- 2,117
22
votes
3
answers
2k
views
How to minimize an absolute value in the objective of an LP?
I want to solve the following optimization problem
$$\begin{array}{ll} \text{minimize} & | c^\top x |\\ \text{subject to} & A x \leq b\end{array}$$
Without the absolute value, this a ...
- 1,502
22
votes
4
answers
3k
views
Linearize or approximate a square root constraint
I encounter a nonlinear constraint that contains the square root of a sum of integer variables. Of course one could use nonlinear solvers and techniques; but I like linear programming. Are there any ...
- 1,859
16
votes
1
answer
11k
views
How to formulate (linearize) a maximum function in a constraint?
How to formulate (linearize) a maximum function in a constraint? Suppose $C = \max \{c_1, c_2\}$, where both $c_1$ and $c_2$ are variables. If the objective function is minimizing $C$, then it can be ...
- 2,104
16
votes
1
answer
960
views
How to linearize a constraint with a maximum or minimum in the right-hand-side?
Suppose we have three variables, $x, y, z \in \mathbb R$. How can we linearize constraints with the following structure?
$$z \geq \min(x, y)$$
$$z \leq \max(x, y)$$
- 2,521
15
votes
4
answers
2k
views
Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?
Is there a single crisp and accessible reference which covers how to generate Mixed Integer Programming formulations to linearize products, handle logical constraints and disjunctive constraints, do ...
- 13.5k
15
votes
5
answers
9k
views
How to linearize the product of two continuous variables?
Suppose we have two variables $x, y \in \mathbb R$. How can we linearize the product $xy$?
If this cannot be done exactly, is there a way to get an approximate result?
- 2,521
13
votes
4
answers
795
views
The effect of choosing big M properly
I have a set of linearized constraints that are modelled using big-Ms. Now, it is, of course, common knowledge to make the value of M and small as possible in order to provide tighter LP relaxations ...
- 1,859
13
votes
6
answers
262
views
How to formulate: each pair of elements in $A$ has one common unit in $B$
We have two sets, $A$ and $B$. Some elements of $A$ must be connected to some elements of $B$, but no element of a given set is connected to another element of the same set. (Think of a bipartite ...
- 13.1k
13
votes
2
answers
129
views
Sensible and realistic way to model truck based transport costs depending on amount
Different kinds of problems involve transporting an amount $x$ from A to B which results in a cost $c(x)$ in the objective function.
Traditionally, often linearized costs are used to get an easy, ...
- 1,110
13
votes
1
answer
969
views
McCormick envelopes and nonlinear constraints
I have a problem with a nonlinear constraint. The non-linearity stems from a term of the form $xb$, where $x \in \mathbb{R}^+$, $x < M$ and $b \in \{0, 1\}$. I am able to remove this non-linearity ...
- 241
13
votes
1
answer
593
views
Linearization of the product of two real valued variables - Binary expansion approach
I want to minimize the following objective function:
\begin{align}\min &\quad x\cdot y\\\text{s.t.}&\quad2 \le x \le 5\\&\quad5 \le y \le 10.\end{align}
Since the objective function is ...
- 803
12
votes
1
answer
592
views
How to linearize membership in a finite set
Given finite set $S$ and variable $x$, how do I linearize the set membership constraint $x\in S$?
- 33.1k