# Questions tagged [integer-programming]

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

371 questions
Filter by
Sorted by
Tagged with
52 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 ...
32 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 ...
48 views

### How to access optimal solution pool?

I have the following code for a staff scheduling model: ...
75 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 ...
119 views

### Rearrange 'x' piles of items into eight possible locations/bins based on item color and length

I have an optimization problem that I believe is a variant of the 'bin packing problem with precedence', but I'm unsure of if that is the correct paradigm to work with and I'm not having a huge amount ...
169 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 ...
202 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 ...
76 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
71 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 \...
92 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 ...
117 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 ...
1 vote
124 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. ...
149 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 ...
1 vote
139 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 ...
1 vote
88 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 ...
1 vote
99 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 ...
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,...
92 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 ...
2k views

### What's the name of a finite-capacity bin packing problem trying to minimize the weight of the heaviest bin?

I have a fixed number of bins which are themselves weightless. Each bin can hold only a fixed amount of weight. Not all bins have the same capacity. I also have a fixed number of objects each of which ...
1 vote
227 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 ...
73 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
68 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 ...
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$...
60 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 ...
369 views

### Family of hard instances for Gomory's cutting plane algorithm

Is there a variant of integer programs for which Gomory's cutting plane algorithm demonstrably takes a superpolynomial number of iterations?
98 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 ...
244 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 ...
75 views

328 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 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'...
81 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 ...
1 vote
125 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}$ ...