Questions tagged [integer-programming]

For questions about mathematical optimization problems involving binary or general integer variables.

Filter by
Sorted by
Tagged with
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 ...
somewhere's user avatar
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: ...
Ryan's user avatar
  • 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 ...
IsalanOnkar's user avatar
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} =...
ephemeral's user avatar
  • 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 ...
user16668649's user avatar
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 ...
orpanter's user avatar
  • 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: ...
kontrol-c's user avatar
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 ...
Bjørn Westergard's user avatar
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 ...
Dr.PB's user avatar
  • 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 ...
CHE's user avatar
  • 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 ...
ephemeral's user avatar
  • 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 ...
Riezz's user avatar
  • 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 ...
ephemeral's user avatar
  • 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 $...
user's user avatar
  • 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 & \...
Anonymous Bunny's user avatar
-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 ...
Abilash's user avatar
  • 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 ...
Christian's user avatar
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 ...
Erel Segal-Halevi's user avatar
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{...
UserX's user avatar
  • 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 ...
mingabua's user avatar
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} ...
Cris's user avatar
  • 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 ...
will's user avatar
  • 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$. ...
graphtheory123's user avatar
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 ...
user11589's user avatar
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 ...
BornPerson's user avatar
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 ...
StringTypeGroup's user avatar
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 ...
TheExerminate's user avatar
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 ...
tomashauser's user avatar
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 ...
linkho's user avatar
  • 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 ...
Yiichan Sun's user avatar
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 ...
John D's user avatar
  • 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 ...
Pia MiA's user avatar
  • 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 ...
John D's user avatar
  • 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$ ...
Libra's user avatar
  • 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 ...
rolfvdhulst's user avatar
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. ...
Pia MiA's user avatar
  • 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, ...
ebrahimi's user avatar
  • 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 ...
Pia MiA's user avatar
  • 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 ...
Ir8_mind's user avatar
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 ...
YjyJeff's user avatar
  • 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 ...
John D's user avatar
  • 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 ...
guso141's user avatar
  • 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, ...
shiftyscales's user avatar
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 ...
husson's user avatar
  • 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? ...
user11048's user avatar
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 ...
user11048's user avatar
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 ...
Tita's user avatar
  • 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 ...
Nandy's user avatar
  • 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} = ...
Hernan19's user avatar
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 ...
Tita's user avatar
  • 205

1
2 3 4 5
7