Questions tagged [linearization]
For questions related to techniques for converting nonlinear expressions in optimization models into equivalent (or approximately equivalent) linear ones.
295 questions
5
votes
2
answers
151
views
Are McCormick envelopes the best convex relaxation for bilinear terms?
I am working on convex optimization problems in network engineering that involve bilinear terms of the form $xy$. According to this resource, McCormick envelopes provide a convex relaxation for such ...
0
votes
0
answers
38
views
How to quantify the error introduced by linearizing a bilinear term in an optimization model?
I’m working on an optimization problem that includes bilinear terms in the constraints. To make the problem solvable by a MILP solver, I’ve linearized these terms using McCormick envelopes.
I’d like ...
- 114
1
vote
1
answer
51
views
Percent change soft constraints in linear programming
In a linear program need to constrain the percent change between two decision variables, $a,b$ where the percent change formula, relative to $b$ is $\frac{a-b}{b}$.
I'm not sure that any arbitrary ...
- 521
1
vote
1
answer
82
views
Linearly approximate a non-concave sigmoidal function
I have the following problem. I have various non-linear functions in my mathematical model that I would like to approximate. Specifically, I have an exponential function and a sigmoidal function.
$$e_{...
- 71
0
votes
1
answer
81
views
Continuous learning curves in scheduling MILP
I have the following problem. I am currently working on a scheduling problem in which I would like to incorporate learning effects. Specifically, this concerns the efficiency of human resources, which ...
- 71
0
votes
2
answers
133
views
How to linearize min/max function of a large number of values as a constraint?
Assuming I have 100 variables $r_1 \dots r_{100}$ which can be positive or negative and I try to find the minimum of all of them in a MILP problem and bind that to a variable $y$.
$$y = \min_{i \in \{...
- 4,307
0
votes
1
answer
134
views
Optimizing for multiple inventories
I have $M$ warehouses $w_1, w_2, ..., w_m$ each with inventory on $N$ items. For example $w_1$ may have 3 of item_0, 2 of item_1, $k$ of item_n.
How does one formulate each of the following objective ...
- 1
1
vote
1
answer
96
views
Activating a fixed cost using a binary variable when the max of 3 affine function is 0 (MILP)
I'm trying to model the scheduling of operations over a set of production assets considering uncertainty, individual costs and time dependent fixed operation costs ($c_f(t)$). Without exposing all the ...
- 11
0
votes
0
answers
43
views
Computational tool to polyhedra from binary vertices with no extra integer solutions creating extra integer or real dimension if necessary
All logical operations acting can be expressed as IP constraints. But it's not obvious that just because one can build everything out of existing logical constraint and other linear constraints that ...
- 4,307
1
vote
0
answers
70
views
Enforcing proportionality in MILP
I am trying to enforce $x\in\mathbb{R}^n$ is proportional to $y\in\mathbb{R}^n$ using MILP. Is this possible?
- 21
1
vote
0
answers
116
views
Big-M stability or Formulation Problem?
I linearized this objective function where $w$ is an exogenous non-negative continuous var and $x$ is a binary decision variable. I end up using the big-M method multiple times and for smaller ...
- 79
2
votes
1
answer
144
views
How to linearize a disjunction form without using additional binary variables?
I am trying to linearize the following logical expression without using any auxiliary binary variables, and I am interested in knowing if there is a way to do that.
$$ (x = y) \implies (b = 1) $$
...
- 10k
0
votes
1
answer
95
views
Integration of non-linear learning curves into MILPs
After some ambiguities in my post yesterday, I try to clear some things up. I have a MILP scheduling model in which I want to incorporate learning effects. I have a variable $z_{ijk}$ that indicates ...
- 19
2
votes
1
answer
213
views
Linear Penalty Term for Deviation From Average Value
I'm building a Pyomo assignment model for speakers at a conference. P speakers (each speaking only once at the conference), R rooms, T timeslots; with some constraints on speaker availability, some ...
- 817
2
votes
0
answers
109
views
Avoiding epsilon when linearizing $y \leq b \implies x = 1$
I understand that the standard answer to this is to model $x = 0 \implies y - \varepsilon \geq b$. To avoid numerical issues (I'm using this for computing reduced costs), I would like to have a ...
- 1,317