Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
223
questions
4
votes
1
answer
306
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 ...
- 30.5k
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 ...
- 501
1
vote
0
answers
51
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 ...
- 30.5k
1
vote
0
answers
40
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 \...
0
votes
1
answer
144
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 ...
CommunityBot
- 1
2
votes
2
answers
89
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$?
- 8,622
1
vote
1
answer
110
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}$ ...
- 1,885
3
votes
0
answers
112
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 ...
- 30.5k
2
votes
1
answer
60
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 ...
- 30.5k
1
vote
2
answers
154
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 ...
- 30.5k
0
votes
0
answers
28
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 ...
- 101
1
vote
1
answer
50
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 ...
- 95
1
vote
1
answer
424
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 \...
- 30.5k
0
votes
1
answer
79
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 ...
- 3,343
1
vote
2
answers
151
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} =...
- 8,450
1
vote
1
answer
163
views
Nonlinear fractional objective function
Could you please teach me when an optimization model with fractional terms in the objective function can be linearized or solved optimally?
I only know that if the objective function has a single ...
CommunityBot
- 1
0
votes
0
answers
75
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
1
vote
0
answers
68
views
Linearization of Conditional Constraints for MIP using Cplex
I'm currently working on a mixed-integer programming (MIP) problem and I'm trying to implement a set of conditional constraints in CPlex. These constraints involve decision variables that are indexed ...
- 1,885
0
votes
1
answer
72
views
Interpret the formulation of a pricing model in crowdshipping
I am trying to run the pricing model from the paper "Designing pricing and compensation schemes by integrating matching and routing models for crowd-shipping systems" on python with Gurobi, ...
CommunityBot
- 1
6
votes
1
answer
719
views
Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?
I have the following network flow model diagram and I have already calculated maximum flow using the R package igraph to be 28. However, what I would like to know ...
- 103
0
votes
0
answers
76
views
Optimize revenue function with log part
I am working on an optimization problem where I aim to maximize revenue. My current model has the following objective function:
$$ Sales(P_i) * log(P_i - const_i))$$ where $P_i$ represents the price ...
4
votes
2
answers
376
views
How to model $C_1=C_2$ implies $b_1 = b_2$
Suppose $C_1 \ge 0$, $C_2 \ge 0$ are continuous variables and $b_1$, $b_2$ are binary variables.
How could I model the following?
$C_1 = C_2 \implies b_1 = b_2$, the opposite does not hold.
- 5,342
-1
votes
1
answer
57
views
How to linearize the multiplication of variables and transform this into an MILP?
Let $C=10$, $U=50$
$P_c,c=1,\cdots,C$ and $\alpha_{u,c},u=1,\cdots,U,c=1,\cdots,C$ are optimization variables
$\alpha_{u,c}$ is binary
$\sigma_{u,c}$, $d_{u,c}$ are known parameters
$\min \sum_{c=1}^...
- 2,211
2
votes
1
answer
95
views
Representing a Multi-Level Categorical Variable using Big-M Method in Linear programming
I'm working with a statistical linear model where I have a variable, ( N ), representing the percentage of charging of a battery. Based on ( N ), I derive another variable, ...
- 1,885
2
votes
1
answer
81
views
How to linearize the multiplication by a binary decision variable?
I am currently optimizing a hydrogen production chain.
I am optimizing the production regime, and the size of the required wind, solar and the electrolyser.
For every hour of the year, the production ...
- 1,885
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
4
votes
3
answers
314
views
Systematic references on linearizing conditional / logical expressions
On this site, one can usually finds questions like “How to transform my expression into linear form?” The expressions usually contain and, ...
- 121
2
votes
1
answer
68
views
How to show that minimizing the epsilon-insensitive loss is equivalent to a quadratic program with inequality constraints?
This question is about an optimization problem that arises in support vector regression (SVR). Suppose you have $N$ pairs $(\vec{x}_n, y_n)$ as data and would like to find a vector of weights $\vec w \...
- 30.5k
3
votes
1
answer
102
views
using milp for a linear complementarity problem
I have to minimize $c^Tx$
subject to $Ax = b$, $x_iw_i = 0$ for all $i$, with $x$ non negative continuous and $w$ binary.
What model should I use to solve this problem?
- 12.9k
1
vote
3
answers
113
views
How to linearize a chain of if-then constraints?
How can I express the process of converting a series of if-then constraints into a linear form?
Let's assume that we have integer variable $x_i$, non-negative variables $y_i^d$, and binary variables $\...
- 30.5k
0
votes
0
answers
45
views
How to linearize such a constraint?
My original content was like this:
Assuming that server $k$ can only allocate corresponding computing functions to MU $i$ after receiving their tasks. Let
$$ y_{i,k,t} = \begin{cases} 1 & \text{if ...
1
vote
1
answer
45
views
$\min\{f(x_1),\dots,f(x_n)\}$ with other constraints
I have an optimization problem which goes:
\begin{align*}
\text{Minimize:}
\\
& \sqrt{x} + \sqrt{y} \tag{NL-objective}
\\
\text{Subject to:}
\\
&3x + 2y \geq 2 &...
- 1,885
3
votes
2
answers
386
views
How to model a binary variable?
I am trying to find a constraint for the following relationship, but am failing a bit at it right now. I want to find a linear constraint that does the following. The binary variable $switch_{ot}$ is ...
5
votes
4
answers
875
views
Rewriting if-then constraints of binary summations
Suppose both $x_{i,j}^{ab}$ and $y_{i,j}^a$ are binaries. Then how can I rewrite the following if-then in linear form?
$\sum_b x_{i,j}^{ab} \ge 1 \implies \sum_{i,j} y_{i,j}^a = 0$
I was thinking of ...
- 147
0
votes
0
answers
68
views
Resource selection problem with non-linear objective function
I have an optimisation problem to solve but I can't model it correctly. Any insight is welcome :)
It has been a few years since my optimisation classes in university, and while I have forgotten a lot ...
- 1
3
votes
2
answers
684
views
Writing a constraint of an integer programming in a linear form
I modeled an optimization problem in an integer programming format. The main constraint I came up with is now nonconvex. I would like to see if there is another equivalent formulation in which the ...
- 30.5k
3
votes
3
answers
235
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 ...
- 8,450
2
votes
3
answers
169
views
Linearization the product of three variables (two binary & one continuous)
Consider the following binary variable $x \in \{0,1\}$ and two continuous real variables $y,p \in \mathbb{R}$.
I am trying to model the following conditional equations as constraints:
\begin{cases}
...
- 8,450
3
votes
3
answers
249
views
Equivalence between constraints in ILP
Let's have binary variables $x$ and $y$. I'd like to define a helping binary variable $z$ such that
$$ z = 1 \; \;\; \mathrm{iff} \; \; \; x + y = 2.$$
If I wanted to express the equivalence between ...
- 1,046
3
votes
1
answer
87
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.5k
1
vote
1
answer
164
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?
- 30.5k
3
votes
2
answers
246
views
Reformulate bilinear binary constraint
I'm a solving a model that has the following constraint:
$$
c_{p,n} = \sum_{s\in S}\sum_{i \in \{1,2,3\} } x_{p,s,i-1} x_{n,s,i}, \forall (p,n) \in C
$$
where both the $c$ and $x$ variables are binary,...
- 3,343
2
votes
0
answers
88
views
The linearization of the logical constraints
I know the logical constraints can be linearized by either the logical representation of whose relation, (for pure binary variables e.g. CNF/DNF) or for general form by using Big-M formulation. As I ...
- 8,450
4
votes
2
answers
297
views
The linearization of the (Iff-and-only-Iff) expression
I am trying to linearize the following expression without using the Big-M formulation, but I cannot convert it. I am willing to know if there exists an efficient way to do that?
$$ Iff \quad (w=1) \...
- 30.5k
0
votes
1
answer
148
views
Converting a piecewise function to a linear equation as a constraint
The value of one of the variable of my model (alpha_1) is given by a piecewise function. Each element of the piecewise depends on the value of some other binary decision variables (X1, x2, x3).
I'd ...
- 3,343
2
votes
2
answers
236
views
Linearizing a disjunctive expression into MILP
I want to linearize the following disjunctive form.
$$\left[\begin{gathered}w_{1}\\x \geq a\end{gathered}\right] \vee \left[\begin{gathered}w_{2}\\x \geq b\end{gathered}\right]$$
where $w_1$ and $w_2$...
1
vote
1
answer
53
views
Linearize constraints on a truncated variable
Let $K$ and $Q$ be two variables, and $Q_\min$ and $Q_\max$ be two parameters. I need a series of linear constraints to define $Q$ vis-a-vis the value of $K$ based on the following rules:
If $K \le ...
- 11
7
votes
1
answer
405
views
How to reformulate (linearize/convexify) a budgeted assignment problem?
I have a scheduling problem at hand. In my system, there is a service station with $M$ service outlets, therefore, the service station can serve $M$ users at a time. But, there are $N$ users $N>M$ ...
- 2,211
3
votes
1
answer
323
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$...
- 37.9k
3
votes
2
answers
117
views
How to linearize or fix this disciplined convex programming error?
How can I linearize this constraint
$$d_{u,c}\sigma \le \|{\bf f}_{u,c}\|^2\le Td_{u,c}$$
$\sigma$ is a very small number based on scale of $f$
$T>0$, ${\bf f}_{u,c}$ is optimization variable, a ...
- 5,342