Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
264
questions
0
votes
0
answers
39
views
How to Linearize the Product of Two Continuous Variables with Known Bounds in GAMS MILP Model
I have a Mixed-Integer Linear Programming (MILP) problem in GAMS where I need to linearize a bilinear term involving two variables. Specifically, I have the following equation:
$$
\text{eh17}(m,n,t) : ...
0
votes
0
answers
51
views
How to linearize the product between a discrete positive variable and a continuous variable limited between 0 and 1
Suppose we have a integer variable x and continuous variable y in [0,1]. What is the best way to linearize the product xy ? The problem is that the x variable is limited by 0 <= x <= M and the ...
0
votes
0
answers
44
views
Probabilistic interpretation of integer linearization solutions
Can we generate approximate integer/binary solutions using pure linear programming?
Suppose that I want to assign $resource_{i}$ to $team_1$ else $team_2$. A solution matrix, M of shape [i,2] could ...
- 559
0
votes
0
answers
87
views
MIP constraints for a maximum value
Is there a better way to model a constraint(s) that ensures $x$ is the maximum value among a set of unique variables, say $\{y_1, y_2, \dots, y_n\}$, instead of directly setting $x$ to be greater than ...
- 593
0
votes
1
answer
53
views
Expressing a chain of boolean ORs for variable to be squeeze within an interval?
I am a network engineer facing a modeling challenge related to the delay constraints of a network transmission problem. My objective is to capture the behavior of transmission delays under different ...
0
votes
1
answer
51
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
43
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
94
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
78
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
212
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=
\...
- 109
2
votes
2
answers
201
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 $...
- 246
2
votes
1
answer
80
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
232
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
146
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
142
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
310
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
106
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,397
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
87
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,397
1
vote
1
answer
46
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
37
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*}
...
- 246
0
votes
0
answers
66
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,397
0
votes
2
answers
93
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
168
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
63
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,397
2
votes
1
answer
226
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,397
0
votes
0
answers
117
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
68
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
131
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
93
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
117
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
70
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
234
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
87
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 ...
- 115
0
votes
0
answers
59
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
252
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
143
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
99
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$,...
- 105
4
votes
1
answer
330
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 ...
- 559
1
vote
0
answers
70
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
83
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
102
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
130
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
192
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
126
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
65
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
103
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