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
1answer
149 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
74 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
124 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
156 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 ...
5
votes
1answer
58 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
151 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
213 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
3answers
200 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
89 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
117 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 ...
6
votes
1answer
146 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
104 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
123 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
52 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
97 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
334 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
150 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
114 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 &\...
1
vote
0answers
47 views

linearisation of if-then constraint [duplicate]

Is it possible to translate this if-then constraint in linear manner to be solved with a linear programming solver? If not, how can it be translated into a integer programming manner to be solved by ...
3
votes
1answer
83 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
95 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{...
3
votes
0answers
72 views

Linearization of the shifted copy of a function

Suppose in a model I have the expression $y_{1}(x) = 10 + 5 x^2$ where $x \in [0,20]$ is a continuous variable. In order to be able to use an MILP solver, I piecewise linearise $z_{1} = x^2$, by ...
6
votes
1answer
147 views

Convert summation of min functions into linear constraints for optimization

I have the following optimization problem: $$ \mbox{maximize } j^{*} \mbox{ subject to:} \sum_{j^{*}\leq j\leq J} \min({\bf A}_j,{\bf B}_j) \geq \lambda, \lambda \in \mathbb{R} \mbox{ and } {\bf A}_j,{...
1
vote
0answers
41 views

Linearize max function in a constraint [duplicate]

I have a constraint as follows: $ \sum_i {r_i} \geq \max \{g_j, B_j\} $ where, $r_i$, $g_j$ are variables and $B_j$ is a parameter. How do I linearize the constraint (I suppose using big-M method)?...
3
votes
0answers
46 views

Linearisation using SOS2

I am trying to linearise the following expresssion. $C(k) = B(k) e^{-d(k)}, B(k) \ge 0 , d(k) \ge 0 $ I am trying to do this by using SOS2 sets. I set $X(k) = e^{-d(k)}$ and I get $C(k) = B(k) X(...
3
votes
1answer
140 views

How to fomulate the following conditional constraint in MILP?

How can I formulate the following conditional constraint to a linear constraint using indicator variables? Please note that all variables are continuous and $c \ge 0$ $\text{1: if} \ c=0 \ \& \ ...
5
votes
1answer
91 views

Linearize a product of an integer variable (not just binary) and a continuous variable?

I have a constraint in my formulation that contains multiplication of an integer variable $y$ and a continuous variable $x$, which is $xy=q$ where $y$ is the number of units in which $q$ gets equally ...
5
votes
3answers
200 views

Problem with binary decision variable constraints in VRP

I would like to create non-linear violation costs in my VRP. I already created my whole VRP with time windows in which I have these decision variable: ...
2
votes
1answer
65 views

Inequality Constraint Linearization of a product of an integer and a binary variable

I have thought I had found the answer here: How to linearize the multiplication of an integer and a binary integer variable? But the answers to that questions didn't help me find a solution for my ...
3
votes
1answer
74 views

How to linearize a weighted maximum coverage problem?

Is it possible that the binary variables below be modeled as continuous variables? \begin{alignat}2\max&\quad\sum _{{e\in E}}w(e_{j})\cdot y_{j}\\\text{s.t.}&\quad\sum {x_{i}}\leq k,\quad&...
5
votes
2answers
119 views

Minimizing $x_1/x_2$ over a simplex in the positive orthant

I need to solve the following problem \begin{align}\min&\quad x_1/x_2\\\text{s.t.}&\quad Ax \leq b\\&\quad x > 0\end{align} where $A$ is a positive matrix. The best thing I can think ...
3
votes
2answers
258 views

Mocking up conditional statements in LP

I would like to know how if condition statements in linear programming can be reformulated using indicator constraints, and hence solved as a mixed integer linear program. Specifically: 1. Is it ...
5
votes
2answers
155 views

Linearizing objective function with variables inside an indicator function

I am working on a problem in which I am trying to maximize the average of a variable only for the data that meet a certain condition with a constraint on the number of data that meet this condition. I ...
4
votes
1answer
207 views

Transforming a Quadratic constraint to SOCP

I have a problem similar to Markowitz portfolio optimization that I would like to transform into second-order cone programming. I have a linear objective function with a quadratic constraint (assuming ...
8
votes
1answer
308 views

if-else condition for the objective variable using big M notation

Let $0\leq \beta\leq 1$ be an objective variable. The size of $\beta$ is $N\!\times\!N$. Now, how can I impose the following? if $\beta_{i,j}>0$ then $\beta_{j,i}=0$ Big M notation can be ...
5
votes
1answer
516 views

How can I deal with a possibly undefined constraint?

I have a minimization problem minimizing $d_k \geq 0$ and some other variables with all strictly positive coefficients. I leave my objective function below to better convey my goal. $$\min_{\mathbf{d}...
6
votes
1answer
123 views

Linearizing the square root of binary summations

My question is similar to this one and almost identical with this. I am so confused due to indexing and could not make sure if I could apply the solution in here to this indexed version as shown below....
6
votes
1answer
58 views

Linearizing the square root of two binary summations

My question is similar to this one though a bit more complicated. Though my question also includes indices, I am removing them to ease readability. Let binary variables $x,y\in\{0,1\}$, non-negative ...
11
votes
2answers
998 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 ...
3
votes
1answer
42 views

defining Mixed integer linear inequalities for a set of variables

The problem is described as follows: considering $n$ variables which are continuous and bounded such that $$L_i \le x_i \le U_i\quad \forall i=1,2,\dots,n.$$ How can i define a set of mixed integer ...
5
votes
2answers
263 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$...
5
votes
2answers
197 views

Trade off between number of constraints and bounds of a variable

I am not familiar with the inner working of the solvers. I mostly use the python pulp or IBM CPLEX solver. For fast execution ...
3
votes
1answer
109 views

Linearizing constraint with continuous and boolean variables

I have two continuous variables $A$, $B$ and two binary variables $x$, $y$. Condition: if $A = B \wedge x = 1 \wedge y=1$ then $z = 1$ else $z = 0$ from In an integer program, how I can force a ...
5
votes
1answer
61 views

How to formulate case distinctions in AMPLs objective function?

This is my first real optimisation problem I formulated and now trying to solve by using AMPL. The following objective function is from a linear 0-1 LP means all variables $x_i^b\in\{0,1\}$, with $i\...
3
votes
0answers
36 views

Extract binary value from continuous variable [duplicate]

I have a continuous variable $c$ which has value in between $[-R, +R]$. I want to create a boolean variable $x$ and, $x = 1$ when $c = 1.0$ otherwise $x = 0$ In more general form: $x = 1$ when $c \...
1
vote
0answers
64 views

Converting Nonlinear Program into an LP

I have a problem with a nonlinear objective function which is \begin{align}\min&\quad Z_j\cdot(N_j)^{0.5}\end{align} where $j$ is the index. I want to know how can I turn it into a linear ...
6
votes
1answer
147 views

How to propagate time using linear inequalities?

I have an adjacency matrix $G_{i,j}$ that tells the distance between $i$ to $j$ (between 0 to 1) if there is no edge between $i$ to $j$ I am putting a large integer $100$. This is my previous ...
6
votes
1answer
74 views

Linearizing objective function with absolute differences

I want to turn this objective function $$\max \sum_{i=1}^{N-1} \sum_{j=i+1}^N |TX_i^T - TX_j^T|$$ where $T$ is just a vector with increasing integers (e.g $[1 \ 2]$) and $X_i$ is a vector ...
11
votes
1answer
270 views

k-means/k-medoids Clustering Implementation in CPLEX Java

I am trying to model a grouping algorithm as k-means clustering problem, by referring to the general definition as mentioned in Wikipedia. In my system, I have $N$ nodes that I want to group in $m$ ...