# Questions tagged [integer-programming]

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

376 questions
Filter by
Sorted by
Tagged with
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
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: ...
1 vote
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
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
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
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 ...
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 ...
55 views

### How to access optimal solution pool?

I have the following code for a staff scheduling model: ...
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
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
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
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
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 ...
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 ...
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
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
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,...
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 ...
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 ...
1 vote
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
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
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
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$...
64 views

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 ...
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 ...
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 ...
93 views

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
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
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
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
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
34 views

• 917
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 ...
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
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: ...
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 ...
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
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 ...