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
2answers
188 views

Piece-wise linear approximation of a constraint

We have a decision variable $0<y<1$ and the following constraint $$z=\frac{y^2-y+1}{y(1-y)},\tag{1}$$ We also have another constraint $$y=f(x),\tag{2}$$ where $f(x)$ is a linear function of $x$. ...
4
votes
2answers
135 views

Linearizing $x^2/(1-x)$ by partitioning the interval $0<x\le X$

We have two decision variables \begin{align} & 0<x\le X,\\ & 0<y\le Y, \end{align} where both $X$ and $Y$ are two sensible upper bounds on our decision variables. We also have a ...
2
votes
1answer
140 views

Linearizing division of two variables

For all $i \in I,j\in J$ and $k\in K$, define variables $x_{ij}, z_{ijk}\in\{0,1\}$, $y_{ij}\geq 0$ and constants $c_j, e_{ijk}, d_j, f_j >0$. We have the following constraint $$\sum_{j\in J_1}c_j\...
4
votes
1answer
206 views

Can we simplify (perhaps linearize) this constraint?

We are dealing with a stochastic model and one of the constraints is \begin{align} y_j=\frac{\sum_{i \in I}\sum_{k \in K}\mathbb{E}\left[X_{ik}^2\right]x^k_{ij}}{\sum_{i \in I} \sum_{k \in K} \mathbb{...
2
votes
0answers
50 views

Function approximation of a complex objective function

I would like to approximate the following objective function using a simpler function that can use be defined in gurobi. \begin{equation} \min_{I_{i,v}} \ \sum^{N_v}_{v}\sum^{TT_v}_{i} \ C_{loss,...
2
votes
2answers
67 views

Change the objective function formula change the complexity of a linear program?

I have a linear program, where I can use it with the same constraint to minimize objective 1 or minimize objective 2. I noted that when I use the formula of objective 2 the problem can be solved with ...
4
votes
1answer
113 views

Can you calculate the mean of some MIP variables using linear constraints?

got a lingering question from a graduate course in integer programming that's been bugging me ever since. Is it possible to find the mean of some variables in a MIP without resorting to quadratic ...
4
votes
0answers
215 views

Linearize a highly non-linear objective function

[EDIT] : The formula below is updated to remove the radical, 0.5 in the term $(I_{i,v} \cdot \Delta t)$ and constant temperature $T$ replces temperature as function of current. [EDIT] :The values of ...
3
votes
1answer
186 views

Range limits on terms in the objective function of an LP

I have a linear maximization problem with an objective as follows: $$\sum c_i\cdot\text{exp}_i$$ where $c_i$ are constants (positive or negative) and $\text{exp}_i$ are linear expressions of the free ...
3
votes
1answer
172 views

If variable falls below a certain value, include difference to set value in objective

I think its easiest to describe my goal first and continue with my implementation and the resulting problems! My goal: Using Pyomo as interface and Gurobi as solver, if a variable $x_{i,t}$ falls ...
6
votes
1answer
331 views

Optimize for bonuses within a group (knapsack)

I am trying to create an LP problem which is like the knapsack problem but with groups of items. Let's say there are 10 groups of items each with up to 5 items. Each group has one special item and you ...
5
votes
1answer
306 views

How to optimize on a fixed-cost based on number of results?

I am trying to create an LP problem which is like the knapsack problem but where there is a fixed bonus/penalty based on the number of items chosen. There are 20 items to choose from with some weight ...
2
votes
1answer
171 views

How to linearize the product of two integer variables?

Given two integer variables $L_x \leq x \leq U_x$ and $L_y \leq y \leq U_y$, how can we linearize the product $x \cdot y$?
2
votes
1answer
76 views

Linearize product of $x\cdot y \text{ with } x,y \in \{-1,0,1\}$ for MILP

I have a problem where I have many products between variables drawn out of $\{-1,0,1\}$. Could you suggest a linearization in terms of variables in $\{-1,0,1\}$ or $B_1 - B_2$ where $B_i \in \{0,1\}$ ...
3
votes
1answer
89 views

Linearization of problem with affine linear functions

Problem: Write the following task as a linear program: $\min f(x),x\in[-2,5]$ where \begin{align}f(x) := \begin{cases} -2x+2,&\quad-2\le x<-1\\ -x+3,&\quad-1\le x < 1\\ 2,&\...
7
votes
2answers
222 views

Product of weighted binary variables equivalent to sum of weighted binary variables?

I'm working on an optimization problem with a non-linear objective function of the form $$\max\prod_{i=1}^{n}(1-a_{i}x_{i}).$$ The objective function represents the combined probability of success for ...
5
votes
1answer
298 views

If continuous variable < constant then same variable = 0

When I come across with a situation needs an if-then constraints I visit Larry's post. I am a bit confused with the titled constraint this time because I am not trying to set $y$ based on $x$ but ...
2
votes
1answer
86 views

Linearization of constraints in a ILP

I have been working on a Graph Theory problem for my thesis and got stuck about the linearization of some constraints. I am hiding everything, constraints, variables and so on, of my problem not ...
3
votes
1answer
62 views

How to know if a combinatorial optimization problem is linear or not?

I want to know if a combinatorial problem like the knapsack problem is linear or not. And how do we know if a given problem is convex or not?
4
votes
1answer
153 views

How to linearize a non-convex optimization objective function?

The non-convex multi-objective optimization problem in my case is defined below: Objective 1: Minimize $f_1(X_1,X_2)=C_0+C_1(1/X_1)+C_2(X_2/X_1)+C_3X_1+C_4X_2+C_5(X_2^2/X_1)$ Objective 2: Minimize $...
4
votes
1answer
131 views

Alternate formulation for modeling inventory constraints

I'm working on a inventory optimization problem where inventory used at a time-period is computed based on price-bucket that is selected for an item. Problem contains multiple items (around 10K), 15-...
3
votes
2answers
434 views

How to linearize a constraint with a maximum of a linear function

I want to linearize the following statement into a MILP: $\forall x\in \mathbb{R}^{m}$ satisfying $Cx \le d$, $\exists i\in \{1,\cdots,m\}$ such that $a_i^Tx \ge b_i$, where $a_i$ and $b_i$ are given ...
6
votes
2answers
360 views

How to model this expression?

Suppose $0\le x \le 1$ is a decision variable and $\gamma(x)$ is defined as follows: $$ \gamma(x)= \begin{cases} \theta & x>0\\ 0 & x=0 \end{cases} $$ where $0\le \theta\le 1$. In my model, ...
6
votes
2answers
131 views

Linearise $\max\{ y_{t-1} + a_t - z_t ,0\}$

I'm trying to linearise these constraints, but I am not able to do correctly do it. $$y_t = \max\{ y_{t-1} + a_t - z_t, 0 \} $$ My attempt was this: \begin{align}y'_t &\geq a_t - z_t\\y'_t &\...
5
votes
2answers
193 views

How to linearize specific range constraints?

I would like to know about the linearization of the $(If, Then)$ constraints as follows: $$\begin{array}{l} \text { If: } \\ 15 \leqslant x \leqslant 25 \\ \text { then: } \quad y=\color{blue}{a} x+\...
10
votes
1answer
284 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
308 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
62 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
166 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
288 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
242 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
199 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
173 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
85 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
104 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
169 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
114 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
247 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
152 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
192 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
194 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. ...
7
votes
2answers
355 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} ...
3
votes
1answer
215 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
108 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
144 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
157 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
113 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
238 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
99 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
100 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\\&...