Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
335
questions
0
votes
2
answers
13
views
How to identify constraints that make problem not solvable in polynomial time?
I am reading this paper, available for free viewing, which contains an example of job shop scheduling, shown below.
The details of the variable definitions, etc., can be found in the paper, but it's ...
1
vote
0
answers
63
views
Optimize cherry picking runs
I am trying to optimize a cherry picking procedure on 96-well microplates. The plates are 12X8 (12 columns, 8 rows). We pass a command file that has many lines like this to a robot:
...
- 111
3
votes
0
answers
35
views
Does Robust Optimization consider uncertain discrete parameters?
I'm aware of many techniques for Robust Optimization, such as the interval method, and those mentioned here: https://arxiv.org/pdf/1501.02634.pdf.
But all of the techniques I've seen are for when the ...
- 31
1
vote
2
answers
136
views
Linearizing if else conditions in ILP
We are given three binary indicator variables $X_{ij}, Y_{jk}$ and $Z_{jl}$. Write linear constraints such that,
a) if $X_{ij}$ is equal to 1, then for that $j$ when $X_{ij} = 1$, exactly one $Y_{jk} =...
- 897
3
votes
2
answers
213
views
Binary Integer Programming Problem - Enforce Zeros on Certain Groups
I'm working on a binary integer programming problem using pulp. I have a vector X = [x_1, x_2, x_3, . . . , x_n]. I have enforced a number of simple constraints. I ...
- 33
7
votes
3
answers
727
views
Binary logical constraint dependent on indices
I don't know if I can ask this here, but I've been pulling my hair out trying to think of how to represent this in constraints.
I have two sets of binary variables: $X_t$ and $Y_{it}$. So, I want to ...
- 507
-1
votes
2
answers
176
views
How do I optimize this problem where the constraints and objective are variable?
Problem Definition:
Pa = Constant
Pb = Constant
Vmax_a = Constant
Vmax_b = constant
Objective Function:
...
2
votes
0
answers
29
views
Maximizing value of nodes visited in fixed time
Consider the following three problems. The first is intended to be a simplification of the second that might be amenable to solution methods the second is not amenable to.
First problem: Assume we ...
3
votes
1
answer
186
views
Graph coloring problem redundant constraints
Say the edges of a 4 nodes graph are 0 1, 1 2 and 1 3.
The solution to the colouring problem ...
- 133
1
vote
1
answer
98
views
Constraints to avoid disjointed solutions in a MIP
Given an directed graph $G= (N,E)$, where $N$ is the set of nodes and $E$ is the set of all edges, each associated with a direction. $G$ is a connected graph but not necessarily a complete graph.
A ...
- 71
0
votes
2
answers
53
views
ILP constraint conditional on a value of a variable
If $X_{ijklm}$ are Boolean Variables, where $i,j,k,l,m$ range from $1$ to $n$, then write an ILP constraint to ensure that for each value of $k$, either all the $jth$ variables are set to $0$ or all ...
- 897
1
vote
2
answers
112
views
Efficient ways to do pairwise/multiplicative variables in integer linear programming on PuLP / Python
I'm trying to formulate an LP that is in essence a variant of the sudoku problem, and I've repurposed the code from https://coin-or.github.io/pulp/CaseStudies/a_sudoku_problem.html.
The differences ...
- 21
1
vote
1
answer
66
views
Setting constant values in constraints depending on actual values of variables
We have a set of constraints in an ILP of the following form :
$ \gamma (X_{11} + X_{12} + X_{13}) \leq C_1$ where $X_{ij} \in \{0,1\}$ and the value of $\gamma$ is going to depend on the actual value ...
- 897
2
votes
0
answers
74
views
When do two integer linear programs yield the same solution?
This question is cross-posted from math stack exchange
An illustrative example
Consider an integer linear program $\min -2x_1 + x_2$ subject to $x_1 - x_2 \leq 3$ and $x_1 + x_2 \leq 10$ and integer $...
- 121
2
votes
1
answer
119
views
Conditional constraints in MILPs
I want to understand how to represent iff constraints in MILPs. For example, I want to represent the following as the constraints of a MILP
$$ c = \begin{cases} 1 &\text{if } d \geq e \\ 0 & \...
-1
votes
1
answer
50
views
does mTSP/CVRP always minimize number of vehicles used?
Context:
I was working on some VRP solvers and realized that tractability deproved when I added Fixed Cost for each vehicle (in an attempt to reduce number of vehicles used).
Questions:
1-
Due to the ...
- 63
0
votes
2
answers
98
views
Assignment problem with multiple precedence constraints
Objective and short problem description
The objective is to load as many passenger vehicles as possible on an auto-train. The train consists of multiple wagons with two levels each. The wagons are ...
1
vote
1
answer
104
views
Anytime solver for integer linear program
One approach to solving NP-hard problems is to use an anytime algorithm: an algorithnm that starts with a heuristic solution and keeps improving it towards the optimum, and when it is stopped, it ...
0
votes
1
answer
70
views
Simulating an integer quadratic knapsack problem
I am trying to simulate the following quadratic integer program using $\textsf{cvxpy}$:
$$ \begin{array}{ll} \underset {x_1, \dots, x_K} {\text{minimize}} & \displaystyle\sum\limits_{i=1}^{K}\frac{...
- 103
3
votes
2
answers
380
views
How to model a binary variable?
I am trying to find a constraint for the following relationship, but am failing a bit at it right now. I want to find a linear constraint that does the following. The binary variable $switch_{ot}$ is ...
- 31
1
vote
1
answer
108
views
Rational LP, its Rational solution and a minimum precision
Suppose we have an LP with rational coefficients.
To my knowledge, this implies that the optimal solution to that LP is also rational. In other words, every variable may be written as:
$$x_{i}^{\star} ...
- 143
0
votes
0
answers
53
views
How do I solve this non-linear optimisation problem based on simulations?
I have an optimisation problem that is essentially a knapsack problem with a non-linear objective.
I have an input dataframe that contains a row for each item, each item has columns defining its mean ...
- 31
0
votes
1
answer
151
views
How to formulate an MIP so that a binary variable is 0 or 1 depending on whether another variable is nonzero?
I have a binary indicator variable $i \in \{ 0, 1 \}$ and an integer variable $c \in \mathbb{Z}$.
I am trying to come up with a formulation in which $i = 0$ if $c = 0$ and $i = 1$ if $c \neq 0$.
...
- 153
3
votes
0
answers
89
views
Number of Subtour Elimination Constraints for ATSP (DFJ Formulation)
In the DFJ formulation of the symmetric TSP, the subtour elimination constraints are typically written as:
$$\sum_{\{i,j\} \in E: \ i \in S, j \notin S} x_{ij} \geq 2, \qquad \forall S \subset V, \; 3 ...
- 31
0
votes
4
answers
108
views
What is the greatest possible number of tables that could be occupied by just 1 person?
A restaurant has a total of 16 tables, each of which can seat a maximum of 4 people. If 50 people were sitting at the tables in the restaurant, with no tables empty, what is the greatest possible ...
- 121
0
votes
3
answers
46
views
Maintaining Pair Preference that is neutral at outset
I am trying to model a job-shop scenario where - given a certain number of workers (W) and parts (P) such that P>W - each worker spends each shift (k) working on a specific part. Due to reasons of ...
3
votes
2
answers
353
views
How to model this binary constraint?
I have an optimization problem that has a variable in the matrix form. The variable is a binary matrix. It has size $M \times N = 10 \times 50$ where $M$ is the number of machines and $N$ is the ...
3
votes
3
answers
235
views
Equivalence between constraints in ILP
Let's have binary variables $x$ and $y$. I'd like to define a helping binary variable $z$ such that
$$ z = 1 \; \;\; \mathrm{iff} \; \; \; x + y = 2.$$
If I wanted to express the equivalence between ...
- 133
1
vote
1
answer
66
views
how to minimize the distance to the final points with incomplete information?
Suppose we have a transportation problem similar to pickup and delivery problems. So, we have a set of drivers and a set of passengers. each passenger has predefined origins and destinations. I'd ...
- 177
2
votes
3
answers
148
views
Is there any "not bad" algorithm that can solve the minimax problem in 0/1 integer programming?
As title, recently I got a minimax problem, after formalizing, the model is like this.
$$\text{minimise } \max_{k \in K} \sum_{i \in I} b_{i,k} \cdot f_i$$
such that: $$ \forall i \in I,\, \sum_{k \in ...
- 23
1
vote
2
answers
68
views
How to tackle online scheduling problems?
In scheduling problems, one usually has different options as objective functions (makespan, tardiness, etc). However, for any such type of scheduling problem one can consider an online version of it ...
- 199
1
vote
2
answers
68
views
Fixing binary variables in an Binary Integer Program
I have a Binary Integer Program with two binary decision variables and additionally have an expected solution. At the time of execution of this program I expect the parameters to change slightly. I am ...
- 392
1
vote
1
answer
109
views
Solver for Flexible Job Shop Scheduling Problem
I have a FJSSP that I would like to solve. However, the jobs in this problem have deadlines and in addition there are setup times between two jobs. Because of this, my objective function is not just ...
- 199
0
votes
1
answer
63
views
Maximization problem with preferences on variables
Consider the following trivial, theoretical model:
$$
\max x+2y+3z \qquad s.t.
$$
$$
x \leq b_x
$$
$$
y \leq b_y
$$
$$
z \leq b_z
$$
$$
x+y+z = 1
$$
$$
x,y,z \in \{0, 1\}
$$
and $b_x$, $b_y$ and $b_z$ ...
- 927
2
votes
1
answer
137
views
Reduced cost fixing for binary programs
Consider the binary program
$$ \min_{ x \in \{0,1\}^N } \left\{ c^T x \mid Ax \leq b \right\}$$
where $A$ and $b$ are real matrices with appropriate dimensions. I am interested in solving large binary ...
- 66
2
votes
0
answers
34
views
Recoverable Robustness for an optimization problem
I am relatively new to the concept of recoverable robustness. I am researching the robust version of an optimization problem. I currently have methods to address the problem with perfect knowledge. ...
- 392
1
vote
1
answer
242
views
multi-commodity flow vs integer programming
A theater center needs to select which shows to broadcast in one of its rooms for a given day. There are three options available: short films that last about 1 hour, movies that last about 2 hours, ...
- 123
0
votes
0
answers
56
views
Gamma uncertainty in the RHS of a constraint
I am new to the concept of robust optimization.I am trying to formulate the robust variation of a Binary Integer Program. Suppose we have a constraint of the form $\sum{x_{i,j}} \geq b_j$ for $ i \in ...
- 392
5
votes
6
answers
2k
views
How can I solve this algorithmic task in Python?
I am trying to solve this task:
There are three datasets: first data on offices in cities: each city has a certain number of offices and each office has its own capacity of employees. Second, data on ...
- 61
5
votes
2
answers
484
views
Minimize worker variance assignment problem
I have a problem, which is similar to Assignment Problem, described as follows:
The problem instance has a number of workers and a number of tasks. Any task can only be assigned to a subset of the ...
- 153
3
votes
1
answer
466
views
Of what size should I expect to be able to solve an integer linear program with Pyomo?
So I am solving a purely integer linear optimization problem with Pyomo on a single computer (core i-5, 12 GB RAM). The problem has around 10000 variables and 300 constraints. For doing this, I am ...
- 199
5
votes
1
answer
258
views
Optimize selection of metal sheets to keep in stock
I already asked this on stack overflow but just found this forum instead and figured it was more suited here. If this isn't allowed please feel free to tell me and I'll delete the post.
I am doing ...
- 53
3
votes
2
answers
451
views
Binary integer programming with dynamic costs and total resource constraint
I am trying to find a suitable paradigm under which my discrete optimisation problem falls into. This looks similar to integer programming, so the goal is to find a binary vector $\bar{x}$. However, ...
- 133
5
votes
3
answers
386
views
Is this arc routing formulation correct?
Let $G=(V,E)$ be a graph. I would like to identify an eulerian cycle in $G$ with minimum cost, with an integer programing approach:
$x_{ij}$ are integer variables that denote the number of times that ...
- 51
1
vote
2
answers
154
views
How do I model a precedence constraint?
How do I model a precedence constraint of 12 tasks distributed among 4 work stations in order to balance the line to obtain the shortest possible cycle time?
...
- 21
1
vote
0
answers
96
views
Assembly Line Balancing---(Minimizing Cycle Time)
A factory has a four workstations assembly line which produces a bluetooth speaker. This
production requires twelve assembly operations, respecting some precedence constraints. Table
4 indicates the ...
- 21
4
votes
1
answer
352
views
Can sensitivity analysis and limits report be done on an BILP problem?
I am not that experienced with Operations Research yet. I have become familiar with what Sensitivity Analysis and Limits Reports are in general and through the use of Excel.
I know that they can only ...
- 205
1
vote
2
answers
225
views
Capacitated Maximum Coverage Location Problem, Python and Gurobi
I am trying to solve a capacitated MCLP problem with two additional constraints.
Non-overlapping circles
Minimum and Maximum value for the capacity for a circle.
for 2nd constraint, I am able to add ...
- 13
1
vote
1
answer
170
views
How to write this logical expression with Gurobi + Java, or express it as a big-m formulation
I am trying to write the following expression in Gurobi+Java or Gurobi+python, if it is more practical It could be expressed as a big-M formulation.
\begin{equation} \label{const4}
\text{D}_{uv} =
...
- 11
2
votes
4
answers
390
views
How to approach this shifts problem with Excel Solver?
I am trying to find a way to solve the following problem of mine by using Solver but I get stuck right at the end of it.
I have a table of 14 companies each of which want to work on a project. I will ...
- 205