Questions tagged [linearization]

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

44 questions
Filter by
Sorted by
Tagged with
14k 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$?
10k 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$?
9k 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,086
529 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$?
• 30.3k
7k 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?
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.1k
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
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
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,047
854 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)$$
896 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,398
8k 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 ...
• 77
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,482
623 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
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,211
2k views

How to linearize the multiplication of an integer and a binary integer variable?

I have the following constraints \begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align} where $x_i\ge 0$ is an integer variable, $t_i\in\{0,1\}$ is a binary variable ...
• 2,211
685 views

Linearize a product of an integer variable (not just binary) and a continuous variable?

I have a constraint in my formulation that contains multiplication of an integer variable $y$ and a continuous variable $x$, which is $xy=q$ where $y$ is the number of units in which $q$ gets equally ...
724 views

• 2,211
376 views

Linearizing power term in objective function

I would like to linearize $x^2$ term in my objective function. I understand this can be solved using quadratic programming solver; however, for my use case linearization is necessary to convert it to ...
• 793
233 views

Quantifying a measure of standard deviation in MILP

I am trying to set up a MILP for production scheduling. The specific details I'm not sure are important but in general a plant has M machines running N parts, each part requiring W workers. The model ...
• 55
318 views

How to deal this L0 norm of a vector of L2 or L1 norms in objective?

I have an optimization variable denoted as ${\bf A\in\mathbb{C}^{100\times 5}}=[{\bf a}_1\hspace{1mm} {\bf a}_2 \hspace{1mm} {\bf a}_3 \hspace{1mm} {\bf a}_4 \hspace{1mm} {\bf a}_5];$ Here, ${\bf a}_1$...
• 2,211
162 views

Why MiniZinc do not do convert to linear constraint a quadratic constraint?

I would like to know which are the advantage to do not convert quadratic expressions into linear expression in MiniZinc. For example let be the following simple MiniZinc code ...
• 179
1k views

Linearizing a Max Function in the constraint - not working

I have a minimization function which is in its simplest form looks like below. I am including the index of the variables. ...
• 793
313 views

Linearize a product of binary variables

I have a function to minimize which has the following term $$\sum_{i\in I}\sum_{j\in J}\sum_{k\in K}x_{ijk}N_{ij}a_{ijk},$$ where the variables are $x_{ijk}\in\{0,1\}$, $a_{ijk}$ are given as input ...
• 381
1 vote
160 views

Linearize conditional constraint

Consider a variable c from the domain {-1,0,1}. I have the following constraint: IF $c = 1 \Rightarrow x = 1$ ELSE $x = 0$ How do I linearize this constraint?
• 19
1 vote