Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
44
questions
37
votes
3
answers
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$?
- 2,481
36
votes
2
answers
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$?
- 2,481
16
votes
1
answer
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
12
votes
1
answer
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
15
votes
5
answers
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?
- 2,481
13
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.1k
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
32
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,047
16
votes
1
answer
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)$$
- 2,481
11
votes
4
answers
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
6
votes
1
answer
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
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,482
13
votes
4
answers
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
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,211
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 ...
- 2,211
6
votes
1
answer
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 ...
5
votes
2
answers
724
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+\...
- 8,382
3
votes
1
answer
86
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....
- 30.3k
2
votes
1
answer
118
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\}$ ...
- 3,975
12
votes
1
answer
539
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 ...
- 793
12
votes
1
answer
309
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 ...
- 747
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 ...
- 241
9
votes
2
answers
844
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 ...
- 2,211
8
votes
2
answers
691
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:
...
- 215
7
votes
1
answer
96
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 ...
- 1,239
7
votes
2
answers
473
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 ...
- 2,211
6
votes
1
answer
237
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....
- 1,239
6
votes
1
answer
371
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 ...
- 197
5
votes
1
answer
566
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 &\...
- 1,239
5
votes
2
answers
527
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$...
- 2,180
4
votes
0
answers
273
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 ...
- 349
4
votes
1
answer
165
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, ...
- 67
3
votes
1
answer
542
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 ...
- 1,589
3
votes
1
answer
332
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}-...
- 2,211
3
votes
1
answer
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
3
votes
3
answers
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
3
votes
1
answer
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
2
votes
1
answer
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
2
votes
3
answers
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
2
votes
2
answers
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
1
answer
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
1
answer
601
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}}\...
- 2,211
1
vote
3
answers
422
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_{...
- 2,211