Questions tagged [mixed-integer-programming]
A mixed-integer programming (MIP) problem is a linear program where some of the decision variables are constrained to take integer values.
337
questions
0
votes
2
answers
41
views
Conditional modelling of a binary variable based on the values of two continous variables
I want to model a binary variable $(b)$ from two continous variables $(x_{in},\:x_{out})$.
These variables are $ 0\leq x_{in} \leq x_{max},\: 0\leq x_{out} \leq x_{max})$. I want the following three ...
- 1
0
votes
1
answer
22
views
Excel Solver Linear Optimization : Formula Debugging
I am trying to get a optimization model to work correctly. The background is to use the solver to find a circuit (AC or DC) that would minimize cost. I am trying to use binary variables so the ...
- 1
0
votes
1
answer
22
views
How can I convert non-linear constraint to linear one?
Problem: Suppose I have $n$ finished products and each product has its own completion time, such as C$_i$ (C$_i$=completion time of product $i$, where $i=\{1,2,...,n\}$). These products will be ...
- 15
1
vote
1
answer
42
views
MIP- If then with either or
I need something like this
It may sound silly but I couldn't find a way to express this.
x,te,ts decision variables, x bool, te,ts >=0;
if $x[m,i]+x[m,j]-1 > 0$
then
either $te[i]+d-ts[j]<=0$ ...
- 13
1
vote
1
answer
15
views
Relationship between number of explored nodes and solution space for a MILP problem
I'm using CPLEX through AMPL to solve a problem using two equivalent formulations. The problem is being solved to global optimality. However, one of the formulations is faster than the other. I have ...
1
vote
1
answer
23
views
assymetric graph coloring formulation
I'm reading this articel which is about formulating VCP to eleminate symmetric solution, they say:
And then In order to eliminate some of the symmetrical solutions, they say these two constraint is ...
- 161
0
votes
0
answers
9
views
Suboptimality of QR decomposition based integer least squares
Given a real n-by-m matrix $A$ and a real vector $y$, the integer least squares problem is to find an integer-valued vector $x$ that minimizes $\left|Ax-y\right|_2^2$.
A typical solution when $A$ is ...
- 51
0
votes
1
answer
43
views
Formulate constraints to an Integer programming: How to algebraically formulate a geometric constraint that the colored grids must form a rectangle?
I am stuck in a constraint formulation of a discrete optimization problem. Consider a board of Cartesian grids (M rows by N columns). We are going to color some grids among them. There is a geometric ...
4
votes
1
answer
48
views
Linearize optimization problem with absolute value
Is there any method to linearize the following optimization problem?
\begin{align}
\min_{x,y} &~~ c~[x; y] \\
\text{s.t.} &~~ \sum x\leq \alpha_1 \\
&~~ \sum |y|\leq \alpha_2 \\
&~~ \...
- 316
1
vote
0
answers
26
views
How much running time does solving a Mixed Integer Linear Program need?
Given a mixed integer linear program with $m$ constraints and $n$ variables how much time do we need to solve this?
I know that MIPs like IPs are in general NP-hard. Nevertheless for IPs one can show ...
- 578
0
votes
1
answer
38
views
Alternate approach to formulate this MIP
This is in concern to reformulating a previously formulated set of linear equations in my previous question: This is the link
\begin{align}
y_i &= 1 &&\text{for $i\in\{0,n+1\}$} \tag1 \\
\...
- 65
0
votes
2
answers
55
views
Reformulate IF-statement in mathematical optimization
I have an optimization problem that chooses which location must be opened based on a set of possible locations. And per location we have a certain amount of available spots from which we must buy a ...
- 3
0
votes
1
answer
56
views
How to convert non-linear equation to linear equation [closed]
I have a problem with X machines, each one with a specific production. All the production needs to be sent to an specific place via different routes which may or may be not cheaper.
I need to minimize ...
- 111
2
votes
1
answer
29
views
Mixed Integer Programming - variable that equals the sign of an expression
I want to define the following:
y = 1 if x<=th
= 0 otherwise
Currently I'm doing the following:
Let's say we know the lower ...
- 1,351
0
votes
0
answers
31
views
Converting constraint with absolute value equation into linear programming constraint
I have following constraints,
w1 = | XR1 - 20 |
where w1 is a binary variable and XR1 is a nonnegative variable. How can I convert this into a linear programming ...
3
votes
1
answer
71
views
Modeling contiguity of machine processing in a flow shop environment via a MIP
I'm working on a Mixed-Integer-Programing (MIP) formulation for a flow shop scheduling problem. One of the requirements/wishes is that for each machine $i$, processing should be contiguous, or at ...
- 101
2
votes
0
answers
51
views
Benders Decomposition Convergence
I have found James Murphy's "Benders, Nested Benders and Stochastic Programming: An Intuitive Introduction" (http://www.optimization-online.org/DB_FILE/2013/12/4157.pdf) to be quite helpful ...
- 41
0
votes
0
answers
31
views
How to write elseif into linear programming
Given:
If a < 0 and c < 0:
d = 1
else:
d = 0
I was wondering how to write it into statement of linear statement?
- 75
0
votes
0
answers
20
views
How to linearize the following if-then constraint with Or constraint involved?
I have the following constraint set that contain an if-then condition and or condition at the same time:
$$ \eta_i = 1 \...
- 367
1
vote
1
answer
117
views
Linear constraint considering binary bit position
Right now, I have some binary variables for a linear programming problem:
$x_1\;x_2\;x_3\;x_4\;x_5\;x_6\;x_7\;x_8$
Say these are groups of 4 bits each in this example. So:
Group 1 ={$x_1\;x_2\;x_3\;...
- 75
0
votes
0
answers
49
views
Is there a way to minimize the standard deviation in linear programming
Here is the scenario:
There are n boxes with $C_{a}$ of capacity at the beginning of each box before assigning.
I want to fit x parcels into the boxes, letting the capacity left for each boxes are as ...
0
votes
1
answer
28
views
Find a minimum threshold value for a constraint [closed]
I want to find a minimum threshold value for a constraint, such that if this constraint is satisfied, the next one must be satisfied.
For example, given two inequations $f_1(X)\geq a$ and $f_2(X) \geq ...
- 11
2
votes
1
answer
26
views
Resources to learn about modeling within the scope of Linear/Integer programming?
I'm currently taking a course in OR, and I'm facing some major difficulties trying to formulate my LP/IP problems. I understand most of the topics just fine, but I just get lost trying to formulate ...
- 153
0
votes
1
answer
40
views
Clustering data using mixed integer linear programming
I am trying to understand if it is possible to use mixed integer linear programming (MILP) in order to perform a basic clustering operation to a dataset $D$. I know there exists standard algorithms ...
- 2,109
0
votes
0
answers
11
views
How to figure out integer variables in the relaxation set?
Suppose, there is mixed-integer programming as follows:
$(1)$
$$\begin{aligned}
\min&\quad c^{\top} x\\
\text{s.t.}& \quad A x \geq b \\
&\quad B x \geq d \\
&\quad x \geq 0 \\
&...
- 113
0
votes
1
answer
48
views
why the code assigns multiple jobs on same position on machines
scheduling n jobs on m machines, each job has a different processing time on each machine. all schedule has n positions indexed by l as l =0,1,...,n as position 0 for dummy job
Used this mathematical ...
- 13
1
vote
1
answer
44
views
Linear Programming - Job Scheduling Domain Mapping To Binary Decisions
I am trying to maximise machine profit subject to a repair plan (job schedule), but cannot seem to map between the integer domain from the job schedule to the binary domain for the revenue model in ...
- 11
1
vote
1
answer
57
views
The difference between subtour-elimination constraints in the symmetric and asymmetric TSP
We know that there are lots of formulations for traveling salesman problem. Some of them are based on the directed graph (asymmetric) and others are based on the undirected graph (symmetric). Also, ...
- 113
1
vote
0
answers
31
views
Which Python package is suitable for solving the following mixed integer optimization problem?
Assume I have given a matrix $A=\mathbb R^{d \times n}$. I want to minimize the following:
$$\min \left \|
\begin{bmatrix}
a_{11} & \dots & a_{1n} \\
\vdots & \ddots & \vdots ...
- 33
2
votes
1
answer
27
views
Modeling the quotient of continuous decision variable in a MIP
For a continuous decision variable $S_{i,j}\geq 0$, I would like to know the quotient of its division by some number $x$, because I need to use it in another constraint. My initial thoughts to do this ...
- 101
1
vote
2
answers
39
views
Mixed Integer Linear Programming problem maximizing projects but they can share resources
I need help with this optimization problem. I'm sharing a simplified version for easier discussion.
For example, I have projects $x_i$ where $i=1,2,...5$.
Each project has factors $a_i, b_i, c_i$ with ...
- 13
1
vote
1
answer
40
views
How to write the following if-then condition in Mixed Integer Programming? If a<b then c=1, 0 otherwise
I am new to mixed-integer programming and I am confused about how to approach this if-then condition.
How do I the following constraint in mixed-integer programming:
if Dm +t < Dn + then Zmn=1, 0 ...
2
votes
1
answer
44
views
Modeling sequence dependent setup times via a MIP for flow shop scheduling
As part of a Non-Permutation Flowshop Scheduling (NPFS) problem, I would like my MIP model to be able to deal with sequence dependent setup times. That is, for each pair of consecutive jobs, a setup ...
- 101
1
vote
2
answers
158
views
MIP binary variable value based on value of continuous variable
I would like to model the following constraint:
$$
b =
\begin{cases}
1 \quad \text{if } c=0 \\
0 \quad \text{if } c>0 \\
\end{cases},
$$
where $b\in\{0,1\}$ and $c\in\mathbb{R}_{\...
- 101
0
votes
0
answers
32
views
Construct linear floorplanning constraints
This question is an extension of a previous question.
Right now, what I have are these "cheap" equations. The goal is to have the floorplan allow a circle with diameter, $D$ outside the red ...
- 71
1
vote
1
answer
41
views
Maximizing a quadratic function subject to linear constraints
Consider the problem:
$$maximize: Z = x_1+2x_2$$
subject to: $$x_1+x_2 \leq 8$$ $$-x_1+2x_2 \leq 2 $$ $$x_1-x_2 \leq 4$$
I know that this problem can be solved by using Branch-and-Bound ...
- 77
1
vote
1
answer
32
views
Modeling some constraints
We have two decision variables $x \in \mathbb{Z}^{0+}$ that is the main decision variable and $0 \leqslant y \leqslant 1$ that is an auxiliary decision variable.
Now based on the nature of the problem ...
- 37
0
votes
0
answers
22
views
Show that incidence vectors of s-t paths are the extreme points
Given a directed graph $G=(V,A)$, let $(U, \bar{U})$ be any partition of the vertices such that $s \in U$ and and $t \in \bar{U}$. Such set of $s-t$ arcs where $s$ and $t$ are tail and head, ...
- 180
2
votes
1
answer
41
views
Fixing a minimal number of variables in linear programming problem to worsen objective
Consider a fairly standard linear program with $A\in \mathbb{R}^{m\times n}$ and cost vector $c\in \mathbb{R}^n_{\geq 0}$ such that
$\begin{align*}\text{maximize}&& c^Tx\\\text{such that} &...
- 78
2
votes
3
answers
180
views
Linearization of product of a continuous and a discrete variable
From my previous questions, I have a variable : $Q$, which is function of a discrete known vector, $P$ and a binary variable $x$ : $Q=f(P,x)$.
I know, we can linearize the products of (a) two / ...
- 65
0
votes
0
answers
73
views
Want to form the linear equations for conditions given below: [duplicate]
I want to formulate the set of linear equations for the following conditions:
$Q(i) = 0$ if $y(i)=1$ for $i = 1,2,...,n$
$Q(i) = P(i)$, if $\sum_{j=1}^{n}{y(j)}=0$ for $j \le i$.
$Q(i) = P(i-r)$, if $...
- 65
1
vote
1
answer
204
views
I want help in formulating a mixed integer linear problem formulation
I want the following help in linear fashion (In my previous question, I asked the same but the solution was not generic. Please check it : Prev.Question).
I have an arbitrary vector: $P(n) = [1, 2, 3,...
- 65
1
vote
1
answer
113
views
How to translate minimization problem containing a min function into a Mixed Integer Problem (MIP)?
I have the following optimization problem:
$\min J = \sum_{i=0}^{N} k_i = k_0 + k_1 +\dots+ k_N$
s.t:
$k_i = f_i(z_i)$
where
$f_i(x) = \begin{cases}
x,& \text{if } x\leq P_i\\
P_i, ...
- 13
1
vote
1
answer
31
views
Choosing optimal intervals
I have two list of numbers of size N. For example, say N=6, x=[1, 3, 5, 10, 15, 20] and y=[1.5, 3.5, 4.7, 9, 12, 18]. I would ...
- 13
0
votes
1
answer
40
views
Optimization problem using MIP
I am trying to solve the following mixed integer programming problem. However, I have any problems with the approach of the model.
Problem: A company that sells athletic shoes aims to make the ...
user798113
0
votes
0
answers
41
views
How would I represent the following constraint in the linear form?
Given the optimization variables $\mathbf{a}, \mathbf{b} \in \mathbb{C}^{n}$ and $\mathbf{y} \in \mathbb{R}^{n}$, I would like to represent the following constraint to the linear form
$\mathrm{diag}(\...
3
votes
2
answers
143
views
Select five vectors that upon undergoing elementwise multiplication are most similar to another vector
I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows.
$$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
- 31
0
votes
1
answer
126
views
What are Bounds in Branch Bound
I am looking at a video to understand branch and bound more. Specifically, the one found at this link: (21) Ch06-03 Branch and Bound Method (B&B) - YouTube.
I have two questions:
Around 9:44, I'm ...
0
votes
1
answer
107
views
Converting a basic MILP into LP
I have a MILP looks like following:
$$ min \sum_i capacity[i] * weight[i] $$
where i=[Mid_North_1, Mid_North_2, North_Mid_1, North_Mid_2]
Basically I got 2 sites ...
- 125
0
votes
1
answer
91
views
one way conditional statement in binary variable linearization
I am trying to write a one-way conditional statemen with binary variables. my condition is (x and y are both binary variables)
(if x=1 then y=0)
and it is the only ...
