Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
339
questions
3
votes
3
answers
281
views
Scheduling for the shortest days using ILP
I've tried Or-Tools and MILP solvers a couple of different ways on this, but they take a surprisingly long time to realize that the solution they generated fairly quickly is in fact minimal. Is there ...
- 39
5
votes
2
answers
353
views
The importance of evaluating the number of constraints
If I introduce a problem, say as an ILP formulation, should I also discuss the number of introduced constraints? If yes, why?
- 561
1
vote
0
answers
54
views
Product allocation to vendor according to their demand
Company X has 3 types of products and due to the limited availability of raw materials, the production of products are also limited.
They have partnered with Store A for them to sell their products. ...
- 29
5
votes
1
answer
324
views
Is it possible to identify all possible Irreducible Infeasible Sets (IIS) for an infeasible Integer Linear Programming problem? (ILP)?
For an Integer Linear Programming problem (ILP), an irreducible infeasible set (IIS) is an infeasible subset of constraints, variable bounds, and integer restrictions that becomes feasible if any ...
- 59
3
votes
1
answer
207
views
Conditional constraint with a strict inequality
It's almost this question: Formulating the conditional constraint
But there they have non-strict inequality. I have $x_i$ a boolean decision var and $Q_i$ as a nonnegative integer decision variable ...
- 143
5
votes
1
answer
135
views
What fraction of the search space has been searched for ILP?
Is there a way to make Gurobi output (an estimate of) how much of the search space has already been cut off as infeasible?
If not with Gurobi are you aware of any binary only (912 of them) ILP solver ...
- 3,975
4
votes
2
answers
220
views
Deriving order/rank variable from another decision variable
There is a decision variable $x_i$ which denotes the time when a person is allowed to do his work.
The objective function is
$\min (x_i - a_i)$
where $a_i$ is the time when the person arrives at the ...
- 41
4
votes
1
answer
197
views
Constrain Mixed-Integer problem such that a graph is fully connected
I have a problem (see my questions about Architectural layouts which poses an interesting abstract question) where there exists an implicit (symmetric) graph whose values in the adjacency matrix are ...
- 3,975
3
votes
0
answers
97
views
Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case
Consider the following mixed-integer linear programming (MILP):
\begin{equation*}
\begin{array}{ll@{}ll}
\text{maximize} & 1 & \\
\text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\
...
- 173
4
votes
2
answers
406
views
When is a formulation with min function an ILP problem?
Consider a simple formulation like the one below.
\begin{align}
\max&\quad\sum_i x_i\\
\text{s.t.}&\quad x_i \leq \underset{\forall j<i}{\text{min}}\ f(x_j)
\end{align}
I am just wondering ...
- 561
1
vote
1
answer
153
views
Linearization of constraints in a ILP
I have been working on a Graph Theory problem for my thesis and got stuck about the linearization of some constraints. I am hiding everything, constraints, variables and so on, of my problem not ...
- 583
9
votes
2
answers
524
views
Mixed-Integer Linear Programming With Free Variables
In the classic Mixed-Integer Linear Programming (MILP), the variables are fixed to be either integer or real. I am interested in the following MILP variant, where only one thing different from the ...
- 173
2
votes
0
answers
251
views
About combinatorial Benders Cuts
I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
- 331
5
votes
2
answers
387
views
R package for multi objective integer evolutionary algorithm
I have a discrete event simulation (simmer package) based on probability distributions in R. I would like to optimize the variables according to several (2 or more) objectives. I used the NSGA-II ...
- 51
1
vote
0
answers
59
views
Building blocks for unimodular matrices
I read Chapter 19.4 of Schrijver(1986) and get to know that every totally unimodular matrix can be produced by taking operations on network matrices and two certain matrices. I find that some paper ...
- 137
5
votes
2
answers
915
views
In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?
In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something.
I'm working ...
- 51
2
votes
0
answers
80
views
What if anything do linear relaxations of "nearby" MILP nodes tell us about other MILP nodes
Assume we are given MILP where $y \in (\mathbb{R}^+)^n$, $x_1, x_2 \in \{0, 1\}$ are the integer variables. It is obvious that this problem when solved via branch and bound has a 2 deep b&b-tree.
...
- 3,975
5
votes
1
answer
173
views
Use of comparisons in objective function of an ILP
If the objective function of a problem contains a comparison between two linear statements, can the problem still be defined as an Integer Linear Program? For example:
$$\text{max} \sum_{\forall i,j} ...
- 53
2
votes
1
answer
274
views
Benders Decomposition cuts for MILP problem with further separable subproblems
I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
- 331
2
votes
1
answer
219
views
Is there any solver intended specifically for integer and binary variables alone on the optimization model other than solvers for MIP, MILP?
Any solvers which can be integrated in python where we can quickly solve if we have integer and binary variables alone in our model other than normal solvers for MIP, MILP?
- 125
2
votes
2
answers
1k
views
0
votes
0
answers
197
views
Check VRP instance is feasibility
Beforehand, this is a very long thread, in case you want to know in advance, to see if this thread's interests match with yours, this thread concerns fast ways of determining whether a VRP instance is ...
- 1,198
3
votes
1
answer
391
views
Scheduling minimization Integer Programming problem formulation
I am working with integer optimization. I have a problem with $t$ tasks and every task $i$ needs $w_i$ weeks to be completed and $p_{il}$ workers on a specific week $l$. There is a total time in weeks ...
- 33
3
votes
0
answers
45
views
MIP: Do binary variables perform better that integers? [duplicate]
I have a model where investments can be done in blocks. Now I could model this with integer or binary variables. Does anybody know which one is the better choice in terms of computational performance?
- 31
5
votes
1
answer
146
views
if $x = 0$ then $y \ne b$
I'm trying to model the following:
if $x=0$ then $y \ne b$
$y$ is a positive integer number( $y\le U$) and $x$ is binary and $b$ is a constant.
- 153
1
vote
2
answers
598
views
How to make the elements of the solution of gurobi belong to the elements of the specified list?
If I want to use the elements of the list as the range of the solution, like list1 = [10,20,50,60,30],and the elements of the solution must belong to the elements of the list The sample example as ...
- 57
1
vote
0
answers
133
views
How can I set the solution of gurobi to be a multiple of 10 instead of all integers?
For example, the solution for gurobi has two solutions, as follows: [10,20,50,70] [55,79,30,80] I only want to output solutions that contain only multiples of 10. The sample example as follow:
...
- 57
5
votes
1
answer
150
views
Is that Ok to exclude fixed components from an objective function?
Suppose we have the following objective function with one decision variable $x_i$ where $p_i$ is a fixed parameter for each $i$ and also, $a$ is a constant for the problem
\begin{align}
\label{eq} \...
- 489
2
votes
1
answer
994
views
Capacitated Maximum Coverage Location Problem, Python and Gurobi
I am building a variant of the maximum coverage location model and want to limit the amount of points that each "facility" can cover. I am using Gurobi optimization . I have tried using the ...
- 23
3
votes
1
answer
197
views
Need help with an appointment scheduling problem
I am currently stuck on writing a linear programming model to describe the process of appointment scheduling for an Oncological Center. I wanted to share it with you guys and see if anyone here could ...
- 31
4
votes
1
answer
208
views
An efficient Integer programming model for the minimum spanning tree problem?
Let $T=(V, E')$ be a spanning tree of a graph $G=(V, E)$. Rather than verifying for any subset of vertices $S\subseteq V$ that $|E'(S)|=|S|-1$, is there an efficient way to satisfy the spanning tree ...
- 173
2
votes
1
answer
142
views
How to prove the following statement about convex hulls?
Consider $M$ finite sets of integer points $P_m$, $m=1,\ldots,M$. Let
$$A = \left\{x_m\in\operatorname{conv}P_m, m=1,\dots,M, \sum_{m=1}^MN_mx_m=0\right\}$$
and
$$B =\operatorname{conv}\left\{x_m\in ...
- 1,641
7
votes
1
answer
212
views
Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?
The Lagrangian relaxation approach is used to generate lower (upper) bounds for minimization (maximization) problems by moving some constraints to the objective function and multiplying them by "...
2
votes
1
answer
70
views
Finding the minimum of a group of timings
I would like to seek some modeling advice on the following:
Say for instance I have 5 nodes representing workstations of the operation of 5 jobs, and that I have less than 5 vehicles. Say I have two ...
- 707
6
votes
0
answers
123
views
Characterization for total dual integrality
A problem I study reduces to whether the polyhedron $P=\{\mathbf{x}\mid A\mathbf{x}=\mathbf{1}, \mathbf{x}\geq0\}$ is integral ($A$ is a matrix with coefficients in $\{0,1\}$). I know that the ...
- 137
4
votes
1
answer
95
views
Name for subclass of ILP without any inequality constraints (including constraints on x)
In "Myths and Counterexamples of Mathematical Programming" myth "IP Myth 21" says:
The problem of finding $x\in \mathbb{Z}$ such that $Ax=b$, where $A\in\mathbb{Z}^{m\times n}$ ...
- 3,975
4
votes
2
answers
575
views
MAX-CUT: are there any algorithms or codes for classical computers, that cater to this specific case?
I missed the opportunity to ask this on OR.SE by 24 days! I asked it at CS.SE on 6 May 2019 and OR.SE entered Private Beta on 30 May 2019.
It's a problem about minimizing a sum of terms that are ...
- 1,268
9
votes
3
answers
958
views
No-good cuts for general integer variables
Question:
Suppose we have an integer program $\min\{c^\top{x}\mid{Ax\leq{b}},x\in\mathbb{Z}_+^n\}$, and suppose that $x^*$ is a feasible solution for this IP (or even that $x^*$ is an extreme point of ...
- 2,047
7
votes
2
answers
604
views
Can a generic ILP solver find graph matchings as fast as a specialized algorithm?
Finding a maximum matching, or a maximum-weight matching, is a well-known problem, which has polynomial-time combinatorial algorithms.
It can also be formulated as an integer linear program.
In ...
3
votes
1
answer
975
views
Efficient solver for multiway number partitioning
I am interested in the following problem.
The input is a set of $n$ integers, and a fixed integer $k$.
The required output is a partitioning of the integers into $k$ subsets, such that the smallest ...
3
votes
1
answer
486
views
Constraints that set values to binary variables depending on other binaries
I am trying to write a mathematical problem that involves some conditions based on binary variables. More specifically, I have a set of three binary variables $d_1$, $d_2$, $d_3$ and depending on ...
- 133
4
votes
2
answers
1k
views
Scheduling optimisation constraint on consecutive shifts & consecutive night shifts (`python`)
I am trying to write a program to schedule a team of 8 individuals into shifts.
I want to know how to model that every individual must get at least one night shift break, and must not work two ...
- 149
2
votes
1
answer
136
views
How does the RCPSP's precedence constraint work?
In [1] the authors define the RCPSP (resource-constrained project scheduling problem) as follows:
minimize
$$
\sum_{t} t x_{n t}
$$
subject to
$$
\begin{array}{c}
\sum_{t} x_{j t}=1, \quad j \in J, \\
...
3
votes
2
answers
122
views
IP model for k-rooted spanning forest
I am looking for an IP model for finding a $k$-rooted minimum spanning forest on an undirected graph $G$.
Given a set of roots $R$ and a set of nodes $N$ $(R\cap N=\emptyset)$, I would find a forest ...
- 937
3
votes
0
answers
163
views
How to linearize a max min objective function?
Let us suppose that I have a $\max \min$ objective function that only depends on one set of variables:
$\underset{x}\max \underset{y}\min dy$
Associated with the linear set of constraints and right ...
- 583
1
vote
1
answer
162
views
Generating numbers that should add up to a fixed value while they follow a known distribution
Suppose a perishable item that is associated with a shelf life $m\in \mathcal{M} = \{1,\dots,M\}$. We have a periodic review system with stock level $S$, i.e., based on the inventory level of the item,...
- 2,086
3
votes
1
answer
157
views
Modeling that there is no feasible solution to a linear system in mixed integer programming
My question is about how to construct a mixed integer programming to model that there is no feasible solution to a given linear system. Specifically, given $x\in \mathbb{R}^{n}$ and $z\in \{0,1\}^{d}$,...
- 109
6
votes
2
answers
1k
views
0 1 solution of linear programming problem with only equality constraints
I have a linear programming problem $LP$ where all the variables $x_{i}$ take value in $\left[0, 1\right]$ (that is $0\leq x_{i} \leq 1$). All the constraints are as follow: $a_{1}+a_{2}+a_{3}=1$ that ...
0
votes
1
answer
200
views
Assignment problem with variable tasks to be done
I'm dealing with a kind of assignment problem, in which I have a set of tasks $t$ to be executed by machines $w$, but these tasks depend on the variatns $v$ of components $m$ being selected, which is ...
- 1,133
3
votes
1
answer
217
views
How can I linearise this nonlinear proportional relation constraint?
My optimisation problem has a constraint in the form
\begin{equation}
\begin{array}{*{35}{l}}
\text{}\hspace{16.5mm}\text{ C4:} \hspace{2mm}\sum_{u=1}^U d_{u,1}L_{u}:\sum_{u=1}^U d_{u,2}L_{u}:\cdots:\...
- 2,211