Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
259
questions
0
votes
1
answer
47
views
Linearization of two constraints: one with a conditional max and one with a sum with a variable as index
I have these two quite nasty constraints I have tried to linearize. I am trying to dynamically control if you are allowed to plan producing product p. You are allowed to do it if the product arrived (...
0
votes
0
answers
36
views
What's the linearization of the product between a discrete variable and a continuous varibale?
I am trying to linearize the product $z=xy$, where $x$ is an integer variable and $y$ a continuous variable, both non-negative, for an optimization problem. I have tried the SCIP formulation:
$v_{bn} \...
0
votes
1
answer
75
views
How to write conditional constraints and sum the result in Linear Programming in Python?
I want to use the sum of a series of linear expressions as objective and constraints. These linear expressions are chosen to be included or not based on some conditions. I can achieve it in Excel ...
- 13
0
votes
1
answer
76
views
PULP: Optimization Assignment of Bicycle production per month
Q1. If bicycles of types A and H are produced, then bicycles of type C can be produced with 20% shorter working hours, while selling profit of bicycles type H can be 20% higher.
Q2: If bicycles of ...
3
votes
1
answer
199
views
How to linearize the following logical constraints?
I am having trouble linearizing the following logical constraints.
$x,y,z$ are non negative continuous variables such that $x=y+z$, and $A$ is a positive parameter. I would like to linearize
$$
y=
\...
- 79
2
votes
2
answers
184
views
Are McCormick Envelopes exact for the following class of optimization problems?
I have the following optimization problem:
\begin{align*}
\text{minimize} \quad &\mathbf{c^T x} \\
\text{such that} \quad &\mathbf{x} \in S.
\end{align*}
Here, $S$ is a polyhedron of the form $...
- 205
2
votes
1
answer
78
views
Minimizing sum(abs(Ax-c)) for binary decision variables - terminology and methods?
My problem requires choosing a fixed number of vectors from a large set of vectors such that the sum of these vectors is close to some known target vector. That is, given known parameters:
$$
l, m, n \...
- 1,857
2
votes
1
answer
223
views
Set a limit on value change of a binary variable
I am working on an Energy Management problem. The objective is to minimize the electricity bill for the customer.
I have a time-series data with 15 min. intervals spanning the course of 1 year. The ...
2
votes
1
answer
139
views
Priority based demand fulfilment in Linear Constraint
Say I have 3 sources. D1, D2, D3. their capacity is 100, 200, 400. I want to create some constraints such that First D1 is depleted then D2 and then D3. But the catch is you cant use min or max ...
2
votes
1
answer
126
views
How to model the constraints of min and max in cvxpy
I have a continuous variable $x_{ij}\in[0,1]$ and I need to write the following constraint:
$$M_i-m_i+1\leq C_i$$ where $M_i=\max\{j: x_{ij}>0\}$ and $m_i=\min\{j: x_{ij}>0\}$
- 403
4
votes
2
answers
309
views
Linear condition between two continuous variables
There are two real variables $x$ and $y$. The conditions are such that:
if $y\le 0$, then $x=0$
if $y>0$, then $x=y$
How to write linear equations or inequalities to satisfy both the conditions?
- 41
0
votes
1
answer
105
views
How to model this constraint in a better way?
I have a resource allocation problem. There are $M$ users and $N$ resources (machines).
One user can be assigned to multiple resources/machines.
But maximum $B$ machines can be activated at a time for ...
- 2,377
3
votes
1
answer
194
views
Reformulate constraints
I have the following constraints and am wondering whether I can formulate the whole thing more narrowly and with fewer constraints. $x_{itk}$ is binary and $u_{it}, v_{itk}\in [0,1]$. $M$ is a Big-M ...
2
votes
1
answer
84
views
Is the linearization with first-order Taylor approximation correct?
I have a QP problem as
$\min \hspace{2mm} x^TQx-c^Tx$
here $x$ in binary
I want to transform it into a MILP by writing the objective function as
$\min \hspace{2mm} z-c^Tx$
and then adding a constraint
...
- 2,377
1
vote
1
answer
45
views
Converting a function composing of multipe pieces into a linear equation
I have a variable (alpha) which depends on some other binary variables, denoted as X_i. So, for some combination of other variables, alpha may take a value (Beta_j). I added some auxillary variables (...
- 97
0
votes
1
answer
36
views
Add second "constraint" to model a binary variable
in my model I have the binary variable $f_{ij}$ which pushes a time-dependent $j$ integer variable $D_{ij}$ to zero if $f_{ij}$ takes the value 1 and keeps the integer number if $f_{ij}$ equals 0. Yes,...
- 89
1
vote
1
answer
88
views
How to model $\max\limits_{x\in X} \min\limits_{y\in Y} \max\limits_{z\in Z} f(z)$ as single MILP
I have the following optimization problem:
\begin{align*}
\max\limits_{x\in X} &\min\limits_{y\in Y} \max\limits_{z\in Z} & f(z) \\
&\text{such that} & (x, y, z)\in P
\end{align*}
...
- 205
0
votes
0
answers
64
views
Is it possible to transform MIQP into MILP without introducing new variable?
I have a QP optimization problem in the form
$$\min {\bf x}^T{\bf Qx}-{\bf c}^T{\bf x}$$
here $\bf Q$ is a symmetric matrix.
$\bf x$ is the optimization variable, and it is binary.
Is there a way to ...
- 2,377
0
votes
2
answers
90
views
linearizing a constraint involving an absolute function
I would like to know what is the best way to linearize a constraint involving an absolute function. More precisely, imagine I have three binary variables and their relationships is as follows:
|x-y| = ...
- 97
1
vote
1
answer
89
views
Linearizing a quadratic constraint
I am working on a quadratic conic optimization problem, but I have discovered that it would be preferable if the quadratic constraint is linearly approximated. In other words, I need some way to make ...
0
votes
1
answer
59
views
How to linearize this L0 norm of a vector?
I have an QP optimization problem.
$\bf x$ is the binary optimizaion variable of size $12\times 1$.
One of the constraints is non-linear/non-convex.
The constraint is L0 constraint.
The constraint I ...
- 2,377
2
votes
1
answer
216
views
How to transform a binary QP into an MILP?
I have a binary quadratic problem with objective ${\bf{x}}^T{\bf{Qx}}+{\bf{c}}^T{\bf{x}}$
subject to
${\bf{A}}{\bf{x}}\le{\bf{b}}$
${\bf{A}}_{eq}{\bf{x}}={\bf{b}}_{eq}$.
here ${\bf{x}}$ is binary.
...
- 2,377
0
votes
0
answers
116
views
why this little constraint changes my whole program?
I'm trying to linearize a CP in ILOG CPLEX.
I have the following constraint that I want to linearize (I already simplified it with the big M) :
...
0
votes
0
answers
66
views
Why are these two constraint equations not equivalent?
I've made a CP Model of an hospital in ILOG CPLEX and I want to test the performance of the CPLEX version of it.
In my CP model, I have the following constraint :
...
0
votes
2
answers
126
views
Converting a piecewise function to linear equations
I am trying to build a MILP model. In this model, I have a dependent variable (alpha) that its value depends on the value of some other variables (or different combination of some other variables). In ...
- 97
-1
votes
1
answer
74
views
How to linearize a product of an integer and a binary variable
i have this constraint right here, which is not linear. How would i linearize such a product. $number_t$ is a positive integer and $new_t$ and $reset_t$ are binary.
$$number_t = (number_{t-1}+new_t)\...
- 71
1
vote
1
answer
112
views
Convex approximation of a constraint
I have a constraint given as
$
\left|x_n+\beta x_{n+ 1}\right|-\varepsilon_{ky}\left|x_{n}\right|\leq0\hspace{1em}\forall n=1,2...,N
$ I need to convert this into a convex form to implement in CVX. $...
- 37
0
votes
1
answer
67
views
Formulation of a stepwise linear approximation
I am currently trying to solve an MILP in Gurobi. Unfortunately, Gurobi does not support non-linear functions and I would like to do the following. I currently have the following constraint. It ...
- 139
3
votes
2
answers
232
views
Convex equivalent of a constraint
I have a constraint as follows in my MILP model:
$$
\sum_{e} (a_1(e) - a_2(e))^2 \leq M
$$
Where, $a_1(e)$ and $a_2(e)$ are binary variables. Would you please guide me how can I find the equivalent ...
0
votes
1
answer
85
views
How to represent "if $y_{it} = 1$ and $z_{jt'}=1$ then $x_{ij,t+t'}=1$"
There is a fulfillment problem in the e-commerce logistics field, where the fulfillment of each order is composed of a main transport (from City A to City B, referred to as a route) and an end ...
- 105
0
votes
0
answers
58
views
Better formulation of bilinear terms
I am working on an optimization problem where I need to formulate a constraint that represents the total sales value under specific conditions. The challenge lies in creating an expression that ...
- 23
2
votes
1
answer
251
views
Replace the constraint using ==> by a linear formulation
I would like to know how to express the continuity constraint without using a decision variable in the conditional form. My challenge is to stay with a linear formulation.
I will start to explain my ...
1
vote
1
answer
141
views
How do I linearize such a constraint?
I was wondering, how one would linearize such a constraint, to make it applicable to LPs.
$ a_{i}=(a_{i-1}+b_{i})(1-c_{i})-d_{i}$
$a_i$ gives information of the number of assigned jobs to machine $i$. ...
2
votes
1
answer
96
views
How to transfer an objective with separate positive and negative parts into linear programming
I've got to deal with an optimization problem as follows,
$$
\begin{aligned}
\max_{x,y} & a^Tx+y^TKx\\
{s.t.}&Ax=b\\
&{Cx}\leq d\\
l&\leq y\leq u\end{aligned}
$$
where $x \in \bf{R}^n$,...
4
votes
1
answer
328
views
Optimization problem with the Harmonic number
I have an optimization problem:
\begin{align*}
\text{ minimize } \sum_{i=1}^n H(x_i)
\\
\text{ subject to } Ax \geq b, x\geq 0, x\in \mathbb{Z}^n
\end{align*}
where $H(n)$ is the $n$-th Harmonic ...
- 1,015
1
vote
0
answers
31
views
Moment based linearization of PDF for LP based optimization
Suppose I’m interested in modeling risk/volatility using the Cauchy distribution and I’d like to optimize some allocations using linear programming.
The Cauchy distribution is quadratic in nature but ...
- 551
1
vote
0
answers
65
views
transform minimize weighted sum of absolute value into a linear optimization
For example, we have an optimization problem
$$
\min \sum_{i=1}^{n} |w_{i} - a_{i}| b_{i} \quad \text{s.t.} \quad \sum_{i=1}^{n} c_i w_i = 0
$$
and $a_i, b_i, c_i$ are given. How to convert it into a ...
- 11
1
vote
0
answers
74
views
How to linearize a product and ratio of $x$ and $y$ where $x$ is binary and $y$ is a continuous variable?
I am an electrical engineer who is currently learning about optimization. From this post, they have shown how to linearize the product of two binary variables.
But in my case, I have a product $x \...
2
votes
2
answers
96
views
How to linearize the product of a binary and a negative continuous variable?
Suppose we have a binary variable $x$ and a negative continuous variable $y$. How can we linearize the product $u=xy$?
- 31
1
vote
1
answer
125
views
How to linearize the following constraints
Given the following two expressions:
$ x - \frac{1}{T}\sum_{i} y_{i}$
$ x - \frac{1}{Q}\sum_{i} \beta_{i} y_{i}$
where $x \in \mathbb{Z}_{+}$, $y \in \mathbb{R}_{+}$, and $T$, $Q$ and $\beta_{i}$ ...
- 113
0
votes
1
answer
186
views
Production scheduling
I'm formulating a scheduling problem with the following decision variables:
$$X_t \space \text{is power sold to market in time period t} \\
Y_t \space \text{is power used for production in time period ...
3
votes
0
answers
124
views
From Quadratic to MILP?
I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP:
(QP) $\min c^T x + x^T Q ...
- 1,240
2
votes
1
answer
64
views
how to linearize if-then when having an operand?
if $x_{i,j,p,s}$ and $y_{i,j,p,s}$ are binary and $z_i^s$ is integer; how to enforce:
$$
((x_{i,j,p,s}=1) \land (z_i^s \ge 5 )) \implies y_{i,j,p,s}=1
$$
The value of $z$ in my problem could be 1 to ...
- 33
1
vote
2
answers
157
views
Matrix lookup modelling variants
As part of a bigger model I have a matrix of variables $x_{ij} \geq 0$ and a "selector" set of variables $y_j \in \{0,1\}, \sum_j y_j = 1$.
From $x_{ij}$ I'd like to get the variables of ...
- 113
1
vote
0
answers
88
views
Handling Variable Division in CVXPY for Calculating Annualized Rate of Change
I am working with a dataset that contains multiple entries for different IDs across various years. Some IDs might have a gap of years between entries. My goal is to solve an optimization problem using ...
- 111
1
vote
1
answer
52
views
How to linearize stepped pricing in a route assignment problem
There is an allocation problem, while we have to assign logistics routes to multiple candidate carriers.
For simplicity, let's assume there are only two routes, $A$ and $B$, with two candidate ...
- 105
1
vote
1
answer
435
views
Is it possible to do a linearization without introducing new variables?
I have three binary variables $x_{i,j}^{m,r}$ , $y_i^{m,r}$, and $z_i^{m,r}$. There is another integer variable $w_i^r$. And I want to linearize the following logic:
$$ \sum_{m} x_{i,j}^{m,r} \ge 1 \...
- 53
0
votes
1
answer
152
views
applying a piecewise linearized equation in pulp
The background is I'm building a toy rent vs. buy mortgage calculator. I am an experienced software engineer but my math skills are 20 years behind me and I admit to being very lost.
I've been using ...
- 101
1
vote
2
answers
263
views
Linearizing if else conditions in ILP
We are given three binary indicator variables $X_{ij}, Y_{jk}$ and $Z_{jl}$. Write linear constraints such that,
a) if $X_{ij}$ is equal to 1, then for that $j$ when $X_{ij} = 1$, exactly one $Y_{jk} =...
- 917
0
votes
0
answers
99
views
Transforming a quadratic constraint into a linear constraint
I have a problem with a quadratic constraint and I want to transform it into a linear constraint. This would help to reduce the computational time of my problem.
Following constraint should be ...
- 11