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.
0
votes
0answers
21 views
integer programming linearization
I have two variables. $g$ is a binary variable and $s$ is a continuous variable. Goal is to linearize this $gs \geq0$ a.k.a if $s \geq 0, g = 1\:\: \text{or}\:\: s\leq0, g = 0$. How can I linearize ...
0
votes
0answers
29 views
SOS1 for linearizing complementarity condition
I am trying to linearize the complementarity condition
$0<a \perp b>0$ with SOS1 method by the following formulation:
$p_1+p_2 = 1e5 \label{1}\tag{1}$
$a < p_1\label{2}\tag{2}$
$b < ...
1
vote
1answer
21 views
Question to the solution of “Indicator Variable if x is in specific range”
This question is to query the solution provided by Erwin Kalvelagen to the post
Indicator Variable if x is in specific range
and
conditional constraint: if $x \in [a,b]=> z=1$
(Sorry for ...
0
votes
0answers
10 views
Bus fleet requirement for transporting passengers/baggage between airport terminals
I am trying to determine the optimum number of buses required for loading and unloading of passengers/baggage. The buses perform following tasks:
Transport terminating passengers and their carry on ...
1
vote
1answer
28 views
Do redundant constraints help in big-M reformulation?
I am trying to reformulate an optimisation problem with unknown $x$ of dimension $K\times 1$ into a mixed-integer program using big-M transformation.
In this respect, among my constraints, I have ...
0
votes
0answers
18 views
(Generalized) Benders Decomposition of MINLP Leads to Linear Master and Sub Problem
I have a mixed-integer nonlinear program (MINLP) which I want to apply (Generalized) Benders Decomposition (GBD) to.
The nonlinearities exclusively originate from products of first-stage decision ...
0
votes
0answers
31 views
which combination(partiotioning ) has the smallest value?
A positive integer can be partitioned, for example, the number 7 can be partitioned into the following:
$7=7$
$ 7=6+1$ , $ \ \ 7=5+2$,$ \ \ 7=4+3$
$ \ \ 7=4+2+1$,$ \ \ 7=3+3+1$,$ \ \ 7=3+2+2$,
$ \ ...
2
votes
1answer
53 views
MIQP problem slow to solve: how to rewrite it?
I am looking for suggestions on how to rewrite a MIQP problem.
Let me firstly introduce the problem
Notation:
The unknown vector is $x$ with size $(4*2+225*2)\times 1$.
We can think of the ...
0
votes
1answer
25 views
How do you set up this constraint in integer programming using binary variables?
Mike wants to invest in $X_1$ if and only if he invests into $X_2$ or
$X_3$ or both.
Please help i can't get my head around this
Thanks
0
votes
1answer
44 views
Rewrite $[p_1(x)\geq 0 \text{ and } p_2(x)\geq 0] \Rightarrow q(x)\geq 0$, $[-p_1(x)\geq 0 \text{ and } -p_2(x)\geq 0] \Rightarrow q(x)\geq 0$
I am trying to reformulate an optimisation problem with unknown $x$ into a mixed-integer program. In this respect, I would like your help to rewrite the following constraints
$$
\begin{cases}
p_1(x)\...
1
vote
1answer
66 views
Rewrite the constraint $ p(x)=0 \Rightarrow q(x)=0 $ in an optimization problem
I am trying to reformulate an optimisation problem with unknown $x$ into a mixed-integer program. In this respect, I would like your help to rewrite the following constraint
$$
p(x)=0 \Rightarrow q(x)=...
0
votes
0answers
15 views
How can i make refrigerator operations should be sequential?.
I am working on the appliance scheduling problem, tried to create the constraint that imposes the refrigerator tasks should be run sequentially.
I have a binary variable $x_{t, u, i, j}$ is 1 if task ...
0
votes
0answers
9 views
How to model and formulate this optimization problem on clustering?
I have a system with 72 nodes.
I have a binary adjacency matrix $S$ of size $72\times 72$. If $S_{i,j}=1$, then node $I$ is adjacent to node $j$. So, we also have $S_{i,j}=S{j,i}$. So, $S$ is a ...
4
votes
2answers
92 views
How to prove that 1/3 is the optimal solution for the muffin problem with 5 students and 7 muffins?
The Muffin Problem
Definition
Let there be $m$ muffins and $s$ students. The problem is to divide the muffins into pieces where every student gets exactly $\frac m s$ muffin, such that the size of ...
1
vote
2answers
78 views
MILP: Minimizing $|Ax-b|$ with at most 5 x variables being non-zero
I have a $m \times n$ matrix $A$, where $n$ is very large and $ n>m$ (underdetermined), and $b$ is $m \times 1$ matrix. I want to minimize $|Ax-b|$, but at most $5$ $x_i$ can be non-zero. Other ...
0
votes
1answer
25 views
Forcing a series of OR statements in ILP Problem
I am attempting to solve an ILP program in relation to maximizing the return on investments. There are 10 decision variables, $x_1, x_2, ...,x_{10}$, with the following goals:
Max $0.067x_1 + ...+0....
3
votes
1answer
36 views
Transportation problem with the least number of transportations.
I have a non trivial case of transportational problem. Let me get you familiar with it.
We have $n$ suppliers $a_1, ..., a_n$ and $m$ consumers $b_1, ..., b_m$.
The suppliers volume of goods to ...
1
vote
1answer
35 views
Solving an integer (boolean) constraint satisfaction problem
I have a 0-1 integer constraint satisfaction problem of the following form: find binary vectors $x = (x_1,\dots,x_m) \in \{0,1\}^m$ and $y = (y_1, \dots,y_n) \in \{0,1\}^n$ that satisfy the ...
0
votes
1answer
33 views
binary quadratic mixed integer nonlinear programming to inequalities
I have this unconstrained z=x.y where x,y are 0-1 integers. How to reformulate that into set of mixed integer linear inequalities with exactly the same feasible region?
0
votes
1answer
42 views
How to count occurrences in linear programming
This is an integer linear programming question.
Let $L$, $T$, and $R$ be positive integer values and define the sets $\mathscr{L} = \{1,2,\ldots,L\}$, $\mathscr{T} = \{1,2,\ldots,T\}$ and $\mathscr{R}...
1
vote
1answer
42 views
Why adding a few rows of constraints can dramatically slow down the running time of MIP optimization?
I am working on a linear mixed-integer programming (MIP) optimization problem. Let's say the constraint can be denoted as $Ax\leq b$, where A is the constraint matrix.
Previously, A has a dimension ...
1
vote
1answer
38 views
Modeling an optimization problem as linear programming problem
Attempt:
First, I call $x$ be the number of shafts produced per year and $y$ the number of frames produced per year. We have that each machine works at most $4500$ hours. we can place all of our data ...
-1
votes
1answer
36 views
Reducing data sparsity in linear integer programming
I have following decision variables and constrains in my ILP model. Resolution time of CPLEX solver grows exponentially with respect to problem space getting larger. Is that solely because 4D matrix ...
1
vote
1answer
33 views
How to create constraints for Mixed integer linear problem?
i am a beginner to Discrete optimization domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can ...
0
votes
1answer
70 views
Linearization of product of three variables
Let $h=xyz$, where $x,y \in \{0,1\}$ and $z \in [0,T]$ with $T>0$ being a constant. Is there any method that can linearize $h=xyz$? For example, if $h=xy$ the method in here can be used to ...
0
votes
0answers
36 views
Graph Clustering - Capacitated VRP on a MultiDiGraph
I'm working on the problem of the CVRP on a Multi Directed non-complete graph that has been extracted from OpenStreetMaps using OSMnx.
In the extracted graph I have also 'flagged' several delivery ...
0
votes
0answers
35 views
Convert the following model to quadratic integer programming
Really having a hard time with this.....Convert the following model to a quadratic integer program:
Maximize $Ay$ subject to $Bx \leq d$ and $y\in$ argmax $x^TMy.$
Does anyone have any idea? Or ...
0
votes
1answer
41 views
Convert fractional to quadratic integer programming
Maximize $\frac{\sum_i\sum_ja_{ij}x_iy_j}{(\sum_ix_i)(\sum_jy_j)}+ \frac{\sum_i\sum_jb_{ij}x_iz_j}{(\sum_ix_i)(\sum_jz_j)}$, subject to $Ax+By+Cz \leq d, \quad x,y,z\in \{0,1\}$.
Can we convert the ...
0
votes
0answers
43 views
Adding to the objective the absolute differences of numbers that are multiples of decision variables in mixed integer programming
I am trying for formulate a mixed integer program that optimizes the cost of transferring water through three piping systems.
I have three tanks $S_i$, $i= 1,2,3$. Each tank $S_i$ has $5$ pipes ($j=...
0
votes
1answer
47 views
Convex constraint in a Mixed-Integer Program
I have an optimization with the following convex constraint:
\begin{equation*}
x_1^2+x_2^2\leq \textrm{C}_1\cdot x_3 + \textrm{C}_2\\
\end{equation*}
My problem also contains some integer variables (...
1
vote
1answer
41 views
Is the LP-relaxation value on a subset of variables a bound for that subsets value in the MIP solution?
Say we're given the following integer problem:
$\min c^Tx$
s.t
$Ax \leq b$
$x \in \{0,1\}^n$
and its corresponding LP-relaxation:
$\min c^Tx$
s.t
$Ax \leq b$
$x \in [0,1]^n$
Then we can ...
0
votes
2answers
89 views
How to add integer cut to MILP constraints to find alternative optimal solutions?
I am solving an MILP optimization with binary variables in MATLAB in which I want to find more than one optimal solution by excluding previous solutions. Therefore, I know I must include the following ...
0
votes
1answer
35 views
Coping with $y = \text{max}\{b-x,0\}$ in constraint for MILP
Problem Description:
I have a mixed integer linear optimization problem (MILP) with objective function $$\min_{x_{jt}} \sum_\omega \sum_j \sum_t y_{jt}(\omega)$$
I know $L_{jt}\le x_{jt}\le U_{jt}$ ...
3
votes
1answer
35 views
dual of sub problem is infeasible, What should we do?
i have this problem
\begin{equation}
\begin{split}
\min &\; c^Tx + b^Ty\\
s.t. & \; Ax \ge d\\
& \; Bx +Dy \ge h\\
& \; y\ge0, x\in\mathbb{X}
\end{split}
\label{OP}
\end{equation}
i ...
2
votes
0answers
83 views
Benders Decomposition Type of Optimality Cut
In Bender's decomposition we use optimality cuts.
An optimality cut is $\pi^T (h-Bx)\leq\phi$ or
$b^Ty'+\pi^T (x-\hat x)\leq\phi$, depending on the subproblem.
I read in the book that both cuts ...
1
vote
0answers
28 views
Probability parameter in a constraint
In a clinic, the patients must be assigned to doctors. However, the clinic is struggling with the no-show patients problem, so they have developed a probability that the patient will effectively ...
1
vote
0answers
44 views
Linear programming - problem with constraint
Context:
Your enterprise have 15 trucks and 200 clients. Each truck has a fixed cost of utilization of 600 USD and each one can deliver the products to a max 12 clients. If you need more trucks to ...
0
votes
1answer
37 views
MILP formulation using binary variable
I am trying to formulate the following MILP:
A company produces products A and B by processing material M through
a machine. The requirements and selling price of a unit of each product are
given as ...
2
votes
0answers
37 views
The best approach to tackle the following class of mixed integer nonlinear programming models
I would be thankful if anyone can help me to find the best approach to solve the following MINLP model. In this model, $p_{js}$, $p_{js}$ and $Q$ are parameters. $x_{js}$ is a binary variable and $y_i$...
2
votes
0answers
58 views
Implementing Benders decomposition for MILP
I'm trying to implement a Benders decomposition on MILP. But I cannot understand a notation in the sub-problem constraints.
What does ":" mean in the following sub-problem? The implementation works ...
1
vote
0answers
31 views
ADMM Heuristic or rather stick to Branch and Bound?
I'm intending on giving a solution to this MIQP, which should be faster than the one of solving the exact problem with GUROBI or CPLEX.(It muss not give always the global solution!)
The main ...
0
votes
1answer
81 views
What is the fastest mixed-integer convex programming software?
So far I had used CVXGEN to solve convex optimization problems in real-time, but as far as I know, it cannot handle Mixed-integer Convex Optimization problems.
What is the fastest software available ...
0
votes
2answers
34 views
How to linearise the constraint with a product term? [closed]
I would like to linear the following constraint
$$y\cdot \sum_{i=1}^{N}\mu_ix_i \geq M$$
where $y$ is a positive integer variable, $x_i \in \{0,1\}, i =1,...,N$ are binary variables, $\mu_i, i =1,...,...
1
vote
1answer
87 views
Why Benders cuts are valid?
In Benders decomposition algorithm, we first solve a master problem which provides us with a solution vector. We then use this vector to construct a subproblem. For a minimization problem, subproblems ...
1
vote
1answer
22 views
Adding a combination of and + or operator constraint in Linear Programming
I have a list of paired variables(paired_list) like below and a resultant variable(my_res).
paired_list = [[a,b],[c,d],[e,f],...].
Here a,b,c,d,e,f are also ...
0
votes
0answers
30 views
MILP formulation
I am currently working on a problem which implies to formulate a MILP problem, but I am a beginner in this field.
The point is, in my opinion, mainly that I don't know if this type of problem has a ...
1
vote
1answer
75 views
Operations Research - Optimal transport routes II
I am interested in how one would modify the below question and answer (what extra notation to use) if routes where more than one base can be considered. For example Main base-->1-->3-->Main or Main ...
1
vote
1answer
34 views
How can i evaluate the time complexity of a mixed integer scheduling problem?
I am solving a complex scheduling problem by formulating it as a mixed integer linear problem and using the branch-and-cut algorithm. I have several different input parameters which can be changed - ...
3
votes
1answer
121 views
Operations Research and Analysis
A sports manufacturer produces two products: footballs and baseballs. These products can be produced either during the morning shift or the evening shift. The cost of manufacturing the football and ...
0
votes
1answer
32 views
What is the geometric representation of a mixed integer second order cone program?
Just as the title suggests, what is the geometric representation of a MISOCP? I know a SOCP can be geometrically (or visually) described as a cone... what about a mixed integer second order cone ...
