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
5 votes
2 answers
540 views

Transform nonlinear cost function to get LP or MILP

I'm trying to schedule power of multiple prosumers in a microgrid. The problem includes a cost function with min and max ...
0 votes
1 answer
60 views

Converting a piecewise function to linear equations

I am trying to build a MILP model. In this model, I have a dependent variable (alpha) that its value depends on the value of some other variables (or different combination of some other variables). In ...
-1 votes
1 answer
56 views

How to linearize a product of an integer and a binary variable

i have this constraint right here, which is not linear. How would i linearize such a product. $number_t$ is a positive integer and $new_t$ and $reset_t$ are binary. $$number_t = (number_{t-1}+new_t)\...
1 vote
1 answer
96 views

Convex approximation of a constraint

I have a constraint given as $ \left|x_n+\beta x_{n+ 1}\right|-\varepsilon_{ky}\left|x_{n}\right|\leq0\hspace{1em}\forall n=1,2...,N $ I need to convert this into a convex form to implement in CVX. $...
0 votes
1 answer
58 views

Formulation of a stepwise linear approximation

I am currently trying to solve an MILP in Gurobi. Unfortunately, Gurobi does not support non-linear functions and I would like to do the following. I currently have the following constraint. It ...
3 votes
2 answers
213 views

Convex equivalent of a constraint

I have a constraint as follows in my MILP model: $$ \sum_{e} (a_1(e) - a_2(e))^2 \leq M $$ Where, $a_1(e)$ and $a_2(e)$ are binary variables. Would you please guide me how can I find the equivalent ...
0 votes
1 answer
84 views

How to represent "if $y_{it} = 1$ and $z_{jt'}=1$ then $x_{ij,t+t'}=1$"

There is a fulfillment problem in the e-commerce logistics field, where the fulfillment of each order is composed of a main transport (from City A to City B, referred to as a route) and an end ...
0 votes
0 answers
51 views

Better formulation of bilinear terms

I am working on an optimization problem where I need to formulate a constraint that represents the total sales value under specific conditions. The challenge lies in creating an expression that ...
2 votes
1 answer
247 views

Replace the constraint using ==> by a linear formulation

I would like to know how to express the continuity constraint without using a decision variable in the conditional form. My challenge is to stay with a linear formulation. I will start to explain my ...
1 vote
1 answer
119 views

How do I linearize such a constraint?

I was wondering, how one would linearize such a constraint, to make it applicable to LPs. $ a_{i}=(a_{i-1}+b_{i})(1-c_{i})-d_{i}$ $a_i$ gives information of the number of assigned jobs to machine $i$. ...
1 vote
2 answers
207 views

Nonlinear fractional objective function

Could you please teach me when an optimization model with fractional terms in the objective function can be linearized or solved optimally? I only know that if the objective function has a single ...
2 votes
1 answer
93 views

How to transfer an objective with separate positive and negative parts into linear programming

I've got to deal with an optimization problem as follows, $$ \begin{aligned} \max_{x,y} & a^Tx+y^TKx\\ {s.t.}&Ax=b\\ &{Cx}\leq d\\ l&\leq y\leq u\end{aligned} $$ where $x \in \bf{R}^n$,...
0 votes
1 answer
106 views

Interpret the formulation of a pricing model in crowdshipping

I am trying to run the pricing model from the paper "Designing pricing and compensation schemes by integrating matching and routing models for crowd-shipping systems" on python with Gurobi, ...
4 votes
1 answer
318 views

Optimization problem with the Harmonic number

I have an optimization problem: \begin{align*} \text{ minimize } \sum_{i=1}^n H(x_i) \\ \text{ subject to } Ax \geq b, x\geq 0, x\in \mathbb{Z}^n \end{align*} where $H(n)$ is the $n$-th Harmonic ...
1 vote
0 answers
31 views

Moment based linearization of PDF for LP based optimization

Suppose I’m interested in modeling risk/volatility using the Cauchy distribution and I’d like to optimize some allocations using linear programming. The Cauchy distribution is quadratic in nature but ...
1 vote
0 answers
56 views

transform minimize weighted sum of absolute value into a linear optimization

For example, we have an optimization problem $$ \min \sum_{i=1}^{n} |w_{i} - a_{i}| b_{i} \quad \text{s.t.} \quad \sum_{i=1}^{n} c_i w_i = 0 $$ and $a_i, b_i, c_i$ are given. How to convert it into a ...
1 vote
0 answers
49 views

How to linearize a product and ratio of $x$ and $y$ where $x$ is binary and $y$ is a continuous variable?

