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
0
votes
1answer
133 views

Which linearisation technique is correct?

I have the objective function (Maximally Diverse Grouping Problem) as $$\max\sum_{g=1}^G\sum_{i=1}^{N-1}\sum_{j=i+1}^{N}d_{ij}x_{ig}x_{jg}$$ Here, $d_{ij}$ are known parameters, and $x_{ig}$ and $x_{...
2
votes
1answer
58 views

How to linearize inequalities having max or min?

I'm modeling an LP problem in which I have to maximize an objective function. Two of the constraints are the following, where $k_i$ are constants and $x_i$ decision variables (continuous). Could ...
2
votes
1answer
91 views

How to deal with log0 in optimization problem

I am adding some constraints to my model described in my previous post, where a discontinuous piecewise-quadratic functions is the objective to be minimized in cvx. Here I have an additional terms, ...
5
votes
1answer
150 views

How to treat a system of bilinear constraints

A model contains constraints of the following form $R(k) \leq X(k) G(k)$ where $X(k)$ binary and $G(k)$, $R(k)$ non-negative variables. The index $k$ runs from $1$ to $50$. I linearise the equations ...
2
votes
1answer
51 views

Constraints that set values to binary variables depending on other binaries

I am trying to write a mathematical problem that involves some conditions based on binary variables. More specifically, I have a set of three binary variables $d_1$, $d_2$, $d_3$ and depending on ...
1
vote
1answer
122 views

How to linearize the product of a binary and a continuous variable? [duplicate]

Suppose we have a binary variable $b \in \{0, 1\}$ and a continuous (possibly negative) variable $y \in \mathbb{R}$. How can we linearize the product $b \cdot y$?
1
vote
1answer
124 views

Non-linear optimization local or global solution

In an NLP, I have a constraint that I would like to formulate in a convex manner preferably without introducing binary variables and/or big M formulations if possible. The actual problem is non-convex ...
4
votes
2answers
190 views

Mixed-integer optimization with bilinear constraint

So I have an optimization problem of the following form: \begin{aligned} \max_{x,y} \quad & \sum_i x_i \\ \text{s.t.} \quad & \sum_i x_iy_i \leq a \\ \quad & x_{\min} \leq x \leq x_{\max} ...
2
votes
3answers
120 views

Linearizing a Max Function in the constraint - not working

I have a minimization function which is in its simplest form looks like below. I am including the index of the variables. ...
3
votes
1answer
157 views

Linearizing a quadratic function with more variables or not in Gurobi?

Suppose I want to set the price $0 \le p_t \le p_{max} $ and based on the price, demand is determined $D_t(p_t)=a-bp_t$. Inventory level at each time is denoted by $I_t$ and it is determined by $I_t= ...
2
votes
1answer
242 views

How can I convexify (allowed some approximation) the objective function?

I have a known matrix, $H$ of size $U\times B$. The optimization variable is $D$ of same size, which is binary Now I have $$S_u=\frac{\sum\limits_{b=1}^{B} D_{u,b}H_{u,b}}{\sum\limits_{b=1}^{B}H_{u,b}-...
1
vote
1answer
187 views

Linearize x different of y in ILP

I am surprised I couldn't find an already written answer for my question in the internet. I want to linearize $x$ different of $y$ for two nonegative integer decision variables. I am not considering ...
3
votes
0answers
71 views

How to linearize a max min objective function?

Let us suppose that I have a $\max \min$ objective function that only depends on one set of variables: $\underset{x}\max \underset{y}\min dy$ Associated with the linear set of constraints and right ...
1
vote
1answer
119 views

MILP constrained by the minimum number of satisfied constraints

I have an MILP where we have $$ t_k = \sum_i P_i\cdot C_{ik} : P_i\ \in \{0,1\}, C_{ik} \in I^+ $$ and our model is constrained by the number of times $t_k$ is bigger than a certain value $T_k$. $$ \...
1
vote
1answer
87 views

How to transform this problem with logarithmic objective function into an approximated convex optimization problem?

I have an objective function as follows $\underset{x_{m,n}}{\max}\hspace{1mm}\hspace{1mm}\sum_{m=1}^{M}\log_2\left(\frac{\sum_{n=1}^{N}(1-x_{m,n})\omega_{m,n}+z}{\sum_{n=1}^{N}x_{m,n}\omega_{m,n}}\...
0
votes
1answer
79 views

How to linearise this nonlinear constraint?

I have a constraint in the form $\sum_{n=1}^{N}x_{m,n}\omega_{m,n}\ge (t_u-1)\beta_u, \forall u, u=1,2,\cdots, U$ where $x_{m,n}$ is binary variable $t_u$ and $\beta_u$ are continuous optimization ...
3
votes
1answer
95 views

Maximizing a piecewise-linear convex function

Note: Initially posted on MathOverflow. I am working on an optimization problem where some of the terms of the objective function to maximize are expressed as a piecewise linear function of variables:...
1
vote
1answer
88 views

How can I linearise this nonlinear proportional relation constraint?

My optimisation problem has a constraint in the form \begin{equation} \begin{array}{*{35}{l}} \text{}\hspace{16.5mm}\text{ C4:} \hspace{2mm}\sum_{u=1}^U d_{u,1}L_{u}:\sum_{u=1}^U d_{u,2}L_{u}:\cdots:\...
8
votes
2answers
2k views

How to linearize a constraint with max

I would like to linearize a constraint with max. I have the following constraint: $$\max_{pcj}X_{pwcj}\leqslant L_{wk}.$$ With this constraint, I would like to ensure that for $\forall w \in W$, no ...
3
votes
1answer
88 views

Linearize $\max x_i\ge1$

I'm trying to linearize this optimization problem ($S_j$ is a subset of variables): \begin{align}\min&\quad\sum_{x_i \in X} x_i\\\text{s.t.}&\quad\max_{i \in S_j}x_i\geq 1\quad\forall S_j\\&...
5
votes
2answers
620 views

How to transform this logical if-then constraint?

Consider the binary variables $x, y, z \in \{0,1\}$. I'd like to formulate the two if-then constraints: $$ x + y \geq 2 \implies z = 0, \tag{1} $$ $$ x + y \leq 1 \implies z = 1. \tag{2} $$ Constraint ...
7
votes
1answer
107 views

Maximizing a Ratio/Percent

I'm using cvxpy to model a problem. Inside a very large and complex LP, I create two continuous, affine (unconstrained) expressions: $x$ and $y$. Due to how they ...
27
votes
1answer
3k views

How to linearize the product of a binary and a non-negative continuous variable?

Suppose we have a binary variable $x$ and a non-negative continuous variable $y$. How can we linearize the product $x y$?
-2
votes
1answer
63 views

how to linearize the full model for TSP quadratic formulation?

I tried to solve this problem but I failed, please how to linearized full model.
2
votes
1answer
253 views

If else condition to MILP

I have following problem: $c_i = 1$ if $X + \sum_j^N G_j = T$ else $c_i = 0$ Also there is another constraint which upper bounds equation $X + \sum_j^N G_j \le T$. $c_i$ is binary $X, T$ are ...
11
votes
2answers
1k views

Linear programming: objective function with “buckets”

I had a linear programming problem with the following objective function $$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$ Where $q, p, C, c$ are known. This problem was ...
2
votes
1answer
67 views

How to model these constraints correctly

$W$ is a vector of $N$ complex elements. $D$ is a binary variable The requirements are: when $D==1$, $L_{\min}\le ||W||_2^2\le L_{\max}$ and when $D==0$, $||W||_2^2=0$ I have formulated the following ...
1
vote
0answers
81 views

Linearization of constraints with square root [closed]

I am trying to solve an optimization programming model involving a non-linear constraint with a square root. It follows (in a simplified form): $X_i\ge\sqrt{A_i/B_i}$ where $X_i,A_i,B_i$ are positive ...
4
votes
1answer
90 views

How to linearize $f(x,y) = (ax+by)/(x+y)$?

I have a problem which is mainly linear but it has a non-linear component. The objective function is obj = Linear_term + $c*f(x,y)$ where, $f(x,y) = (G_1 x_1 + G_2 x_2)/(x_1 + x_2)$. The decision ...
4
votes
1answer
140 views

How/when can we use MINLP engines instead of linearizing MP models?

Nowadays, mathematical programming solvers have been frequently used to solve lots of practical/academic problems. Many of these might be interpreted as a MIP or MINLP to represent a specific problem (...
6
votes
1answer
190 views

Linearizing a program with multinomial logit in the objective

I have a nonlinear problem as follows: \begin{align}\min&\quad\sum_{k=1}^{K}\left|y_k - \sum_{i=1}^{N} \frac{e^{x_{k}^{i}}}{\sum_{j=1}^{K} e^{x^{i}_{j}}}\right|\\\text{s.t.}&\quad x^i_{j} \ge ...
2
votes
1answer
142 views

Linearize sum of continuous and boolean variable

For maximizing the objective function $\sum_i{d_i y_i}+ A x - B \cdot \mathbb{I}_{x>0}$, how can I linearize $ A x - B \cdot \mathbb{I}_{x>0}$ term where $d_i, A$ and $B$ are positive constants ...
1
vote
2answers
163 views

Switching of decision variables to be larger than or equal to a decision variable according to an indicator variable value

I would like to seek some advice on modeling the following: I have two integer decisions variables, $x, x'$, that are either equal or greater than zero and either of them is greater than or equal to a ...
3
votes
3answers
221 views

How to linearize the Min function while letting the binary variable to be fixed for x1==x2 as well?

As discussed here, the min function, i.e $X = \min\{x_1,x_2\}$, can be linearized as follows: \begin{align} X & \le x_1 \\ X & \le x_2 \\ X & \ge x_1 - ...
1
vote
3answers
256 views

How can I linearize this IF-THEN constraint?

Let $P_{t,u}; t=1,2,\ldots,T, u=1,2,\ldots,U$ be known values $\alpha$ is also a known parameter $X_{t,u}$ an optimization variable I have the following constraint: IF $P_{t,u}\geq\alpha$, THEN $X_{...
4
votes
1answer
96 views

Formulating these logical constraint in an ILP

I have these two constraints : $z \leq My$ $t \leq M'y $ where $z$ and $t$ are two integer variables $ z, t\geq 0$, $y$ is a binary variable, and $M$, $M'$ are two big numbers. So basically these ...
13
votes
2answers
98 views

Sensible and realistic way to model truck based transport costs depending on amount

Different kinds of problems involve transporting an amount $x$ from A to B which results in a cost $c(x)$ in the objective function. Traditionally, often linearized costs are used to get an easy, ...
7
votes
1answer
157 views

Strong MIP formulations for a large-scale mixed-integer nonlinear feasibility problem

I'm trying to construct a strong MIP formulation for the following integer nonlinear feasibility problem. Informally: We have a $m \times n$ decision matrix of binary variables Each row of the matrix ...
3
votes
1answer
123 views

Logical constraint in ILP

I want to write the following constraint: Let $z$ be an integer variable such that $0\le z\le M$, and $t$ be a binary variable where $M$ denotes big-M. The logical constraint is as follows: if $z \...
3
votes
1answer
148 views

How to express this logical constraint for an ILP?

I am trying to write an ILP for a problem but I have this logical constraint and I'm stuck. In my model I have: two binary variables: $x$ and $y$ One Integer variable: $z$ The logical constraint I am ...
10
votes
6answers
2k views

Nonlinear integer (0/1) programming solver

I have the following optimisation problem.\begin{align}\max&\quad\sum_i\sum_j\sum_k x_{ji}y_{kj} \operatorname{cost}(i,k)\\\text{s.t.}&\quad\sum_j x_{ji}=1\quad\forall i\\&\quad\sum_k y_{...
3
votes
1answer
63 views

Linearizing separable functions: SOS2 sets or binary variables

When linearizing a separable nonlinear function is there an advantage/disadvantage in using SOS2 sets in comparison to using binary variables?
5
votes
1answer
105 views

Minimize binary variable's distance with respect to the index values

For a given binary decision variable $x[i,j,k]$ my goal is to get as dense results in terms of k for successive values of j. Distance of k value to be kept as close as possible throughout j values: $d ...
5
votes
2answers
293 views

How to model If $A \le B$ then $Y = 1$, otherwise $Y = 0$

Somehow I don't get it right. I would like to model the following conditional: If $A\le B$ then $Y=1$ otherwise $Y=0$ where $A, B$ are reals and $Y$ is binary. I can model as follows: $Y \cdot A \le B$...
8
votes
2answers
375 views

knapsack problem with non-linear constraint

I have a basic knapsack problem where I need to fit the most weight possible in a bin: ...
5
votes
2answers
176 views

How to linearize a quadratic constraint to add it then via a callback function

Suppose we have a positive continuous variables $0 \le x \le UB$ where $UB$ is a known upper bound. How can we linearize the term $x^2$? Detailled problem: Suppose that via a callback we compute a ...
5
votes
1answer
147 views

Linearizing a constraint with square root of a variable

I am trying to linearize the constraint set (2) in the following simplified program. The parameters: $A,C,D,T\in\mathbb{R}^+$. The set $\mathcal{J}$ is polynomially-sized. \begin{alignat}2\min &\...
3
votes
1answer
101 views

Linearizing power term in objective function

I would like to linearize $x^2$ term in my objective function. I understand this can be solved using quadratic programming solver; however, for my use case linearization is necessary to convert it to ...
2
votes
1answer
113 views

Linearize sum of product in objective function

Notation: I have an optimisation problem with objective function: \begin{align}\max&\quad\sum_n Q_n\\\text{s.t.}&\quad Q_n=x_{ij}^{nk}(y_i^{nk}-c_n), \forall n \in N, k \in K, (i,j) \in P.\end{...
12
votes
4answers
768 views

Single reference for Mixed Integer Programming formulations to linearize, handle logical constraints and disjunctive constraints, do Big M, etc?

Is there a single crisp and accessible reference which covers how to generate Mixed Integer Programming formulations to linearize products, handle logical constraints and disjunctive constraints, do ...