Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
211
questions
5
votes
1
answer
227
views
Linearize minimum and maximum constraint with variable and constant
Let's say I want to linearize the restrictions: $ \min(0, y) \leq x \leq \max(0, y) $
Then I can define $y_{\max}$ and $y_{\min}$ such that:
$$ y_{\max} \geq 0 \\ y_{\max} \geq y \\ y_{\min} \leq 0 \\ ...
- 153
5
votes
1
answer
218
views
Absolute value in an equality constraint
What is the best way to model or represent an equality constraint which includes an absolute term in the expression:
$$ x = |y| $$
$x \in \mathbb{R^+}$ and $y \in \mathbb{R}$
- 103
6
votes
2
answers
197
views
When should we avoid linearizing a quadratic term?
Some solvers like Gurobi can handle mixed-integer quadratically-constrained quadratic models regardless of their nonconvexity. I have some experience that Gurobi can handle instances of the max $k$-...
- 169
2
votes
1
answer
189
views
How to write constraint with sum of absolutes in Integer Programming?
I found a solution for just one term here
How can we formulate constraints of the form
$$ \sum_{i=1}^n |x_i -a_i| \ge K $$
in Mixed Integer Linear Programming ?
- 203
2
votes
2
answers
415
views
Mixed Integer Programming with product of a binary variable and multiple continuous variables
Suppose we have a binary variable $x$ and two non-negative continuous variables $y_1\ge 0$ and $y_2 \ge 0$. How can we linearize $xy_1 y_2$ ?
FYI, this is a follow up question to this:
How to ...
- 31
2
votes
1
answer
234
views
linearize bilinear quadratic objective terms
I need to model a problem as a linear program. However my working solution contains a (bilinear) quadratic objective term:
$$
\sum x_i * y_i \\
x \in \{0,1\} \\
y \in \mathbb{R}^+
$$
The value of $y$ ...
- 147
3
votes
1
answer
752
views
How to minimize the sum of absolute values
How can I solve a problem such as the following:
$$
\text{minimize}~~~ \sum_{i=1}^n |x_i|
\\
\text{subject to}~~~ A x \geq b
$$
?
Without the absolute values on the variables, it is a simple linear ...
7
votes
2
answers
856
views
Is there a better way of defining a constraint on positive integer variables such that no two variables are the same and are uniquely assigned a value
So suppose I have integer variables $x_1,x_2,\dots,x_N$ and I enforce that the integer variables are bounded i.e $1 \leq x_i \leq N$
I was interested in posing a constraint so that in the collection $...
- 205
4
votes
2
answers
484
views
Transform nonlinear cost function to get LP or MILP
I'm trying to schedule power of multiple prosumers in a microgrid.
The problem includes a cost function with min and max ...
- 143
2
votes
2
answers
206
views
Difference between constraint formulation and performance
I am wondering about the characteristics and performance of some constraints with only binary variables. I assume that solving (integer) linear programs is faster than quadratic ones.
At first:
$$
a,b,...
- 147
2
votes
1
answer
193
views
Linearize function
I have a facility location problem with a non-linear objective;
There are fixed costs $S_j$ to opening facility $j$
$Y_j$ is a binary, $1$ if facility $j$ is opened, $0$ otherwise
$D_j$ is the number ...
- 99
1
vote
0
answers
201
views
Converting quadratic constrains to linear constraint [closed]
I try to convert a quadratic constraint to a linear one:
$$
w_j = \sum w_\text{j,i} \\
w_\text{j,i} = \frac{w_j}{D} \times u \\
w_j,D,u \in \mathbb{N} \\
$$
The values for $w_j$ and $D$ are constant ...
- 147
6
votes
2
answers
547
views
How to solve Rogo Puzzle with an extra constraint?
Given a n×m grid with numbered cells and forbidden cells, the objective of the Rogo puzzle is to find a loop of fixed length through the grid such that the sum of the numbers in the cells on the loop ...
- 1,235
1
vote
1
answer
84
views
If $x=\min\{f(\mathbf{a}),1-\epsilon\}$, how can we model and partition $x$?
I have been dealing with a problem for sometime and although tried different things and asked some questions before, I think the problem might be somewhere that we didn't look before.
Variables $0\le ...
user9659
2
votes
1
answer
72
views
Linearizing $y=\sum_{i=1}^n(z+c)\left(\frac{r_i^2}{1-r_i}\right)\phi_i$
Variables $0\le x< 1$, $y,z\ge 0$. We have a constraint
$$y=(z+c)\frac{x^2}{1-x},$$
where constant $c>0$.
We partitioned $x$ into $n$ intervals of equal length and defined a new variable $\phi_i=...
user9659
2
votes
3
answers
1k
views
How to use condition in cplex?
I want to use conditions to my variable.
dvar boolean x[I][J][K][L]
dvar in h[i]
my code is
...
- 21
5
votes
1
answer
116
views
Linearizing this absolute difference objective function $\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$
For $x_i>0, i=1,\ldots,I$, I tried to linearize this objective function
$$\min\sum_{i=1}^{I}\sum_{j=1}^{i}|x_i-x_j|$$
as
$$\min\sum_{i=1}^{I}\sum_{j=1}^{i}y_{ij}$$
subject to
\begin{align}
& y_{...
user9659
6
votes
2
answers
484
views
How to measure the tightness of MILP models?
Suppose we have a MILP model. How can we say this model is tight or not?
How to make it more tight? Any advice or example?
- 1,235
5
votes
2
answers
807
views
Knapsack - How to optimize bonuses for each pair of items
I am trying to solve a variation of the knapsack problem where every pair of items in my knapsack has a bonus or penalty associated with it.
My knapsack can hold a dozen items
There are thousands of ...
- 197
2
votes
1
answer
113
views
How to optimize multiple linear regressions based on cost?
I have an optimization problem where I'd like to maximize revenue and I have separate variables for cost and revenue.
Building a single unit of a product takes 100 hours of labor
I have a list of ...
- 197
3
votes
3
answers
916
views
Converting if conditions to linear constraints
I have an optimization problem and I want to convert the following if conditions to linear constraints:
If $(y_1 > U_1)$ and $(m_1)$ and $(E_1)$ then $x_1=1$
If $(y_2 > U_2)$ and $(m_2)$ and $(...
- 77
8
votes
2
answers
830
views
MILP Penalty Function Only for Negative Values
This is (hopefully) an easy answer but I haven't dealt with this before.
I have a MILP which includes an unbounded, continuous decision variable. However, I generally don't want this decision ...
- 721
4
votes
1
answer
107
views
Modeling $x=1$ iff $y\leq D$ and $x=0$ otherwise (either-or-constraints)
We have decision variables $x\in\{0,1\}$ and $y>0$. We know that $x=1$ if and only if $y\leq D$ and $x=0$ iff $y>D$. $D>0$ is a model parameter.
How I modeled these constraints is
\begin{...
user9659
5
votes
1
answer
341
views
Can we linearize the division of a binary variable by a continuous variable?
I'm trying to solve an MINLP problem where the following division term is appearing in the objective:
$$z_r = \frac{x_{ry}}{\sum_r d_r x_{ry}}, \forall r, y,$$ where $x_{ry}$ is a 2D binary variable ...
2
votes
1
answer
296
views
How can I linearize this nonlinear variable relationship?
Assume a mathematical optimization problem with two positive continuous variables:
0 <= x <= 1
0 <= y <= 1000
I am seeking an efficient way to express ...
- 29
3
votes
2
answers
248
views
Piece-wise linear approximation of a constraint
We have a decision variable $0<y<1$ and the following constraint
$$z=\frac{y^2-y+1}{y(1-y)},\tag{1}$$
We also have another constraint
$$y=f(x),\tag{2}$$
where $f(x)$ is a linear function of $x$.
...
user9659
5
votes
2
answers
171
views
Linearizing $x^2/(1-x)$ by partitioning the interval $0<x\le X$
We have two decision variables
\begin{align}
& 0<x\le X,\\
& 0<y\le Y,
\end{align}
where both $X$ and $Y$ are two sensible upper bounds on our decision variables.
We also have a ...
user9659
3
votes
1
answer
324
views
Linearizing division of two variables
For all $i \in I,j\in J$ and $k\in K$, define variables $x_{ij}, z_{ijk}\in\{0,1\}$, $y_{ij}\geq 0$ and constants $c_j, e_{ijk}, d_j, f_j >0$.
We have the following constraint
$$\sum_{j\in J_1}c_j\...
- 103
4
votes
1
answer
235
views
Can we simplify (perhaps linearize) this constraint?
We are dealing with a stochastic model and one of the constraints is
\begin{align}
y_j=\frac{\sum_{i \in I}\sum_{k \in K}\mathbb{E}\left[X_{ik}^2\right]x^k_{ij}}{\sum_{i \in I} \sum_{k \in K} \mathbb{...
user9659
3
votes
0
answers
82
views
Function approximation of a complex objective function
I would like to approximate the following objective function using a simpler function that can use be defined in gurobi.
\begin{equation}
\min_{I_{i,v}} \ \sum^{N_v}_{v}\sum^{TT_v}_{i} \ C_{loss,...
- 347
2
votes
2
answers
259
views
Change the objective function formula change the complexity of a linear program?
I have a linear program, where I can use it with the same constraint to minimize objective 1 or minimize objective 2. I noted that when I use the formula of objective 2 the problem can be solved with ...
- 335
4
votes
1
answer
261
views
Can you calculate the mean of some MIP variables using linear constraints?
got a lingering question from a graduate course in integer programming that's been bugging me ever since.
Is it possible to find the mean of some variables in a MIP without resorting to quadratic ...
- 140
4
votes
0
answers
267
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 ...
- 347
3
votes
1
answer
228
views
Range limits on terms in the objective function of an LP
I have a linear maximization problem with an objective as follows: $$\sum c_i\cdot\text{exp}_i$$ where $c_i$ are constants (positive or negative) and $\text{exp}_i$ are linear expressions of the free ...
- 542
3
votes
1
answer
286
views
If variable falls below a certain value, include difference to set value in objective
I think its easiest to describe my goal first and continue with my implementation and the resulting problems!
My goal:
Using Pyomo as interface and Gurobi as solver, if a variable $x_{i,t}$ falls ...
- 33
6
votes
1
answer
366
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
323
views
How to optimize on a fixed-cost based on number of results?
I am trying to create an LP problem which is like the knapsack problem but where there is a fixed bonus/penalty based on the number of items chosen.
There are 20 items to choose from with some weight ...
- 197
5
votes
1
answer
2k
views
How to linearize the product of two integer variables?
Given two integer variables $L_x \leq x \leq U_x$ and $L_y \leq y \leq U_y$, how can we linearize the product $x \cdot y$?
- 1,467
2
votes
1
answer
110
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,965
3
votes
1
answer
139
views
Linearization of problem with affine linear functions
Problem: Write the following task as a linear program: $\min f(x),x\in[-2,5]$ where
\begin{align}f(x) := \begin{cases}
-2x+2,&\quad-2\le x<-1\\
-x+3,&\quad-1\le x < 1\\
2,&\...
- 41
7
votes
2
answers
246
views
Product of weighted binary variables equivalent to sum of weighted binary variables?
I'm working on an optimization problem with a non-linear objective function of the form $$\max\prod_{i=1}^{n}(1-a_{i}x_{i}).$$
The objective function represents the combined probability of success for ...
- 313
5
votes
1
answer
330
views
If continuous variable < constant then same variable = 0
When I come across with a situation needs an if-then constraints I visit Larry's post. I am a bit confused with the titled constraint this time because I am not trying to set $y$ based on $x$ but ...
- 1,239
1
vote
1
answer
149
views
Linearization of constraints in a ILP
I have been working on a Graph Theory problem for my thesis and got stuck about the linearization of some constraints. I am hiding everything, constraints, variables and so on, of my problem not ...
- 583
4
votes
1
answer
103
views
How to know if a combinatorial optimization problem is linear or not?
I want to know if a combinatorial problem like the knapsack problem is linear or not. And how do we know if a given problem is convex or not?
- 335
4
votes
1
answer
472
views
How to linearize a non-convex optimization objective function?
The non-convex multi-objective optimization problem in my case is defined below:
Objective 1: Minimize $f_1(X_1,X_2)=C_0+C_1(1/X_1)+C_2(X_2/X_1)+C_3X_1+C_4X_2+C_5(X_2^2/X_1)$
Objective 2: Minimize $...
- 169
4
votes
1
answer
175
views
Alternate formulation for modeling inventory constraints
I'm working on a inventory optimization problem where inventory used at a time-period is computed based on price-bucket that is selected for an item. Problem contains multiple items (around 10K), 15-...
- 959
3
votes
2
answers
498
views
How to linearize a constraint with a maximum of a linear function
I want to linearize the following statement into a MILP: $\forall x\in \mathbb{R}^{m}$ satisfying $Cx \le d$, $\exists i\in \{1,\cdots,m\}$ such that $a_i^Tx \ge b_i$, where $a_i$ and $b_i$ are given ...
- 109
6
votes
2
answers
372
views
How to model this expression?
Suppose $0\le x \le 1$ is a decision variable and $\gamma(x)$ is defined as follows:
$$
\gamma(x)= \begin{cases}
\theta & x>0\\
0 & x=0
\end{cases}
$$
where $0\le \theta\le 1$.
In my model, ...
- 2,140
6
votes
2
answers
138
views
Linearise $\max\{ y_{t-1} + a_t - z_t ,0\}$
I'm trying to linearise these constraints, but I am not able to do correctly do it.
$$y_t = \max\{ y_{t-1} + a_t - z_t, 0 \} $$
My attempt was this:
\begin{align}y'_t &\geq a_t - z_t\\y'_t &\...
user4387
5
votes
2
answers
697
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,155