Skip to main content

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
0 votes
1 answer
46 views

Linearization of two constraints: one with a conditional max and one with a sum with a variable as index

I have these two quite nasty constraints I have tried to linearize. I am trying to dynamically control if you are allowed to plan producing product p. You are allowed to do it if the product arrived (...
0 votes
0 answers
33 views

What's the linearization of the product between a discrete variable and a continuous varibale?

I am trying to linearize the product $z=xy$, where $x$ is an integer variable and $y$ a continuous variable, both non-negative, for an optimization problem. I have tried the SCIP formulation: $v_{bn} \...
1 vote
0 answers
74 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
185 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 ...
0 votes
1 answer
74 views

How to write conditional constraints and sum the result in Linear Programming in Python?

I want to use the sum of a series of linear expressions as objective and constraints. These linear expressions are chosen to be included or not based on some conditions. I can achieve it in Excel ...
0 votes
1 answer
76 views

PULP: Optimization Assignment of Bicycle production per month

Q1. If bicycles of types A and H are produced, then bicycles of type C can be produced with 20% shorter working hours, while selling profit of bicycles type H can be 20% higher. Q2: If bicycles of ...
2 votes
2 answers
183 views

Are McCormick Envelopes exact for the following class of optimization problems?

I have the following optimization problem: \begin{align*} \text{minimize} \quad &\mathbf{c^T x} \\ \text{such that} \quad &\mathbf{x} \in S. \end{align*} Here, $S$ is a polyhedron of the form $...
1 vote
3 answers
116 views

If $x_1 \geq 4$ then **one** out of the following three constraints must hold: $x_2 \leq 3, x_3 \leq 4, x_4=5$

How does one linearize the following constraints: If $x_1 \geq 4$ then one out of the following three constraints must hold: $x_2 \leq 3, x_3 \leq 4, x_4=5$. $$x_1 \leq 4 + Mz_1$$ $$x_2 \leq 3 + M(1-...
3 votes
1 answer
199 views

How to linearize the following logical constraints?

I am having trouble linearizing the following logical constraints. $x,y,z$ are non negative continuous variables such that $x=y+z$, and $A$ is a positive parameter. I would like to linearize $$ y= \...
2 votes
1 answer
78 views

Minimizing sum(abs(Ax-c)) for binary decision variables - terminology and methods?

My problem requires choosing a fixed number of vectors from a large set of vectors such that the sum of these vectors is close to some known target vector. That is, given known parameters: $$ l, m, n \...
2 votes
1 answer
223 views

Set a limit on value change of a binary variable

I am working on an Energy Management problem. The objective is to minimize the electricity bill for the customer. I have a time-series data with 15 min. intervals spanning the course of 1 year. The ...
2 votes
1 answer
139 views

Priority based demand fulfilment in Linear Constraint

Say I have 3 sources. D1, D2, D3. their capacity is 100, 200, 400. I want to create some constraints such that First D1 is depleted then D2 and then D3. But the catch is you cant use min or max ...
0 votes
1 answer
105 views

How to model this constraint in a better way?

I have a resource allocation problem. There are $M$ users and $N$ resources (machines). One user can be assigned to multiple resources/machines. But maximum $B$ machines can be activated at a time for ...
2 votes
1 answer
126 views

How to model the constraints of min and max in cvxpy

I have a continuous variable $x_{ij}\in[0,1]$ and I need to write the following constraint: $$M_i-m_i+1\leq C_i$$ where $M_i=\max\{j: x_{ij}>0\}$ and $m_i=\min\{j: x_{ij}>0\}$
4 votes
2 answers
309 views

Linear condition between two continuous variables

There are two real variables $x$ and $y$. The conditions are such that: if $y\le 0$, then $x=0$ if $y>0$, then $x=y$ How to write linear equations or inequalities to satisfy both the conditions?
3 votes
1 answer
194 views

Reformulate constraints

I have the following constraints and am wondering whether I can formulate the whole thing more narrowly and with fewer constraints. $x_{itk}$ is binary and $u_{it}, v_{itk}\in [0,1]$. $M$ is a Big-M ...
2 votes
1 answer
84 views

Is the linearization with first-order Taylor approximation correct?

I have a QP problem as $\min \hspace{2mm} x^TQx-c^Tx$ here $x$ in binary I want to transform it into a MILP by writing the objective function as $\min \hspace{2mm} z-c^Tx$ and then adding a constraint ...
1 vote
1 answer
45 views

Converting a function composing of multipe pieces into a linear equation

I have a variable (alpha) which depends on some other binary variables, denoted as X_i. So, for some combination of other variables, alpha may take a value (Beta_j). I added some auxillary variables (...
1 vote
1 answer
88 views

How to model $\max\limits_{x\in X} \min\limits_{y\in Y} \max\limits_{z\in Z} f(z)$ as single MILP

I have the following optimization problem: \begin{align*} \max\limits_{x\in X} &\min\limits_{y\in Y} \max\limits_{z\in Z} & f(z) \\ &\text{such that} & (x, y, z)\in P \end{align*} ...
0 votes
1 answer
36 views

Add second "constraint" to model a binary variable

in my model I have the binary variable $f_{ij}$ which pushes a time-dependent $j$ integer variable $D_{ij}$ to zero if $f_{ij}$ takes the value 1 and keeps the integer number if $f_{ij}$ equals 0. Yes,...
0 votes
0 answers
64 views

Is it possible to transform MIQP into MILP without introducing new variable?

I have a QP optimization problem in the form $$\min {\bf x}^T{\bf Qx}-{\bf c}^T{\bf x}$$ here $\bf Q$ is a symmetric matrix. $\bf x$ is the optimization variable, and it is binary. Is there a way to ...
0 votes
2 answers
90 views

linearizing a constraint involving an absolute function

I would like to know what is the best way to linearize a constraint involving an absolute function. More precisely, imagine I have three binary variables and their relationships is as follows: |x-y| = ...
1 vote
1 answer
87 views

Linearizing a quadratic constraint

I am working on a quadratic conic optimization problem, but I have discovered that it would be preferable if the quadratic constraint is linearly approximated. In other words, I need some way to make ...
0 votes
2 answers
126 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 ...
15 votes
4 answers
2k 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 ...
2 votes
1 answer
138 views

Lifting a 3rd order polynomial into a higher dimensional space

An MINLP from a paper I am reading has the following expression in its constraints: $$ p_{l,s}=z_lb_l\Delta\theta_{l,s}+b_l\lambda_{l,s}u_l\Delta\theta_{l,s} $$ Where from left to right: $p_{l,s}$: ...
0 votes
1 answer
59 views

How to linearize this L0 norm of a vector?

I have an QP optimization problem. $\bf x$ is the binary optimizaion variable of size $12\times 1$. One of the constraints is non-linear/non-convex. The constraint is L0 constraint. The constraint I ...
2 votes
1 answer
215 views

How to transform a binary QP into an MILP?

I have a binary quadratic problem with objective ${\bf{x}}^T{\bf{Qx}}+{\bf{c}}^T{\bf{x}}$ subject to ${\bf{A}}{\bf{x}}\le{\bf{b}}$ ${\bf{A}}_{eq}{\bf{x}}={\bf{b}}_{eq}$. here ${\bf{x}}$ is binary. ...
0 votes
0 answers
116 views

why this little constraint changes my whole program?

I'm trying to linearize a CP in ILOG CPLEX. I have the following constraint that I want to linearize (I already simplified it with the big M) : ...
0 votes
0 answers
66 views

Why are these two constraint equations not equivalent?

I've made a CP Model of an hospital in ILOG CPLEX and I want to test the performance of the CPLEX version of it. In my CP model, I have the following constraint : ...
5 votes
2 answers
104 views

How to formulate case distinctions in AMPLs objective function?

This is my first real optimization 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\...
5 votes
2 answers
583 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 ...
-1 votes
1 answer
74 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
112 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
67 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
232 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
85 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
58 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
251 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
141 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
224 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
96 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
111 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
328 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
65 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 ...
2 votes
2 answers
96 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
125 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
124 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
64 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
2 3 4 5 6