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.
387
questions
2
votes
1
answer
21
views
Several questions on Column Generation: degeneracy, columns in/out and non-integer solutions
I am currently using Column Generation accompanied with Dantzig-Wolfe decomposition to solve MILP. I have several questions to ask.
At the beginning, the objective value of RMP does not improve even ...
- 41
2
votes
2
answers
52
views
How to write a constraints on a first nodes for a courier-package problem?
We have an employee whose job is to pick up and deliver some packages, and they have each a capacity of C. They can also pick up multiple packages in their route, and packages can be transferred ...
- 23
0
votes
0
answers
15
views
Is type of variables can help in linearization?
I was wondering if the type of variables, whether binary or non-negative can affect the linearization?
For example assuming that $x_{i,j,t}$ and $y_{i,t,s}$ are two binary variables, then when we want ...
- 367
1
vote
1
answer
69
views
How to linearize an if-then statement?
I want to write constraints for finding a path for some rider, driver on a directed network problem.
Let $x_{i,j}^d$ indicate whether driver travels from $i$ to $j$ and $z_{i,j}^{r,d}$ indicates ...
- 25
1
vote
1
answer
40
views
Linearize tricky constraint to MILP, LP
It's hard to describe this constraints. Please check this:
It is a selection problem.
Item Name
Brand
Value
Price
item 1
A
0.1
0.2
item 2
B
0.2
0.3
item 3
A
0.1
0.3
We want to select several ...
- 13
2
votes
0
answers
45
views
Avoid Cycles in Integer Program
Traveling salesman problem can be cast to an integer program, see
https://gurobi.github.io/modeling-examples/traveling_salesman/tsp.html. The problem is, however, that the solution might contain ...
- 61
0
votes
0
answers
13
views
How to use SMT solver to prove model validation
I have a mixed-integer model with some parameters. I also have a set of validation rules telling me if the model is satisfiable. How can I use SMT solver to prove that my validation rules are valid ...
- 143
9
votes
1
answer
124
views
Shortest palindromic Egyptian representation for reciprocal integers
Consider the problem of representing the reciprocal of an integer as an Egyptian fraction where all the denominators are palindromes. i.e. write
$$ \frac{1}{n} = \sum_{i} \frac{1}{a_i} $$
where $a_i$...
- 2,132
0
votes
1
answer
56
views
How to minimize the gap between a fractional linear expression with a constant value?
how to minimize the gap between a fractional linear expression with a constant value
I have a selection problem with objective function like:
$$
min\mid\frac{\sum a_i\cdot x_i}{\sum b_i\cdot x_i}-\...
- 13
3
votes
1
answer
61
views
Issue with integer subproblem in Dantzig-Wolfe decomposition
I am dealing with an integer model, and I'm using Dantzig-Wolfe (DW) algorithm that I have developed in Matlab to decompose the model into a master and sub-problems. I put the integer constraints in ...
1
vote
1
answer
36
views
Portfolio optimization with cardinality constraint
The simple portfolio optimization problem with cardinality constraint is stated as
\begin{align}
\min_{\vec{w}} -\vec{\mu}^T \vec{w} + \frac{\gamma}{2} \vec{w}^T \Sigma \vec{w}
\end{align}
such that
...
- 113
1
vote
2
answers
37
views
Q: penalizing variables deviating from a given ratio
I want my optimization variables $\phi_1, \cdots , \phi _n >0$ (positive real) to remain around a known ratio, say $\alpha_1 :\alpha_2 :\cdots :\alpha_n$, where $\alpha_i\in (0, 1)$. To be clear, ...
- 55
2
votes
2
answers
90
views
About Benders decomposition for MILP [closed]
I have been using Benders decomposition for the following MILP:
Original problem
I put the binary y variables into the residual subproblem, which is as follows:
Residual subproblem
The dual form is:
...
- 41
0
votes
1
answer
30
views
CNF form of the logical $exactly(2) x_{i}$
Let's say, in order to linearize the product of the two binary variables the logical condition would be, z <=> (x and y), where x, y, and z are binary. The corresponding CNF form is as follows:
\...
- 115
0
votes
1
answer
25
views
linearizing if-then with two binary invoved
I need to linearize this $\alpha_i^{ap}=1 \implies \beta_{ij}^{ap} =1 $. As both are binary,
I think the right answer is $ \alpha_i^{ap} \ge \beta_{ij}^{ap} $. But rading one of the questions a the ...
- 3
-1
votes
2
answers
38
views
Conditional statement in mixed integer linear programming
I have been trying to enforce the following conditional statement in a MILP:
If $X_1 + 2(X_2 + X_3) = 4$, then $X_4 = 1$.
where $X_1, X_2, X_3, X_4$ are binary.
How can I write this in conventional ...
3
votes
0
answers
69
views
How many variables and constraints can modern mixed integer programming solvers handle? [closed]
I know it depends on the specific problem instance, but approximately how large of an MIP problem can we write and still be guaranteed that an optimization solver will find a solution? For instance, ...
- 259
1
vote
1
answer
49
views
Which linearization is correct?
I'm trying to linearize the following constarints, however, Iam not sure if it's correct? Both of the make sense and seems incorrect at the same time! Could anyone help me to identify what I'm missing?...
- 25
0
votes
1
answer
22
views
Is the product of two variable summations convex?
I have a mixed integer programming problem, which I believe may be convex.
Namely, I have a matrix $R$, where rows are seats and columns are riders. The idea is optimally seat riders on the bus such ...
- 203
2
votes
1
answer
25
views
Find cycles with fixed number of edges without shared vertices in a directed graph
I am trying to find minimum weighted cycles with fixed number of edges without shared vertices in a weighted directed graph. Specifically, say I need to find 4 cycles (one cycle per user) each with 5, ...
- 21
0
votes
0
answers
31
views
Minimizing $\|A x - b\|^2_2$ subject to $x \in \{0,1\}^n$ or $x \in \Bbb Z^n$
I have the following Boolean least-squares problem.
$$ \underset{x \in \{0,1\}^n}{\text{minimize}} \quad \| A x - b \|_2^2 $$
where $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R}^n$. A ...
2
votes
1
answer
74
views
Valid inequalities in a polyhedron
Let $\alpha, \beta >0, k \in \mathbb{Z}$, $\pi \in \mathbb{R}^n, \pi_0 \in \mathbb{R}$. Let $P\subset \mathbb{R}^n$ be a polyhedron, such that the inequalities:
$$\pi x \leq \pi_0 +\alpha (x_j -k) $...
- 415
2
votes
1
answer
62
views
Maximising average of decision variables : mixed integer programming
I am trying to linearise a model I came up with for this problem:
I have $n$ binary decision variables $x_i$ , each assosiated with a revenue $c_i$.
The profit will be either the weighted average of ...
- 729
1
vote
0
answers
20
views
VRP where only a subset of vertices needs to be visited
Hi just a quick question, I am looking at a VRP problem, where only a subset of costumers needs to be visited.
So given a complete graph G=(V,E) a fleet of vehicles needs to service a given number $n$ ...
- 113
1
vote
1
answer
113
views
Multiplication of two continuous variables
I am working on MILP problem using AMPL/CPLEX. How to model the multiplication of two continuous variables x,y? and does it make a difference if they are integers?
Thank you.
- 33
2
votes
1
answer
51
views
Modelling a different ranges constraint based on a value
I want to set a variable $D$ to a certain value based on another variable $X$ depending on the range of $X$ as follows:
if $0<x \le100 , D =2$
if $100<x \le200 , D =5.3$
if $200<x \le300 , ...
- 33
0
votes
1
answer
32
views
Formulate nonlinear conditions as linear constraints.
Is there a way to formulated the conditions below in the form of linear constraint(s)?
If $S_1 ≤ 1$ and $S_2 ≤ 1 ⇒ X = 0$
If $S_1 ≥ 2$ or $S_2 ≥ 2 ⇒ X ≤ 1$
$S_1, S_2 \in \left \{ 0, 1, 2 \right \}$
$X ...
- 3
0
votes
1
answer
45
views
Linearize if else constraint in a MILP
How can you write the following if/else condition in a linear form?
If S ≥ 3, then X ≤ 1,
else X = 0
with
S ∈{0, 1, 2, 3}
X ∈{0, 1}
I've seen some examples where X is forced to a value in the if ...
- 3
0
votes
2
answers
70
views
How to convert a non-linear constraint to a linear constraint?
How to convert non-linear constraint $s_{k} = \min(t_i y_{ik})$ to MIP constraint?
Here, $t_i$ is a positive decision variable and $y_{ik}$ is a binary decision variable.
1
vote
0
answers
16
views
Nonlinear discrete and continuous optimization problem
I'm trying to minimize a cost function that is made up of dependent binary variables and continuous variables.
For example the cost function could look like:
$F(x_{0}, x_{1}, x_{2}, r_{0}, r_{1}) = 0....
- 111
0
votes
1
answer
80
views
How can I apply the McCormick Envelopes to the product of two binary variables?
I've seen the McCormick envelopes applied many times to the product of two continuous variables, but I can't seem to find when both of them are binaries. Also, I applied the restrictions as described ...
1
vote
0
answers
35
views
Conversion into MINLP
I want to solve the following optimization problem.
\begin{aligned}
\text{Objective:} \hspace{1cm} & \text{maximize} \hspace{0.2cm} \sum_{s=1}^{N}{\frac{1}{N}}\left[\sum_{t=1}^{T}\left(\frac{1}{...
- 33
1
vote
2
answers
28
views
When to construct LP, IP, or MIP model
After doing a few optimization word problems, I've noticed I'm struggling a bit when trying to determine whether or not to set up the problem as an Integer Program, Linear Program, or Mixed Integer ...
- 11
0
votes
1
answer
24
views
Variable Neighbourhood search (VNS): How to specify the neighborhood structures?
I am new to optimisation and looking into VNS to attempt to apply a meta-heuristic to a MIQP in the form $$\max_x x^TQx$$
subject to: $x_i\in\{0,1\}$, $\sum_i x_i=C$, where $C$ is an integer.
I don't ...
1
vote
1
answer
50
views
Need help establishing linear objective and linear constraints
So I have a problem, that is really similar to the assignment problem.
Basically there is a company producing square envelopes. A number of papers should be put into the envelope. Exactly one paper pr ...
4
votes
2
answers
163
views
Problem-Heavy References in Linear/Integer/etc. Programming and Operations Research
I am reaching out for problem-heavy references in Linear / Integer / Mixed-Integer (MIP) / Non-Linear / Network Programming and Operations Research (and Linear Algebra as it pertains to the ...
user1098096
1
vote
1
answer
148
views
Linear Programming: Either OR constraint non-binary decision variables
I'm working on a production problem where I'm producing a number of products. My decision variables indicate quantity levels of production across a range of prices. My current LP solves for the ...
- 23
1
vote
2
answers
33
views
Bin packing with load fairness across the bins
The bin pack problem denotes the process of assigning a set of n items into a minimal number of bins of capacity c. It can be simply formulated as an ILP as per the below description:
My question is :...
- 111
1
vote
1
answer
48
views
Integer allocation problem alternative to MI-SOCP?
Can the following problem be solved without needing to use a MI-SOCP solver? I think I can code it as just a simple parallel branch-and-bound search but I'm not sure if the performance will be close ...
- 13
1
vote
1
answer
22
views
Retaining the variable value for some consecutive intervals
I have been trying to model a constraint for a variable in an MIP formulation. My problem is like this; X(t) is a variable, whose value has to remain constant for some pre-defined consecutive periods ...
1
vote
0
answers
37
views
What is an unimodular problem?
Given an optimization problem below:
$$ \min_{Y^m_{ij} \in \{0,1\}} \sum_{p \in P} \sum_{(i,j)\in A} \sum_{c \in C} n^c \rho_{ij}^{p,m(c)} X_{ij}^c\\
\text{where } X_{ij}^c \text{ solves:}\\
\min \...
2
votes
1
answer
288
views
How to transform a nonlinear constraint to linear constraint using big M?
Given a nonlinear constraint
$$xy=0$$
where $x$ is a continuous variable and $y$ is a binary variable.
Question: Using the Big-M method, how do I get to change the constraint above to a linear ...
2
votes
1
answer
72
views
How do I solve this mixed integer program?
I have a minimisation problem in the following form
$$\textrm{min}: x^TAx$$
constrained by $\sum x_i=N$
where $x$ is a vector containing only 1's and 0's, and $A$ is a square matrix of real numbers.
...
2
votes
1
answer
120
views
What is the best way to convert this into a integer linear program and what is the best way to solve such a problem?
I am studying a mixed integer program in the form
$$ \textrm{min}: \sum A x$$ constrained by $\sum x_i = N$
where $x$ is a vector containing only 1's and 0's, N is an integer, and $A$ is a square ...
- 33
1
vote
0
answers
49
views
Maximizing summation function with variable in index and in upper bound
I have a function $f(N_i, P_i) = \sum_{i=1}^M(N_i(1-kP_i))-\sum_{i=1}^M\sum_{j=1}^{N_i}\alpha_{ij}$, where $\alpha_{ij}$ are parameters. I want to maximize this function.
I want to maximize this ...
- 67
2
votes
2
answers
57
views
How do I transform the following set of conditions into inequalities?
I've been working on a mixed integer linear program for quite a while now and I need to set up constraints involving binary variables. I just can't find the correct answer to the following problem. ...
- 21
1
vote
1
answer
41
views
How to count gaps in a timetable?
I have a timetable with $n$ time slots. There can be an arbitrary amount of appointments in this timetable.
Some example schedules for $n=4$: $(x_1, x_2, x_3, x_4)$: $(1,1,0,0), (1,0,0,1), (1,1,1,0) $,...
- 13
4
votes
0
answers
110
views
Minimizing the difference of convex functions in MIP
I am working on the following mixed-integer program (MIP):
$\min_{\mathbf{x}, \mathbf{y}} \ f(x_{1}) - f(x_{2}) + c_{x}^{\top}\mathbf{x} + c_{y}^{\top}\mathbf{y} \\
\text{s.t.} \\
A\mathbf{x} + B\...
- 303
2
votes
0
answers
24
views
Understanding "Blessing of Binary"
The theorem I am stating is Theorem 6.2 (Blessing of Binary) of the dissertation THE ROLE OF EXTREME POINTS FOR CONVEX HULL OPERATIONS, which was cited from Stochastic Dual Dynamic Integer Programming ...
- 3,206
2
votes
1
answer
83
views
What are the prerequisites to learning integer programming and what textbooks would you recommend to learn it?
There was this course in many undergraduate mathematics programs called integer programming. It included Modelling, Linear Programming Primal, Linear Programming Duality, Dual Simplex Algorithm and ...
- 95