I am an electrical engineer who is currently learning about optimization. From this post, they have shown how to linearize the product of two binary variables. But in my case, I have a product $x \...
0 votes
1 answer
149 views

Production scheduling

I'm formulating a scheduling problem with the following decision variables: $$X_t \space \text{is power sold to market in time period t} \\ Y_t \space \text{is power used for production in time period ...
2 votes
2 answers
89 views

How to linearize the product of a binary and a negative continuous variable?

Suppose we have a binary variable $x$ and a negative continuous variable $y$. How can we linearize the product $u=xy$?
1 vote
1 answer
118 views

How to linearize the following constraints

Given the following two expressions: $ x - \frac{1}{T}\sum_{i} y_{i}$ $ x - \frac{1}{Q}\sum_{i} \beta_{i} y_{i}$ where $x \in \mathbb{Z}_{+}$, $y \in \mathbb{R}_{+}$, and $T$, $Q$ and $\beta_{i}$ ...
3 votes
0 answers
118 views

From Quadratic to MILP?

I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP: (QP) $\min c^T x + x^T Q ...
2 votes
1 answer
62 views

how to linearize if-then when having an operand?

if $x_{i,j,p,s}$ and $y_{i,j,p,s}$ are binary and $z_i^s$ is integer; how to enforce: $$ ((x_{i,j,p,s}=1) \land (z_i^s \ge 5 )) \implies y_{i,j,p,s}=1 $$ The value of $z$ in my problem could be 1 to ...
1 vote
2 answers
154 views

Matrix lookup modelling variants

As part of a bigger model I have a matrix of variables $x_{ij} \geq 0$ and a "selector" set of variables $y_j \in \{0,1\}, \sum_j y_j = 1$. From $x_{ij}$ I'd like to get the variables of ...
1 vote
0 answers
42 views

Handling Variable Division in CVXPY for Calculating Annualized Rate of Change

I am working with a dataset that contains multiple entries for different IDs across various years. Some IDs might have a gap of years between entries. My goal is to solve an optimization problem using ...
1 vote
1 answer
50 views

How to linearize stepped pricing in a route assignment problem

There is an allocation problem, while we have to assign logistics routes to multiple candidate carriers. For simplicity, let's assume there are only two routes, $A$ and $B$, with two candidate ...
1 vote
1 answer
431 views

Is it possible to do a linearization without introducing new variables?

I have three binary variables $x_{i,j}^{m,r}$ , $y_i^{m,r}$, and $z_i^{m,r}$. There is another integer variable $w_i^r$. And I want to linearize the following logic: $$ \sum_{m} x_{i,j}^{m,r} \ge 1 \...
0 votes
1 answer
98 views

applying a piecewise linearized equation in pulp

The background is I'm building a toy rent vs. buy mortgage calculator. I am an experienced software engineer but my math skills are 20 years behind me and I admit to being very lost. I've been using ...
1 vote
2 answers
175 views

Linearizing if else conditions in ILP

We are given three binary indicator variables $X_{ij}, Y_{jk}$ and $Z_{jl}$. Write linear constraints such that, a) if $X_{ij}$ is equal to 1, then for that $j$ when $X_{ij} = 1$, exactly one $Y_{jk} =...
0 votes
0 answers
90 views

Transforming a quadratic constraint into a linear constraint

I have a problem with a quadratic constraint and I want to transform it into a linear constraint. This would help to reduce the computational time of my problem. Following constraint should be ...
1 vote
0 answers
81 views

Linearization of Conditional Constraints for MIP using Cplex

I'm currently working on a mixed-integer programming (MIP) problem and I'm trying to implement a set of conditional constraints in CPlex. These constraints involve decision variables that are indexed ...
6 votes
1 answer
744 views

Network flow model - How can I turn this diagram into a matrix that when converted to RREF solves for max flow?

I have the following network flow model diagram and I have already calculated maximum flow using the R package igraph to be 28. However, what I would like to know ...
0 votes
0 answers
76 views

Optimize revenue function with log part

I am working on an optimization problem where I aim to maximize revenue. My current model has the following objective function: $$ Sales(P_i) * log(P_i - const_i))$$ where $P_i$ represents the price ...
4 votes
2 answers
377 views

How to model $C_1=C_2$ implies $b_1 = b_2$

Suppose $C_1 \ge 0$, $C_2 \ge 0$ are continuous variables and $b_1$, $b_2$ are binary variables. How could I model the following? $C_1 = C_2 \implies b_1 = b_2$, the opposite does not hold.
-1 votes
1 answer
68 views

How to linearize the multiplication of variables and transform this into an MILP?

