Questions tagged [linearization]

For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.

Filter by
Sorted by
Tagged with
2 votes
3 answers
98 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
48 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....
  • 27.3k
3 votes
3 answers
190 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 vote
1 answer
103 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
47 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,281
4 votes
2 answers
270 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) \...
3 votes
2 answers
148 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
53 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
49 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
2 votes
1 answer
62 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
202 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,281
3 votes
1 answer
199 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,179
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
100 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,179
1 vote
1 answer
65 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
160 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
85 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
183 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 ...
3 votes
1 answer
62 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
57 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 ...
3 votes
0 answers
80 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
364 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
212 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 ...
3 votes
2 answers
196 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, & \...
2 votes
1 answer
120 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
140 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
106 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
206 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
141 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
163 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$-...
2 votes
1 answer
152 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
339 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 ...
2 votes
1 answer
201 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
515 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
841 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
415 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 ...
2 votes
2 answers
180 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
178 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 ...
1 vote
0 answers
154 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
539 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 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 ...
user avatar
2 votes
1 answer
70 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=...
user avatar
2 votes
3 answers
733 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
112 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_{...
user avatar
6 votes
2 answers
404 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?
5 votes
2 answers
792 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
84 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
692 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
712 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 ...
4 votes
1 answer
89 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{...
user avatar