Questions tagged [linearization]

For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.

Filter by
Sorted by
Tagged with
10
votes
4answers
428 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 ...
31
votes
8answers
1k 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 ...
13
votes
2answers
98 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, ...
12
votes
1answer
289 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 ...
14
votes
5answers
2k 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?
13
votes
4answers
249 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 ...
19
votes
3answers
427 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 ...
14
votes
1answer
394 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)$$
12
votes
4answers
800 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 ...
31
votes
1answer
4k 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$?
32
votes
2answers
5k 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$?

1 2
3