# Questions tagged [linearization]

For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.

152 questions
Filter by
Sorted by
Tagged with
139 views

217 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{... 60 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,...
86 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 ...
145 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 ...
232 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 ...
194 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 ...
199 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 ...
348 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 ...
310 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 ...
373 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$?
86 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\}$ ...
108 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,&\...
231 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 ...
307 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 ...
110 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 ...
68 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?
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 1 answer 145 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 2 answers 452 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 2 answers 363 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 2 answers 135 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 2 answers 331 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 1 answer 337 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 1 answer 373 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 0 answers 65 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 1 answer 170 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 1 answer 337 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 2 answers 246 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 2 answers 225 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 1 answer 178 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_{...
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 ...