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
9
votes
1answer
247 views

How to linearize membership in a finite set

Given finite set $S$ and variable $x$, how do I linearize the set membership constraint $x\in S$?
5
votes
1answer
276 views

Model “if and only if” indicator constraints in Linear programming

Apologies if this question has been asked, but I haven't been able to find it. I'm modelling something with Gurobi and want to do the following: \begin{align}\text{cond} < \dfrac{1}{3} &\iff x =...
3
votes
0answers
56 views

Linearization of a quadratic model, what is the difference while using gurobi?

I have a quadratic model of parking $N$ cars in $S$ separate lanes as follows. Each car has an arrival time and a departure time. Departure follow the last in first out principle. The objective is to ...
4
votes
1answer
110 views

Problems modeling a constraint in network design problem

I'm working on a network design problem where the objective is to minimise the network design cost. Given a graph G = (V, E) and a set of point-to-point demands K, the task is to route the demands and ...
5
votes
1answer
240 views

What is a good way to penalise LP relaxation?

I have a binary integer program. It is of a large size and the solver is taking longer time. I am thinking of relaxing the binary integer variable and making it a continuous variable. How can I ...
6
votes
2answers
233 views

Forbid transformation of max(x,y) into MILP

The function $\max(x,y)$ can be linearized by making use of additional binary variables. I suppose global optimisers are implemented to perform this transformation automatically. Is there a global ...
2
votes
2answers
166 views

Linearize a product of binary variables

I have a function to minimize which has the following term $$\sum_{i\in I}\sum_{j\in J}\sum_{k\in K}x_{ijk}N_{ij}a_{ijk},$$ where the variables are $x_{ijk}\in\{0,1\}$, $a_{ijk}$ are given as input ...
2
votes
1answer
163 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
65 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 ...
3
votes
1answer
95 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, ...
6
votes
1answer
157 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 ...
3
votes
1answer
59 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
137 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
129 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 ...
3
votes
1answer
165 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
3answers
122 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. ...
6
votes
2answers
242 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
1answer
197 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
74 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 ...
2
votes
1answer
124 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$. $$ \...
3
votes
1answer
101 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:...
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 ...
1
vote
1answer
101 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}}\...
1
vote
1answer
90 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:\...
4
votes
1answer
92 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\\&...
6
votes
2answers
639 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 ...
-2
votes
1answer
69 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
264 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 ...
2
votes
1answer
68 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
83 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 ...
3
votes
1answer
250 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}-...
4
votes
1answer
95 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
141 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
196 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 ...
7
votes
1answer
114 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 ...
1
vote
2answers
176 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 ...
1
vote
3answers
267 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_{...
3
votes
3answers
227 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 - ...
4
votes
1answer
98 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 ...
2
votes
1answer
147 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 ...
7
votes
1answer
162 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
126 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
153 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
71 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
106 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 ...
8
votes
2answers
389 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
192 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
167 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
123 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 ...