Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
339
questions
1
vote
1
answer
151
views
Modeling Multi-Agent Collision in Google CP-SAT Solver
I would like to implement a solution for Multi-Agent Pathfinding Problem using Google's CP-SAT Solver.
How do I implement the constraint that prohibits 2 or more agents from occupying the same cell at ...
- 325
2
votes
2
answers
403
views
How to model Max-Cut as ILP
I want to model Max-Cut in IBM's CPLEX, but I fail at modeling the objective function.
My attempt is to use is to sum the XOR of inclusion for vertices of each edge, as exactly then an edge is ...
- 131
1
vote
2
answers
235
views
Google CP-SAT Infeasible ILP for Large Problem Area
I am trying to generate a shortest path between source and sink in a square grid of cells. I am using the Google CP-SAT solver ...
- 325
2
votes
0
answers
67
views
Good encoding for grid layout problem
How would you encode the problem given by https://oeis.org/A337663 with an off-the-shelf solver?
You need to lay out $n$ ones and $2, 3, ..., m$ on an infinite grid, for $m$ as large as possible. For ...
- 232
2
votes
1
answer
359
views
Is it possible to merge two objective functions using the LpSolve package in R?
I have been using the LpSolve package to solve a minimization problem in my final course work, but I need to reconcile this problem with a maximization problem. Conducting several researches, I ...
1
vote
1
answer
146
views
How to model this problem?
I have recently tasked with a problem in which I have to locate electric vehicle charging points (new) keeping in mind that there continue to exist older charging points. The problem is to model the ...
- 139
4
votes
2
answers
589
views
Modeling an either-or-constraint
We would like to model a constraint for an assignment problem that dictates that either assign a specific subset of nodes $I\subset\mathcal{I}$ to a specific subset of nodes $J\subset\mathcal{J}$, or ...
user9659
4
votes
2
answers
1k
views
How can we write a binary variable as a power to a constant number?
Let $x_{i,j}$ be a two-dimensional binary variable.
Is it possible to write $x_{i,j}$ as a power to a number?
For example:
$$1- 0.3^{x_{i,j}} $$
- 307
2
votes
3
answers
360
views
How to formulate if-then for two sums in an integer program
I have two sets of Boolean variables, $x_1, \dots, x_n$ and $y_1, \dots, y_m$ and a positive integer $b$. I would like to add the constraint:
$$\text{If }\sum_i x_i = b \text{ then }\sum_i y_i > b$...
- 131
0
votes
2
answers
153
views
On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope
Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid A x \leq b\}$ is integer, while $A$ is ...
- 119
6
votes
1
answer
133
views
Modulo Integer Programming, $m$ equations $n$ variables
I am following 'Application of Number Theory to Numerical Analysis', and there is a section by G.H. Bradley called 'Modulo Optimization Problems and Integer Linear Programming'. There he explains that ...
- 421
3
votes
2
answers
307
views
Activate Binary if specific pairs of binaries equal 2
I have a problem formulation with binary variables x1,x2,x3,...
- 743
2
votes
3
answers
153
views
Warm starting ideas for iteratively solving a model with a few additional constraints
I'm trying to solve a MILP model iteratively, and at each iteration a few constraints are added to the problem that cut off the previous optimal solution. I'm trying to figure out ways to implement a ...
- 29
3
votes
1
answer
283
views
Meaning of infeasible model: unsuccessful solving for an IP model with binary variables
For fun, I have modeled the Union-closed sets conjecture for a universe of a given size into a problem with binary variables.
Each binary variable $x_k$ is the indicator of the set with elements ...
- 393
2
votes
1
answer
93
views
Load to ship assignment problem
Problem
We’d like to optimize the delivery of loads across a network using a fleet of ships. Assume there is a set of $\mathcal{S}$ ships that need to deliver the set of $\mathcal{L}$ loads in a ...
- 129
7
votes
2
answers
508
views
I ran a relaxed MIP and got some integer results; how can I constrain MIP to match those integers?
Suppose I run a relaxation of an MIP. If my result is all integers, I have achieved the same min/max that the MIP would achieve. However, what can I say if some portion of my result is integer?
If ...
- 892
0
votes
2
answers
107
views
What kind of problem is this : LP , Multi-objective , other?
I started studying Operations Research (OR) recently and I faced a problem in which I struggled to model it using the traditional LP models. After some attempts, I'm not sure if such a problem is a ...
- 109
0
votes
0
answers
64
views
Decision whether to serve the current table now or skip it
Can the following problem be formulated as a LP/IP problem, where an agent (waiter) that has just arrived at a certain table has to decide whether to visit that table now, or skip the current table ...
- 9
2
votes
1
answer
56
views
Is it possible to change the underlying field from Euclidean to $\mathbb{F}_p$?
I have an ILP $Ax=b$ that I know has feasible solution(s), and I would like to find a/all feasible solution(s). The issue is that $A,x,b$ are defined over $\mathbb{F}_p$. More specifically, I need the ...
- 421
3
votes
1
answer
90
views
Are there examples where introducing clusters of binary variables provides a benefit for solving?
I have a larger model with a large number of binary variables among many others. For the purpose of this question, consider the effect that the binary variables impose on the model to be similar to ...
- 313
3
votes
1
answer
142
views
LP Objective function for distributing workload
In this example, we have a group of students that each needs to be paired with a teacher. Each student has a different number of questions to ask the teacher, and each student-teacher pairing has a ...
- 243
1
vote
0
answers
82
views
Bipartite matching
If I have two matrix
$$A = \begin{bmatrix}
1 & 2 \\
2 & 3
\end{bmatrix} $$ and $$B = \begin{bmatrix}
3 & 4 \\
5 & 3
\end{bmatrix} $$
We have to make a matching between $A$ and $B$ ...
- 139
5
votes
1
answer
282
views
Writing a specific MILP problem
I would like to choose a set of $\beta_j$s that maximizes a simple linear objective function of the type
$$
\underset{\beta_j}{\operatorname{max}}\sum_{j=1}^{J}X_j\beta_j \\
$$
subject to the ...
- 215
4
votes
1
answer
159
views
Can we reformulate a min-max nonlinear integer programming problem with the same optimal solution?
I'm trying to solve the below min-max nonlinear integer programming problem with the following objective functions:
$$\min_{x_i,y_i} \max_i \left\{\frac{x_i}{2+3y_i} + \frac{2x_i}{4+7y_i}\right\} \\ \...
6
votes
1
answer
257
views
Binary decision variable to indicate whether a continous decision variable is equal to its upper bound
Given a continuous nonnegative decision variable $x\in [0,T]$ bounded by $T$, how can we enforce a relation between $x$ and another binary decision variable $y$ such that when $x$ is equal to its ...
- 147
4
votes
1
answer
153
views
Binary decision variable to indicate whether an inequality is satisfied or not
I have a problem where I have a continuous decision variable (let's call it $m$) that is bounded between $(0, T]$ where $T>0$ is a predefined parameter. I also have another binary decision variable ...
- 147
-5
votes
1
answer
246
views
How to make Gurobi solve huge LP/IP model with only using A,b,c matrices?
I work on the scaling of MIP. I have scaled the A,b,c matrices of the huge original model. These matrices have more than 25000 rows and columns. I need to make Gurobi solve the scaled model. Normally, ...
- 105
2
votes
1
answer
56
views
How does a ratio of fixed cost to variable cost affect the problem difficulty?
I am working on an OR scheduling problem where OR opening cost is considered a fixed cost when a surgery is scheduled. If OR is used beyond a certain time, overtime cost is incurred.
I would like to ...
- 331
11
votes
5
answers
2k
views
How to compute all paths between two given nodes in a network?
In this post, Erwin Kalvelagen describes a method to compute all paths between two nodes in a given network, such that:
no arc is used more than once
a given path does not contain more than $M$ arcs
...
- 12.9k
3
votes
2
answers
519
views
How to formulate and solve a variant of the Cutting Stock Problem
I should mention up front that I'm new to this forum and operations research in general. A problem has come up recently at work that I'm having a tough time solving.
Our machine shop acquires many ...
- 33
3
votes
1
answer
70
views
How to optimize two partitions at the same time under non linear constraints?
Let :
$G$ be a undirected graph with nodes $a_1, \ldots, a_n$
$x_1, \ldots, x_m$ a set of real values
$\epsilon > 0$
Var the variance function
$d$ the "distance" between sets : $d(X_1, ...
- 93
1
vote
1
answer
153
views
Taking derivatives of objective function with a binary variable to find minimum
I transform my minimization problem into one with only an objective function (no constraints). I only have one variable, which is binary.
Can I derivate the objective and make it equal to 0 to find ...
- 507
5
votes
2
answers
335
views
Assembly line balancing: What does machine precedence mean?
I am looking at the looking at the following classical integer programming model for assembly line balancing:
R.R.Vemuganti's "Applications of Set Covering, Set Packing and Set Partitioning ...
- 193
2
votes
1
answer
69
views
Ensure that scheduled repeating maintenance has to be completed
I'm trying to model the scheduling of maintenance in some machines, and was wondering how I could ensure that, if maintenance is planned to start in period $t$, then it has to be carried out until ...
- 516
4
votes
1
answer
398
views
Minimum up time for a machine in a linear program?
If we let $x_i$ = 1 if a machine is on during hour $i$, and 0 if the machine is off, how would we enforce a constraint that requires the machine to be “on” for a minimum of at least $M$ hours?
For ...
- 495
6
votes
1
answer
359
views
Binary variable switch constraints
I have a set of binary variables $X = \{ x_1, x_2, x_3, ... x_N \}$ which are connect and used with the rest of the model.
I want to define a set of binary variables which represents the change ...
- 63
6
votes
2
answers
774
views
Confusion Between Different Types of Optimization Problems
I do not have a background in optimization and I am trying to teach myself more about this topic. I find myself having a lot of trouble understanding the different "types" of optimization ...
- 1,821
5
votes
2
answers
1k
views
Is Traveling Salesman Problem "Combinatorial Optimization" or "Integer Optimization"?
I am looking at the Traveling Salesman Problem and I can not figure out if this problem is a type of "Integer Optimization Problem", or is a type of "Combinatorial Optimization Problem&...
- 1,821
6
votes
2
answers
504
views
Integer Programming Constraints - Min/Max Days Between Deliveries
I'm starting a consulting project for a client who manufacturers perishable food. They want to optimize their delivery schedule to each of their DSD (Direct Store Delivery) customers.
For each store, ...
- 743
4
votes
1
answer
183
views
How do you know if Column Generation is any faster than standard MIP formulations?
I'm currently in the process of learning about column generation, so I apologize in advance if I show a gross lack of understanding about it.
Anyways, what I've gathered so far is that Column ...
4
votes
1
answer
127
views
Exploiting ordering to removing infeasible solutions in MILP
I kindly ask for some ideas or references to exploit ordering in MILPs.
In particular, there are resources $ r = [r_1, r_2, ..., r_K] $ such that $r_{i} \leq r_{i+1} $. These are input to the problem.
...
- 303
-3
votes
1
answer
98
views
Modelling constraint
I have the following problem statement:
A company is considering to hire more operators. Starting with four machine operators
in May, the company wants to investigate if it pays off to hire more. Each ...
- 5
3
votes
1
answer
113
views
Dichotomic search for biobjective linear program, max flow problem for hospital patients
I recently asked this question about formulating a max flow diagram for hospital patients. I am now considering a secondary objective which is to maximize the effetiveness of the scheduled treatment. ...
- 67
3
votes
1
answer
3k
views
Complicated constraint with logical operators in PuLP
I have an optimization problem that I am trying to solve with PuLP.
All the variables are Booleans.
The variables that are "selected" will be true, all others false.
Objective function is ...
- 33
2
votes
0
answers
52
views
How to construct a restriction for a blending problem that has 2 inputs that are blended, and as result we get 2 outputs?
THE PROBLEM
A refinery has 10 million barrels of type A crude and 6 million barrels of
Type B crude oil. The refinery has 3 plants to produce Gasoline (it makes a profit
of 2 USD / barrel) and Naphtha ...
- 67
3
votes
1
answer
387
views
How to construct the linear programing representation of a blending problem?
THE PROBLEM
A refinery has 10 million barrels of type A crude and 6 million barrels of
Type B crude oil. The refinery has 3 plants to produce gasoline (it produces a profit
of 2 USD / barrel) and ...
- 67
4
votes
1
answer
319
views
Adding a group constraint to binary decision variables
I have a problem where I have N binary decision variables where each one of them belongs to a group (Where the number of groups G is less than N) and I have to choose a subset of them to maximize some ...
- 147
2
votes
1
answer
154
views
Is this integer optimization problem still NP?
I have the following integer optimization problem
\begin{align}\min&\quad\sum_ix_i\\
\text{s.t.}&\quad Ax \geq b\\
&\quad x \geq 0,\\
&\quad x \in \mathbb{Z}^n\end{align} where
$b$ is ...
- 129
3
votes
1
answer
67
views
Maximizing the number of nonnegative coordinates of $Wx$
I want to find good incumbent solutions to the following problem:
$\newcommand{\RR}{\mathbb{R}}$
$\newcommand{\norm}[1]{\left\Vert#1\right\Vert}$
Given a matrix $W \in \RR^{m \times n}$, find the ...
- 133
6
votes
2
answers
308
views
Multi-commodity Network Flow: Convert a node-arc solution to an arc-path solution
For a logistics optimization problem I am working on, the most natural expression of the problem is using a node-arc formulation of the MCNF. It is solved using an LP/MIP solver like CPLEX/Gurobi.
...
- 119