Let $C=10$, $U=50$ $P_c,c=1,\cdots,C$ and $\alpha_{u,c},u=1,\cdots,U,c=1,\cdots,C$ are optimization variables $\alpha_{u,c}$ is binary $\sigma_{u,c}$, $d_{u,c}$ are known parameters $\min \sum_{c=1}^...
2 votes
1 answer
98 views

Representing a Multi-Level Categorical Variable using Big-M Method in Linear programming

I'm working with a statistical linear model where I have a variable, ( N ), representing the percentage of charging of a battery. Based on ( N ), I derive another variable, ...
2 votes
1 answer
92 views

How to linearize the multiplication by a binary decision variable?

I am currently optimizing a hydrogen production chain. I am optimizing the production regime, and the size of the required wind, solar and the electrolyser. For every hour of the year, the production ...
4 votes
1 answer
173 views

Non-Linear objective function due to piecewise component

I have the following objective function: $\sum_{n}(1-prob_{n})(1+x_n)$ Where $x$ is my decision variable. $prob_{n}$ is a piecewise function that can look like: $prob_{n} = $ \begin{cases} 0.5, ...
4 votes
3 answers
326 views

Systematic references on linearizing conditional / logical expressions

On this site, one can usually finds questions like “How to transform my expression into linear form?” The expressions usually contain and, ...
2 votes
1 answer
88 views

How to show that minimizing the epsilon-insensitive loss is equivalent to a quadratic program with inequality constraints?

This question is about an optimization problem that arises in support vector regression (SVR). Suppose you have $N$ pairs $(\vec{x}_n, y_n)$ as data and would like to find a vector of weights $\vec w \...
3 votes
1 answer
104 views

using milp for a linear complementarity problem

I have to minimize $c^Tx$ subject to $Ax = b$, $x_iw_i = 0$ for all $i$, with $x$ non negative continuous and $w$ binary. What model should I use to solve this problem?
1 vote
3 answers
121 views

How to linearize a chain of if-then constraints?

How can I express the process of converting a series of if-then constraints into a linear form? Let's assume that we have integer variable $x_i$, non-negative variables $y_i^d$, and binary variables $\...
0 votes
0 answers
45 views

How to linearize such a constraint?

My original content was like this: Assuming that server $k$ can only allocate corresponding computing functions to MU $i$ after receiving their tasks. Let $$ y_{i,k,t} = \begin{cases} 1 & \text{if ...
1 vote
1 answer
48 views

$\min\{f(x_1),\dots,f(x_n)\}$ with other constraints

I have an optimization problem which goes: \begin{align*} \text{Minimize:} \\ & \sqrt{x} + \sqrt{y} \tag{NL-objective} \\ \text{Subject to:} \\ &3x + 2y \geq 2 &...
3 votes
2 answers
388 views

How to model a binary variable?

I am trying to find a constraint for the following relationship, but am failing a bit at it right now. I want to find a linear constraint that does the following. The binary variable $switch_{ot}$ is ...
5 votes
4 answers
877 views

Rewriting if-then constraints of binary summations

Suppose both $x_{i,j}^{ab}$ and $y_{i,j}^a$ are binaries. Then how can I rewrite the following if-then in linear form? $\sum_b x_{i,j}^{ab} \ge 1 \implies \sum_{i,j} y_{i,j}^a = 0$ I was thinking of ...
0 votes
0 answers
68 views

Resource selection problem with non-linear objective function

I have an optimisation problem to solve but I can't model it correctly. Any insight is welcome :) It has been a few years since my optimisation classes in university, and while I have forgotten a lot ...
3 votes
2 answers
695 views

Writing a constraint of an integer programming in a linear form

I modeled an optimization problem in an integer programming format. The main constraint I came up with is now nonconvex. I would like to see if there is another equivalent formulation in which the ...
3 votes
3 answers
253 views

Quantifying a measure of standard deviation in MILP

I am trying to set up a MILP for production scheduling. The specific details I'm not sure are important but in general a plant has M machines running N parts, each part requiring W workers. The model ...
2 votes
3 answers
192 views

Linearization the product of three variables (two binary & one continuous)

Consider the following binary variable $x \in \{0,1\}$ and two continuous real variables $y,p \in \mathbb{R}$. I am trying to model the following conditional equations as constraints: \begin{cases} ...
3 votes
3 answers
258 views

Equivalence between constraints in ILP

Let's have binary variables $x$ and $y$. I'd like to define a helping binary variable $z$ such that $$ z = 1 \; \;\; \mathrm{iff} \; \; \; x + y = 2.$$ If I wanted to express the equivalence between ...

1
2 3 4 5