Skip to main content

Questions tagged [integer-programming]

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

Filter by
Sorted by
Tagged with
2 votes
1 answer
160 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 ...
2 votes
5 answers
180 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 ...
0 votes
1 answer
72 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
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 \...
0 votes
1 answer
63 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 ...
2 votes
1 answer
112 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 ...
2 votes
2 answers
86 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 ...
3 votes
1 answer
104 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
1 answer
123 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. ...
3 votes
1 answer
117 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
1 answer
137 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
1 answer
86 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
1 answer
95 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 ...
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,...
2 votes
1 answer
90 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 ...
7 votes
4 answers
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
1 answer
215 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 ...
0 votes
0 answers
71 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
67 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 ...
0 votes
2 answers
73 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
58 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 ...
17 votes
1 answer
368 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?
2 votes
2 answers
97 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 ...
4 votes
1 answer
243 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 ...
-1 votes
1 answer
70 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)\...
2 votes
1 answer
191 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 ...
1 vote
1 answer
87 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} \...
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 ...
3 votes
3 answers
307 views

Scheduling for the shortest days using ILP

I've tried Or-Tools and MILP solvers a couple of different ways on this, but they take a surprisingly long time to realize that the solution they generated fairly quickly is in fact minimal. Is there ...
2 votes
0 answers
77 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 ...
2 votes
1 answer
113 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}$ ...
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 ...
2 votes
3 answers
193 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 ...
7 votes
1 answer
568 views

CPLEX MIP warm start seems slow down the program?

I have been working on a combinatorial optimization problem which can be modeled as an integer linear programming. I implemented it as a c++ project in visual studio 2017 and CPLEX1271. With the hope ...
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 ...
1 vote
1 answer
118 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 ...
0 votes
2 answers
162 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
326 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
0 answers
110 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'...
0 votes
2 answers
76 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
1 answer
123 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}$ ...
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 vote
0 answers
264 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 ...
0 votes
2 answers
243 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 ...
1 vote
0 answers
88 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: ...
1 vote
2 answers
245 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} =...
3 votes
2 answers
265 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 ...
-1 votes
2 answers
186 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: ...
7 votes
3 answers
743 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 ...
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 ...

1
2 3 4 5
8