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
2
answers
65
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 $\...
- 175
1
vote
0
answers
25
views
LP - Shift changes and days off
This is a follow-up question regarding this topic. I recreated the post and added information from the linked post as requested. Within this post, a binary variable $l_{it}$ was introduced, which ...
0
votes
0
answers
41
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
1
vote
1
answer
35
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 &...
- 11
3
votes
2
answers
355
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 ...
- 31
5
votes
4
answers
836
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 ...
- 175
3
votes
2
answers
636
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 ...
- 133
3
votes
2
answers
326
views
How to model C1 = C2 implies b1 = b2
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.
- 2,132
0
votes
0
answers
62
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
3
answers
189
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 ...
- 33
2
votes
3
answers
121
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}
...
- 103
3
votes
1
answer
61
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....
- 28.2k
3
votes
3
answers
214
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 ...
- 133
1
vote
1
answer
119
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?
- 21
2
votes
0
answers
54
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 ...
- 7,664
4
votes
2
answers
283
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) \...
- 43
3
votes
2
answers
181
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,...
- 183
0
votes
1
answer
62
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 ...
- 67
1
vote
1
answer
50
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
1
vote
1
answer
128
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 ...
2
votes
2
answers
215
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$...
- 7,664
3
votes
1
answer
235
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$...
- 2,191
2
votes
0
answers
33
views
Choosing upper and lower bound using big-M [duplicate]
This question is related to my previous question posted here: Piecewise constraint using big-M notation and this question posted on the math stackexchange: https://math.stackexchange.com/questions/...
- 43
3
votes
2
answers
104
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 ...
- 2,191
1
vote
1
answer
68
views
MILP: Substituting products with additive logarithms
I would like to linearize a product, for example $a*b$. if I solve my solution in log space, I can formulate it as $a+b$ and when my final output is returned, remember to convert back to original ...
- 471
4
votes
1
answer
165
views
How to solve a "nearly" linear program
Given a positive integer $n$, a constant $k=2/3$, and $7$ variables $x_1, x_2, x_3, x_{12}, x_{13}, x_{23}, x_{123}$ (non-negative reals or integers) I would like to find:
$$\min \binom{x_1}2$$
...
- 393
2
votes
1
answer
115
views
Multiple absolute values with multiple variables in an LP
Assume that we have a LP with the constraint
$$ \sum_{j} \left(c_j x_j + |c_j x_j - \alpha_j + \beta_j|\right) \leq y $$
and
$$\alpha_j + \beta_j \leq \lambda_j $$
for all $j$, where the (positive) ...
- 145
5
votes
3
answers
197
views
MIP constraint with sum of decision variables having certain value : $\sum_{i=1}^nx_i = 2 \implies \delta = 1$
I want to formulate a MIP constraint such that :
$$\sum_{i=1}^nx_i = 2 \implies \delta = 1$$
$x_i, \delta \in \{0, 1\}$.
My problem is that delta should be one when this sum is exactly 2 and not ...
- 235
3
votes
1
answer
63
views
Outer approximation approach for MINLP
Does anybody know why in the outer approximation approach for MINLP it is not necessarily/needed to solve MILP to optimality? What is the rationale or explanation behind it?
2
votes
1
answer
74
views
Expressing inner product of binary variables in MIP
I have a $m$ by $n$ matrix $X$ of binary variables in my MIP which represents a list of $m$ items each belonging to one of $n$ categories. $m$ is usually around $1,000$ while $n$ is much lower at ...
- 123
3
votes
0
answers
90
views
Linearize objective function with non-linear terms
I have a problem with linear constraints but in the objective function I want to have some linear terms along with a $x^2$ term. So it is like the following:
$$\min \sum \limits _i \sum \limits _j (a[...
2
votes
1
answer
439
views
Optimization problem with if condition as constraint
I am trying to solve an optimization problem where the constraint contains absolute values and I am not sure how I can express this in a 'Pyomo-friendly' way.
Consider the following optimization ...
- 175
3
votes
1
answer
229
views
Linearize objective function in MILP
I have an objective function that I want to linearize but want to confirm that I'm doing it correctly. There are some constraints that are linear in $x$ but they're unimportant for the problem. The ...
- 45
3
votes
2
answers
229
views
How to model logic constraint: $y=1$ if $a\le x\le b$ and $y=0$ otherwise?
I am trying to formulate indicator-type of constraints. $y$ is binary $0$ or $1$ and $x$ is a continuous variable.
$$ y =
\begin{cases}
1, & \text{ if } a \leq x \leq b \\
0, & \...
- 53
2
votes
1
answer
145
views
Linearize a higher order polynomial objective function?
My question up front with context below:
Is there a generalized linearization possible for a higher order polynomial (max degree 6 in my case) involving a mix of binary and real variables? If not, ...
- 23
2
votes
1
answer
145
views
Why MiniZinc do not do convert to linear constraint a quadratic constraint?
I would like to know which are the advantage to do not convert quadratic expressions into linear expression in MiniZinc. For example let be the following simple MiniZinc code
...
- 179
2
votes
1
answer
110
views
Linearize a product of binary variables with 2 indexes
I have the following inequality that I would want to linearize.
Consider that $r_{ij}, x_{ij}, y_{ij}$ are binary variables defined for every pair of nodes $(i,j) \in A$. Also, I have a set of nodes $...
5
votes
1
answer
215
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
177
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
175
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
172
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
375
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
219
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
618
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
845
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
447
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
190
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
185
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
183
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
541
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,120