Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
198
questions
1
vote
1
answer
207
views
Non-linear optimization local or global solution
In an NLP, I have a constraint that I would like to formulate in a convex manner preferably without introducing binary variables and/or big M formulations if possible. The actual problem is non-convex ...
- 81
3
votes
1
answer
290
views
Linearizing a quadratic function with more variables or not in Gurobi?
Suppose I want to set the price $0 \le p_t \le p_{max} $ and based on the price, demand is determined $D_t(p_t)=a-bp_t$. Inventory level at each time is denoted by $I_t$ and it is determined by $I_t= ...
- 2,140
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
7
votes
2
answers
1k
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} ...
- 193
3
votes
1
answer
280
views
Linearize x different of y in ILP
I am surprised I couldn't find an already written answer for my question in the internet.
I want to linearize $x$ different of $y$ for two nonegative integer decision variables. I am not considering ...
- 583
3
votes
0
answers
145
views
How to linearize a max min objective function?
Let us suppose that I have a $\max \min$ objective function that only depends on one set of variables:
$\underset{x}\max \underset{y}\min dy$
Associated with the linear set of constraints and right ...
- 583
2
votes
1
answer
202
views
MILP constrained by the minimum number of satisfied constraints
I have an MILP where we have
$$
t_k = \sum_i P_i\cdot C_{ik} : P_i\ \in \{0,1\}, C_{ik} \in I^+
$$
and our model is constrained by the number of times $t_k$ is bigger than a certain value $T_k$.
$$
\...
4
votes
1
answer
315
views
Maximizing a piecewise-linear convex function
Note: Initially posted on MathOverflow.
I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:...
- 141
0
votes
1
answer
154
views
How to linearise this nonlinear constraint?
I have a constraint in the form
$\sum_{n=1}^{N}x_{m,n}\omega_{m,n}\ge (t_u-1)\beta_u, \forall u, u=1,2,\cdots, U$
where $x_{m,n}$ is binary variable
$t_u$ and $\beta_u$ are continuous optimization ...
- 2,191
1
vote
1
answer
513
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,191
2
votes
1
answer
185
views
How can I linearise this nonlinear proportional relation constraint?
My optimisation problem has a constraint in the form
\begin{equation}
\begin{array}{*{35}{l}}
\text{}\hspace{16.5mm}\text{ C4:} \hspace{2mm}\sum_{u=1}^U d_{u,1}L_{u}:\sum_{u=1}^U d_{u,2}L_{u}:\cdots:\...
- 2,191
4
votes
1
answer
127
views
Linearize $\max x_i\ge1$
I'm trying to linearize this optimization problem ($S_j$ is a subset of variables): \begin{align}\min&\quad\sum_{x_i \in X} x_i\\\text{s.t.}&\quad\max_{i \in S_j}x_i\geq 1\quad\forall S_j\\&...
- 41
6
votes
2
answers
843
views
How to transform this logical if-then constraint?
Consider the binary variables $x, y, z \in \{0,1\}$.
I'd like to formulate the two if-then constraints:
$$ x + y \geq 2 \implies z = 0, \tag{1} $$
$$ x + y \leq 1 \implies z = 1. \tag{2} $$
Constraint ...
- 385
-2
votes
1
answer
105
views
how to linearize the full model for TSP quadratic formulation?
I tried to solve this problem but I failed, please how to linearized full model.
- 45
3
votes
1
answer
519
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
2
votes
1
answer
82
views
How to model these constraints correctly
$W$ is a vector of $N$ complex elements.
$D$ is a binary variable
The requirements are:
when $D==1$, $L_{\min}\le ||W||_2^2\le L_{\max}$
and when $D==0$, $||W||_2^2=0$
I have formulated the following ...
- 2,191
1
vote
0
answers
118
views
Linearization of constraints with square root [closed]
I am trying to solve an optimization programming model involving a non-linear constraint with a square root. It follows (in a simplified form): $X_i\ge\sqrt{A_i/B_i}$ where $X_i,A_i,B_i$ are positive ...
3
votes
1
answer
318
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,191
6
votes
1
answer
284
views
How to linearize $f(x,y) = (ax+by)/(x+y)$?
I have a problem which is mainly linear but it has a non-linear component. The objective function is
obj = Linear_term + $c*f(x,y)$ where,
$f(x,y) = (G_1 x_1 + G_2 x_2)/(x_1 + x_2)$.
The decision ...
- 63
4
votes
1
answer
208
views
How/when can we use MINLP engines instead of linearizing MP models?
Nowadays, mathematical programming solvers have been frequently used to solve lots of practical/academic problems. Many of these might be interpreted as a MIP or MINLP to represent a specific problem (...
- 7,664
7
votes
1
answer
248
views
Linearizing a program with multinomial logit in the objective
I have a nonlinear problem as follows: \begin{align}\min&\quad\sum_{k=1}^{K}\left|y_k - \sum_{i=1}^{N} \frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K} e^{x^{i}_{j}}}\right|\\\text{s.t.}&\quad x^i_{j} \ge ...
- 173
7
votes
1
answer
217
views
Maximizing a Ratio/Percent
I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they ...
- 195
1
vote
2
answers
374
views
Switching of decision variables to be larger than or equal to a decision variable according to an indicator variable value
I would like to seek some advice on modeling the following:
I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is greater than or equal to a ...
- 707
1
vote
3
answers
391
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,191
3
votes
3
answers
782
views
How to linearize the Min function while letting the binary variable to be fixed for x1==x2 as well?
As discussed here, the min function, i.e $X = \min\{x_1,x_2\}$, can be linearized as follows:
\begin{align}
X & \le x_1 \\
X & \le x_2 \\
X & \ge x_1 - ...
- 294
4
votes
1
answer
169
views
Formulating these logical constraint in an ILP
I have these two constraints :
$z \leq My$
$t \leq M'y $
where $z$ and $t$ are two integer variables $ z, t\geq 0$, $y$ is a binary variable, and $M$, $M'$ are two big numbers.
So basically these ...
- 117
2
votes
1
answer
233
views
Linearize sum of continuous and boolean variable
For maximizing the objective function $\sum_i{d_i y_i}+ A x - B \cdot \mathbb{I}_{x>0}$, how can I linearize $ A x - B \cdot \mathbb{I}_{x>0}$ term where $d_i, A$ and $B$ are positive constants ...
- 123
7
votes
1
answer
272
views
Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem
I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem.
Informally:
We have a $m \times n$ decision matrix of binary variables
Each row of the matrix ...
- 173
3
votes
1
answer
324
views
Logical constraint in ILP
I want to write the following constraint:
Let $z$ be an integer variable such that $0\le z\le M$, and $t$ be a binary variable where $M$ denotes big-M. The logical constraint is as follows:
if $z \...
- 117
3
votes
1
answer
472
views
How to express this logical constraint for an ILP?
I am trying to write an ILP for a problem but I have this logical constraint and I'm stuck.
In my model I have:
two binary variables: $x$ and $y$
One Integer variable: $z$
The logical constraint I am ...
- 117
10
votes
6
answers
2k
views
Nonlinear integer (0/1) programming solver
I have the following optimisation problem.\begin{align}\max&\quad\sum_i\sum_j\sum_k x_{ji}y_{kj} \operatorname{cost}(i,k)\\\text{s.t.}&\quad\sum_j x_{ji}=1\quad\forall i\\&\quad\sum_k y_{...
- 109
3
votes
1
answer
154
views
Linearizing separable functions: SOS2 sets or binary variables
When linearizing a separable nonlinear function is there an advantage/disadvantage in using SOS2 sets in comparison to using binary variables?
- 2,132
5
votes
1
answer
145
views
Minimize binary variable's distance with respect to the index values
For a given binary decision variable $x[i,j,k]$ my goal is to get as dense results in terms of k for successive values of j. Distance of k value to be kept as close as possible throughout j values:
$d ...
- 315
8
votes
2
answers
629
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
5
votes
2
answers
795
views
How to linearize a quadratic constraint to add it then via a callback function
Suppose we have a positive continuous variables $0 \le x \le UB$ where $UB$ is a known upper bound.
How can we linearize the term $x^2$?
Detailled problem:
Suppose that via a callback we compute a ...
5
votes
1
answer
499
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
3
votes
1
answer
332
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
1
answer
323
views
Linearize sum of product in objective function
Notation:
I have an optimisation problem with objective function: \begin{align}\max&\quad\sum_n Q_n\\\text{s.t.}&\quad Q_n=x_{ij}^{nk}(y_i^{nk}-c_n), \forall n \in N, k \in K, (i,j) \in P.\end{...
- 33
3
votes
0
answers
90
views
Linearization of the shifted copy of a function
Suppose in a model I have the expression $y_{1}(x) = 10 + 5 x^2$ where $x \in [0,20]$ is a continuous variable. In order to be able to use an MILP solver, I piecewise linearise $z_{1} = x^2$, by ...
- 2,132
6
votes
1
answer
441
views
Convert summation of min functions into linear constraints for optimization
I have the following optimization problem:
$$
\mbox{maximize } j^{*} \mbox{ subject to:} \sum_{j^{*}\leq j\leq J} \min({\bf A}_j,{\bf B}_j) \geq \lambda, \lambda \in \mathbb{R} \mbox{ and } {\bf A}_j,{...
- 63
1
vote
0
answers
64
views
Linearize max function in a constraint [duplicate]
I have a constraint as follows:
$ \sum_i {r_i} \geq \max \{g_j, B_j\} $
where, $r_i$, $g_j$ are variables and $B_j$ is a parameter.
How do I linearize the constraint (I suppose using big-M method)?...
- 793
3
votes
0
answers
58
views
Linearisation using SOS2
I am trying to linearise the following expresssion.
$C(k) = B(k) e^{-d(k)}, B(k) \ge 0 , d(k) \ge 0 $
I am trying to do this by using SOS2 sets.
I set $X(k) = e^{-d(k)}$ and I get $C(k) = B(k) X(...
- 2,132
3
votes
1
answer
475
views
How to fomulate the following conditional constraint in MILP?
How can I formulate the following conditional constraint to a linear constraint using indicator variables? Please note that all variables are continuous and $c \ge 0$
$\text{1: if} \ c=0 \ \& \ ...
- 294
6
votes
1
answer
608
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
3
answers
252
views
Problem with binary decision variable constraints in VRP
I would like to create non-linear violation costs in my VRP. I already created my whole VRP with time windows in which I have these decision variable:
...
- 51
2
votes
1
answer
256
views
Inequality Constraint Linearization of a product of an integer and a binary variable
I have thought I had found the answer here: How to linearize the multiplication of an integer and a binary integer variable?
But the answers to that questions didn't help me find a solution for my ...
- 93
2
votes
1
answer
92
views
How to linearize a weighted maximum coverage problem?
Is it possible that the binary variables below be modeled as continuous variables?
\begin{alignat}2\max&\quad\sum _{{e\in E}}w(e_{j})\cdot y_{j}\\\text{s.t.}&\quad\sum {x_{i}}\leq k,\quad&...
- 101
5
votes
2
answers
172
views
Minimizing $x_1/x_2$ over a simplex in the positive orthant
I need to solve the following problem
\begin{align}\min&\quad x_1/x_2\\\text{s.t.}&\quad Ax \leq b\\&\quad x > 0\end{align} where $A$ is a positive matrix.
The best thing I can think ...
- 53
3
votes
2
answers
440
views
Mocking up conditional statements in LP
I would like to know how if condition statements in linear programming can be reformulated using indicator constraints, and hence solved as a mixed integer linear program. Specifically:
1. Is it ...
- 151
5
votes
2
answers
473
views
Linearizing objective function with variables inside an indicator function
I am working on a problem in which I am trying to maximize the average of a variable only for the data that meet a certain condition with a constraint on the number of data that meet this condition. I ...
- 53