Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
45
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
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
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
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
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
7
votes
2
answers
2k
views
Mixed-integer optimization with bilinear constraint
So I have an optimization problem of the following form:
\begin{aligned}
\max_{x,y} \quad & \sum_i x_i \\
\text{s.t.} \quad & \sum_i x_iy_i \leq a \\
\quad & x_{\min} \leq x \leq x_{\max} ...
- 293
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
7
votes
1
answer
10k
views
How to linearize min function as a constraint?
I'm trying to solve an optimization problem including following constraint, and I need to linearize it in a maximization nonlinear programming model. Please help me to reformulate it with mixed ...
- 87
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
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
11
votes
4
answers
1k
views
How to linearize a constraint with a maximum of binary variables times some coefficient in the right-hand-side
I have the following constraint that I'd like to linearize:
$P$ is a given set
$b_p \in \{0,1\} , \forall p \in P$ a binary variable associated with each element of $P$
$c_p \in \mathbb{R}^+$, a ...
- 2,428
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
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
10
votes
3
answers
1k
views
Is there a heuristic approach to the MILP problem?
I have the following optimization problem which is a MILP. I can solve it with a MILP solver.
\begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,...
- 2,377