Questions tagged [integer-programming]
For questions about mathematical optimization problems involving binary or general integer variables.
376
questions
2
votes
1
answer
96
views
Reasonable implementation of a MILP scheduling problem
I have the following (fairly classical) "big-M" formulation of a scheduling problem. I am not able to solve it in reasonable amount of time for instances with more than 20 jobs (I am using ...
- 21
1
vote
1
answer
73
views
Pyomo warmstart does not work with GLPK and CBC
I am trying to warmstart a MIP using Pyomo and a free solver like GLPK or CBC.
Following the documentation it is enough to specify warmstart=True in the following code:
...
- 23
1
vote
1
answer
74
views
CPLEX Working Memory
I have an integer program that is memory intensive. When I solve the problem with defaults the best LP relaxation constantly keeps improving even if the extent of improvement is small. But ...
- 33
0
votes
0
answers
44
views
Probabilistic interpretation of integer linearization solutions
Can we generate approximate integer/binary solutions using pure linear programming?
Suppose that I want to assign $resource_{i}$ to $team_1$ else $team_2$. A solution matrix, M of shape [i,2] could ...
- 559
0
votes
3
answers
132
views
Constraint formulation
Let $P$ be the set of periods, with $y_p$ as a binary variable, and $w_{p}^{t}$ as a binary variable that links period $p$ with period $t$, where $p, t \in P$, and $t = p +2$.
The constraint I am ...
- 113
0
votes
0
answers
63
views
MILP with "unnecessary" continuous variables
This is a theoretical question. I have an integer programming model where I use a series of continuous variables for clarity purposes. These continuous variables are obtained as the product of some ...
2
votes
1
answer
38
views
How to correctly interpret the $\ln(n)$ approximation ratio of the set cover problem under its integer formulation context?
The wikipedia article of the set cover problem stated the following point regarding the inapproximability of the greedy method "When $n$ refers to the size of the universe.... it cannot be ...
2
votes
1
answer
55
views
How to access optimal solution pool?
I have the following code for a staff scheduling model:
...
2
votes
1
answer
185
views
How to increase the lower bound while solving a MILP model?
I have developed an IP model for a combinatorial problem. The model is faster than the other models in the literature. However, for some instances, the model reaches the optimum solution (which I know ...
- 593
0
votes
1
answer
77
views
PULP: Optimization Assignment of Bicycle production per month
Q1. If bicycles of types A and H are produced, then bicycles of type C can be produced with 20% shorter working hours, while selling profit of bicycles type H can be 20% higher.
Q2: If bicycles of ...
1
vote
1
answer
72
views
Lexicographic objective to maximize the x-th highest value
Given the following (stylized) IP:
\begin{align}
\mbox{minimize }& \sum_i c_ix_i&\\
\mbox{s.t. }&\sum_i x_i \leq Q & \\
& f(x_i) \geq L & \forall i \\
& 0 \...
- 3,481
2
votes
2
answers
102
views
Optimizing calls to a separation problem in branch and cut
I have a MIP in which I am able to generate cuts at intermediate relaxation solutions using the context class. These cuts are derived from a separation problem. However, after adding them, the code ...
- 33
3
votes
1
answer
138
views
Restrict the number of non-zero variables to any constant in MILP
I am designing an MILP in which given a set $[n]$ of $n$ agents, we create for each $i \in [n]$ a real variable $x_i$. The variables $x_i$ are between 0 and 1 ($0 \leq x_i < 1$).
I would like to ...
- 303
2
votes
5
answers
249
views
Unable to find good solution for CVRP with Time Window
I am trying to solve Capacitated VRP with Time Window for 50 demand points. I was trying to optimize this in Gurobi Solver but it doesn't give good answer like optimality gap is 30% or more.
Any idea ...
- 23
3
votes
1
answer
193
views
Branch & bound: why does the lower bound increase?
For a minimization problem, when running a branch & bound algorithm, I understand that:
Every integer feasible solution provides an upper bound on the
optimal objective value of the original ...
- 109
1
vote
1
answer
90
views
How to track the first timestep at which a binary variable becomes 1 in an IP? [duplicate]
I have an MIP where I have a binary variable $y_t$ which is set to 1 or 0 and is indexed by time t. It can be set to 1 at multiple timestamps but it is never continuously 1 for more than single ...
- 33
0
votes
0
answers
33
views
Shipment Allocation using Pulp
I am trying to create a model where each shipment must be allocated to a route to minimize the freight cost. I am a complete newbie at LP Optimization.
Explanation of dataset:
Every destination (D1,...
0
votes
1
answer
76
views
Minimize Expenses For Workers
My goal is to minimize the labor expenses. Say we have 3 types of workers:
$x_1$ = Permanent Driver, rate = 693.875/day
$x_2$ = Reliever Drivers rate = 435/day
$x_3$ = Crews rate = 400/day
There are 6 ...
- 1
2
votes
1
answer
94
views
Why this ILP and LP are equivalent?
Let's consider a competition with $n$ questions. Each question has a price $p_i$ and a score $v_i$. To advance to the next round of the competition, we need to accumulate a minimum score of $D$. We ...
- 21
1
vote
1
answer
126
views
A tool for finding integer solutions to linear systems
I have a system of linear equations $A x = 0$, where $A$ is an integer matrix, and I want to find a non-zero solution, if it exists. In that case, a rational solution exists. Multiplying by the common ...
- 1,015
0
votes
0
answers
74
views
Improving the lower bound
Good afternoon.
I have a very difficult to a MIP model. I have tried several different strategies to reduce the gap. I am using Gurobi and in this case, I already have an incumbent solution.
I've set &...
1
vote
1
answer
71
views
Connections between Bounds in MIPs
we are currently learning about MIP/MILP minimization at university and have become familiar with the branch-and-bound algorithm. Unfortunately, the relationship between upper bound, lower bound and ...
- 19
0
votes
2
answers
75
views
How to write a If then else constraint with continuous variables
I have a problem under investigation which requires if, elseif and else conditions to implement as a constraint in a mixed integer program. Any leads will be appreciated. Thanks a lot.
Let $x_t$, $y_t$...
0
votes
0
answers
64
views
Shopping Basket Deal Optimization
I am looking for guidance on a solution to the problem of picking the best special offers that can be applied to a given basket of items.
In the system, a special offer has N collections of qualifying ...
4
votes
1
answer
246
views
Can we add a certain binary row to a matrix which preserves total unimodularity?
Suppose I have a matrix $A\in \{-1, 0, 1\}^{m\times n}$ which is Totally Unimodular (TU), and a vector $b^T \in \{-1, 0, 1\}^{1\times n}$ which has exactly one entry which is $1$ and exactly one entry ...
- 246
2
votes
2
answers
110
views
Small number of constraints, but very large coefficients
I'm looking for advice on solving ILP problems with a relatively small number of constraints and variables, but very large coefficients. I have less than 500 variables and constraints, but my ...
-1
votes
1
answer
93
views
How to linearize a product of an integer and a binary variable
I have this constraint right here, which is not linear. How would I linearize such a product. $number_t$ is a positive integer and $new_t$ and $reset_t$ are binary.
$$number_t = (number_{t-1}+new_t)\...
- 71
2
votes
1
answer
198
views
How to evaluate the quality of a solution obtained using the price-and-branch method for an IP problem?
I have solved an integer programming problem using the price-and-branch (not branch-and-price) approach exactly as same as described in this question and obtained a feasible solution. As this approach ...
- 35
1
vote
1
answer
89
views
Problems with Big-M Constraint
I have the following constraints for my roster optimisation problem:
\begin{align}
&(1-r_{i,t})\le \sum_{j=t-\chi}^{t-1}sc_{i,j}\quad &\forall i\in I, t\in \{1+\chi,\ldots,T\}
\end{align}
\...
- 81
2
votes
1
answer
126
views
Solving a weighted XOR-SAT problem
I want to solve a variant of the weighted XOR-SAT problem. Concretely,
Given $n$ boolean variables $x_1,\ldots,x_n$ each of which is assigned a non-negative cost $c_1,\ldots,c_n\in\mathbb{R}_{\ge 0}$ ...
- 123
1
vote
0
answers
108
views
What is the suitable optimization method for this case?
What is the best optimization method to solve a large-scale problem (about 300 thousand variables)?
The problem is nonlinear, nonconvex, involves only binary variables, and is unconstrained. The ...
- 409
3
votes
0
answers
124
views
Continuous optimization with a Euclidean TSP objective
I am trying to solve a problem of the form $$\min_{x_1,\dots,x_n} f(x_1,\dots,x_n)$$ subject to a constraint that $\mathrm{length}(\mathrm{TSP}(x_1,\dots,x_n))\leq c$, where $x_1,\dots,x_n$ are all ...
- 149
0
votes
2
answers
170
views
Need help with integer programming exercise
This is an exercise from Wolsey that I can't solve. Show how to go from Equivalence (1) to (2) and from Equivalence (2) to (3):
$$
\begin{align}
X &= \{ x \in \{0, 1\}^4~\mid~97x_1 + 32x_2 + ...
4
votes
1
answer
330
views
Optimization problem with the Harmonic number
I have an optimization problem:
\begin{align*}
\text{ minimize } \sum_{i=1}^n H(x_i)
\\
\text{ subject to } Ax \geq b, x\geq 0, x\in \mathbb{Z}^n
\end{align*}
where $H(n)$ is the $n$-th Harmonic ...
- 1,015
1
vote
0
answers
111
views
Applications of Knapsack and Cutting Stock in Pure Math
I'm giving a seminar to PhD students in pure math, and one of the things I'd like to do is show that more applied optimization can also make its way into pure Mathematics. As for classical problems, I'...
- 650
1
vote
1
answer
137
views
Maximizing sum of probabilities with variable distributions
Suppose $\\{X_i\\}$ are binary decision variables and $\\{A_j\\}$ are Skellam random variables with $(\mu_1, \mu_2) = (\sum_i b_{i} X_i, c_j)$. Here, $b_i, c_j \in \mathbb{R}^{\geq 0}$ are constants. ...
- 111
1
vote
1
answer
122
views
Benchmark problems for Benders Decomposition
We are implementing a scheduling model using Benders Decomposition. Does someone know of any existing implementation of Benders or any repositories that contain continuous or integer problems solved ...
- 21
0
votes
2
answers
85
views
What is the best way to constrain a binary matrix so that at most one row has positive values?
I have a binary variable $x_{i,j}$ for $i\in\{1,\ldots,m\}$ and $j\in\{1,\ldots,n\}$ and the constraint is to have at most one row that has ones. I wrote this as: $$x_{i,j}+x_{i',j'}\leqslant1,\forall ...
- 101
0
votes
0
answers
34
views
Stationarity conditions for IPs
Let's consider the following (MQ)IP:
$\min x^T Q x$
s.t. $g(x) \geqslant 0$
$x_i \in \mathbb{Z}$ $i \in I$
By ignoring the integrality constraints we end up with the QP:
$\min x^T Q x$
s.t. $g(x) \...
- 1,240
1
vote
1
answer
129
views
How to linearize the following constraints
Given the following two expressions:
$ x - \frac{1}{T}\sum_{i} y_{i}$
$ x - \frac{1}{Q}\sum_{i} \beta_{i} y_{i}$
where $x \in \mathbb{Z}_{+}$, $y \in \mathbb{R}_{+}$, and $T$, $Q$ and $\beta_{i}$ ...
- 113
1
vote
0
answers
268
views
Deriving a valid inequality
Given a set of facilities $I$ and days $J$, each facility $i \in I$ has a capacity of $C_i$, and a set of days $J$ where in each day $j \in J$ there's a total demand of $q_j$ that can be satisfied by ...
- 113
0
votes
2
answers
246
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 ...
- 11
1
vote
0
answers
90
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
1
vote
2
answers
295
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} =...
- 917
3
votes
2
answers
289
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
747
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 ...
- 517
-1
votes
2
answers
193
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
34
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 ...
- 29
3
votes
1
answer
235
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
164
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 ...
- 113