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
151 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 ...
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 ...
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 ...
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 - ...
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
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 ...
13
votes
2answers
95 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, ...
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 ...
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$...
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{...
12
votes
4answers
687 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 ...
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 \ \& \ ...
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 ...
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: ...
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 ...
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
259 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 ...
26
votes
1answer
2k 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$?
15
votes
1answer
1k views

How to formulate (linearize) a maximum function in a constraint?

How to formulate (linearize) a maximum function in a constraint? Suppose $C = \max \{c_1, c_2\}$, where both $c_1$ and $c_2$ are variables. If the objective function is minimizing $C$, then it can be ...
29
votes
2answers
3k views

How to linearize the product of two binary variables?

Suppose we have two binary variables $x$ and $y$. How can we linearize the product $xy$?
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
309 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 ...
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
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\...