Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
35
questions
31
votes
3
answers
18k
views
In an integer program, how I can force a binary variable to equal 1 if some condition holds?
Suppose we have a binary or continuous variable $x$, a binary variable $y$, and a constant $b$, and we want to enforce a relationship like
If $x \gtreqless b$, then $y = 1$.
How can we write this ...
- 13.1k
12
votes
2
answers
3k
views
In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?
Suppose we have the constraint
$$a_1x_1 + \cdots + a_nx_n \gtreqless b,$$
where $a_i$ and $b$ are constants and $x_i$ are decision variables. Suppose also that we want the constraint to hold if $y=1$ (...
- 13.1k
10
votes
1
answer
3k
views
What are good reference books for introduction to operations research?
The reference books should cover the wide range of problem-solving techniques and methods.
19
votes
6
answers
7k
views
When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs
Various optimization modeling languages and solvers allow for both indicator constraints (see for example here, here and here) and traditional binary variable and big-M approaches can be used to model ...
- 193
9
votes
3
answers
979
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
29
votes
3
answers
7k
views
What is the difference between integer programming and constraint programming?
At first glance both approaches appear to be very similar.
What are the major differences between integer programming and constraint programming?
- 2,013
14
votes
2
answers
1k
views
How to choose between high number of binary variables or fewer number of integer (not only 0 and 1) variables in a IP formulation?
When I have to write the formulation of an IP, I usually have the choice between writing $i\times j$ binary variables with two indices such as $ x_{i,j} $ or, writing $j$ integer variables $x_i$.
Is ...
- 151
15
votes
1
answer
1k
views
What is quadratization?
In the context of discrete optimization, what exactly does it mean to "quadratize" a function?
The term seems to be used mainly by operations researchers, in my experience.
- 1,268
12
votes
2
answers
627
views
Expressing a chain of boolean ORs using ILP
How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables ...
- 897
5
votes
2
answers
553
views
Linear and Integer programming materials
I was wondering if you could refer me to some online video/text resources to learn linear and integer programming. I am intending to work in the field of data science. I greatly appreciate your kind ...
- 67
29
votes
3
answers
1k
views
Feeding known lower bounds to solvers
Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all feasible solutions, and your solver of choice:
For what theoretical and/or practical ...
- 1,006
11
votes
1
answer
485
views
Expressing a chain of boolean ORs using ILP involving different variables
How can I express a chain of OR operations in an ILP, given that each operand is an inequality between two binary variables? I have asked a similar question here: Chain of Boolean ORs. In that ...
- 897
8
votes
1
answer
2k
views
How to linearize the multiplication of an integer and a binary integer variable?
I have the following constraints
\begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align}
where $x_i\ge 0$ is an integer variable, $t_i\in\{0,1\}$ is a binary variable ...
- 2,211
7
votes
1
answer
664
views
When using docplex.cp is it possible to get all feasible solutions?
I would like to solve an ILP and get all feasible solutions (even the worst one).
How could I do that using docplex.cp?
I've seen a similar question in: Using CPLEX "solution pool" to count ...
- 1,133
6
votes
1
answer
688
views
Linearize a product of an integer variable (not just binary) and a continuous variable?
I have a constraint in my formulation that contains multiplication of an integer variable $y$ and a continuous variable $x$, which is $xy=q$ where $y$ is the number of units in which $q$ gets equally ...
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
20
votes
1
answer
2k
views
What's the difference between Lagrangian relaxation and Lagrangian decomposition?
What is the difference between Lagrangian relaxation and Lagrangian decomposition? Are they the same thing?
- 13.1k
14
votes
4
answers
654
views
Does this $0-1$ integer program have any speciality?
Given matrix $A \in \{0,1\}^{m \times n}$ and vector $b \in (\mathbb{Z^+})^m$, where $\mathbb{Z^+}$ is the set of positive integers,
$$\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject ...
- 243
13
votes
3
answers
1k
views
Allocating credit card points
I’m interested in the idea behind this in general, so I thought this would be the best place to post, though I have a practical and semi-urgent need of allocating the points on my credit card towards ...
- 233
12
votes
2
answers
610
views
Expressing an implication as ILP where each implication term comprises a chain of boolean ORs
Consider an implication of the form $A \implies B$ where both $A, B$ comprises a chain of Boolean OR variables. For example, $(a_1 \lor a_2 \lor a_3) \implies (b_1 \lor b_2 \lor b_3)$. How can this ...
- 897
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
10
votes
2
answers
1k
views
Decision Variable Value from a Set (Gurobi)
Is there a way to set a decision variable to take values from a set?
Example:
decision variable $x \in \{0,50,100\}$
So this variable can only take one of these three values and not more.
I have ...
- 1,193
9
votes
2
answers
526
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
7
votes
1
answer
868
views
How to find the idle intervals in integer programming?
I have a scheduling problem with one machine and one job. I defined a binary variable $z_t$ that is 1 iff the job is scheduled at time $t$ (the job can be served in multiple times that are not ...
- 381
6
votes
2
answers
425
views
Linear objective function with non-linear constraints
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
407
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
4
votes
2
answers
525
views
Formulating the conditional constraint
I want to develop a model extension of capacitated location problem.
The variables are a binary $x_i$ and a continuous $Q_i$. The following condition must be satisfied:
if $x_i = 0$, $Q_i$ must be ...
3
votes
1
answer
389
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
3
votes
2
answers
123
views
Modelling a data-sensitivity scenario as an ILP problem
I am new to linear programming, and I recently came across the following exercise, which I do not know how to solve:
When publishing data, it is sometimes important to "suppress" sensitive ...
user4156
2
votes
2
answers
101
views
Is there a name for this type of integer programming?
Let $x_i$ be a decision variable, and let $c_i$ be the coefficient for the decision variable $x_i$.
An integer programming problem is where the goal is to:
$\text{maximize} \quad \sum_i c_ix_i$
$\text{...
- 133
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, \\
...
2
votes
2
answers
1k
views
2
votes
1
answer
49
views
Finding bounds on a data sensitivity scenario ILP problem
This is a follow up to a problem I posted here: Modelling a data-sensitivity scenario as an ILP problem
As a recap, I was interested in finding the minimum number of cells that need to be suppressed ...
user4156
1
vote
0
answers
121
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
0
votes
0
answers
199
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,208