Skip to main content

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
37 votes
3 answers
16k 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$?
Michiel uit het Broek's user avatar
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$?
Michiel uit het Broek's user avatar
16 votes
1 answer
10k 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 ...
Mostafa's user avatar
  • 2,104
14 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 ...
Mark L. Stone's user avatar
12 votes
1 answer
561 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$?
RobPratt's user avatar
  • 32.3k
15 votes
5 answers
8k 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?
Michiel uit het Broek's user avatar
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} ...
Johnny's user avatar
  • 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 ...
Albert Schrotenboer's user avatar
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 ...
Vida's user avatar
  • 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 ...
David M.'s user avatar
  • 2,107
16 votes
1 answer
929 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)$$
Michiel uit het Broek's user avatar
11 votes
4 answers
978 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 ...
Renaud M.'s user avatar
  • 2,418
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 ...
Discrete lizard's user avatar
13 votes
4 answers
729 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 ...
Albert Schrotenboer's user avatar
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,...
KGM's user avatar
  • 2,297
8 votes
1 answer
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 ...
KGM's user avatar
  • 2,297
6 votes
1 answer
778 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 ...
optimizationguy's user avatar
5 votes
2 answers
785 views

How to linearize specific range constraints?

I would like to know about the linearization of the $(If, Then)$ constraints as follows: $$\begin{array}{l} \text { If: } \\ 15 \leqslant x \leqslant 25 \\ \text { then: } \quad y=\color{blue}{a} x+\...
A.Omidi's user avatar
  • 8,950
3 votes
1 answer
126 views

How to enforce logical implication $\sum_j a_j x_j \le b \implies \sum_j c_j x_j \le d$

Some modeling languages and solvers support indicator constraints of the form $$y=\hat{y} \implies \sum_j a_j x_j \le b,$$ where $y$ is a binary decision variable and $\hat{y}\in\{0,1\}$ is a constant....
RobPratt's user avatar
  • 32.3k
2 votes
1 answer
2k views

How to linearize the product of a binary and a continuous variable? [duplicate]

Suppose we have a binary variable $b \in \{0, 1\}$ and a continuous (possibly negative) variable $y \in \mathbb{R}$. How can we linearize the product $b \cdot y$?
joni's user avatar
  • 1,572
2 votes
1 answer
133 views

Linearize product of $x\cdot y \text{ with } x,y \in \{-1,0,1\}$ for MILP

I have a problem where I have many products between variables drawn out of $\{-1,0,1\}$. Could you suggest a linearization in terms of variables in $\{-1,0,1\}$ or $B_1 - B_2$ where $B_i \in \{0,1\}$ ...
worldsmithhelper's user avatar
13 votes
1 answer
580 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 ...
S_Scouse's user avatar
  • 803
12 votes
1 answer
330 views

QA techniques for optimization problem coding

I often spend much, much, more time QAing and debugging my code than I do actually writing the optimization problem or shaping my data. Are there any tools or techniques to make it easier? I am asking ...
Zohar Strinka's user avatar
11 votes
2 answers
1k views

Linear programming: objective function with "buckets"

I had a linear programming problem with the following objective function $$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$ Where $q, p, C, c$ are known. This problem was ...
BarkingCat's user avatar
9 votes
2 answers
963 views

How can I transform this MILP into an LP problem?

I have a MILP problem with one of the constraints is given below. Sometimes, even for a small-sized problem, the solver takes a very long time to find a solution. What could be an efficient ...
KGM's user avatar
  • 2,297
8 votes
2 answers
756 views

knapsack problem with non-linear constraint

I have a basic knapsack problem where I need to fit the most weight possible in a bin: ...
Cesar Canassa's user avatar
7 votes
1 answer
99 views

Linearizing the square root of two binary summations

My question is similar to this one though a bit more complicated. Though my question also includes indices, I am removing them to ease readability. Let binary variables $x,y\in\{0,1\}$, non-negative ...
tcokyasar's user avatar
  • 1,249
7 votes
2 answers
496 views

How can I linearize or convexify this binary quadratic optimization problem?

I have an optimization problem as below. I am having a hard time with the last constraint. $\max \eta$ subject to ${\bf U}(:,m)^T{\bf A}{\bf U}(:,m)=0,m=1,2,\cdots,M$ here $\bf{A}$ is a Binary ...
KGM's user avatar
  • 2,297
6 votes
1 answer
381 views

Optimize for bonuses within a group (knapsack)

I am trying to create an LP problem which is like the knapsack problem but with groups of items. Let's say there are 10 groups of items each with up to 5 items. Each group has one special item and you ...
Eddie's user avatar
  • 197
6 votes
1 answer
243 views

Linearizing the square root of binary summations

My question is similar to this one and almost identical with this. I am so confused due to indexing and could not make sure if I could apply the solution in here to this indexed version as shown below....
tcokyasar's user avatar
  • 1,249
5 votes
1 answer
629 views

Linearizing a constraint with square root of a variable

I am trying to linearize the constraint set (2) in the following simplified program. The parameters: $A,C,D,T\in\mathbb{R}^+$. The set $\mathcal{J}$ is polynomially-sized. \begin{alignat}2\min &\...
tcokyasar's user avatar
  • 1,249
5 votes
2 answers
554 views

How to model If $A \le B$ then $Y = 1$, otherwise $Y = 0$

Somehow I don't get it right. I would like to model the following conditional: If $A\le B$ then $Y=1$ otherwise $Y=0$ where $A, B$ are reals and $Y$ is binary. I can model as follows: $Y \cdot A \le B$...
Clement's user avatar
  • 2,252
4 votes
0 answers
287 views

Linearize a highly non-linear objective function

[EDIT] : The formula below is updated to remove the radical, 0.5 in the term $(I_{i,v} \cdot \Delta t)$ and constant temperature $T$ replces temperature as function of current. [EDIT] :The values of ...
Jose_Peeterson's user avatar
4 votes
1 answer
186 views

Non-Linear objective function due to piecewise component

I have the following objective function: $\sum_{n}(1-prob_{n})(1+x_n)$ Where $x$ is my decision variable. $prob_{n}$ is a piecewise function that can look like: $prob_{n} = $ \begin{cases} 0.5, ...
akkha's user avatar
  • 67
3 votes
3 answers
269 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 ...
Dano's user avatar
  • 55
3 votes
1 answer
376 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$...
KGM's user avatar
  • 2,297
3 votes
1 answer
344 views

How can I convexify (allowed some approximation) the objective function?

I have a known matrix, $H$ of size $U\times B$. The optimization variable is $D$ of same size, which is binary Now I have $$S_u=\frac{\sum\limits_{b=1}^{B} D_{u,b}H_{u,b}}{\sum\limits_{b=1}^{B}H_{u,b}-...
KGM's user avatar
  • 2,297
3 votes
1 answer
461 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 ...
S_Scouse's user avatar
  • 803
3 votes
1 answer
556 views

If else condition to MILP

I have following problem: $c_i = 1$ if $X + \sum_j^N G_j = T$ else $c_i = 0$ Also there is another constraint which upper bounds equation $X + \sum_j^N G_j \le T$. $c_i$ is binary $X, T$ are ...
ooo's user avatar
  • 1,589
2 votes
1 answer
171 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 ...
juaninf's user avatar
  • 179
2 votes
3 answers
2k 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. ...
S_Scouse's user avatar
  • 803
2 votes
2 answers
325 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 ...
zdm's user avatar
  • 403
1 vote
1 answer
674 views

How to transform this problem with logarithmic objective function into an approximated convex optimization problem?

I have an objective function as follows $\underset{x_{m,n}}{\max}\hspace{1mm}\hspace{1mm}\sum_{m=1}^{M}\log_2\left(\frac{\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z}{\sum_{n=1}^{N}x_{m,n}\omega_{m,n}}\...
KGM's user avatar
  • 2,297
1 vote
3 answers
456 views

How can I linearize this IF-THEN constraint?

Let $P_{t,u}; t=1,2,\ldots,T, u=1,2,\ldots,U$ be known values $\alpha$ is also a known parameter $X_{t,u}$ an optimization variable I have the following constraint: IF $P_{t,u}\geq\alpha$, THEN $X_{...
KGM's user avatar
  • 2,297
1 vote
1 answer
192 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?
Waldo's user avatar
  • 19