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 ...
OR Junior's user avatar
  • 543
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 ...
Ankit Basu's user avatar
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 \...
Joris Kinable's user avatar
2 votes
2 answers
87 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 ...
tr244's user avatar
  • 21
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 ...
Samuel Bismuth's user avatar
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 ...
Maths_hawk's user avatar
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 ...
NormalFit's user avatar
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 ...
Demitri's user avatar
  • 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,...
Jayit Ghosh's user avatar
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 ...
Siazam's user avatar
  • 1
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 ...
occasional's user avatar
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 ...
Erel Segal-Halevi's user avatar
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 &...
Angelo Aliano Filho's user avatar
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 ...
Vv J's user avatar
  • 19
0 votes
2 answers
74 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$...
Srinivasan B's user avatar
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 ...
Robert Snipe's user avatar
4 votes
1 answer
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 ...
graphtheory123's user avatar
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 ...
Elliot Gorokhovsky's user avatar
-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)\...
Uni ewr's user avatar
  • 71
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 ...
Sina_Alef's user avatar
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} \...
lukdooxb1's user avatar
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}$ ...
nalzok's user avatar
  • 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 ...
Hussein Sharadga's user avatar
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 ...
Tom Solberg's user avatar
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 + ...
Tio Pikachu Lizardon's user avatar
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 ...
Erel Segal-Halevi's user avatar
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'...
J. Dionisio's user avatar
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. ...
Jacob's user avatar
  • 111
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 ...
Vivek's user avatar
  • 21
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 ...
Jika's user avatar
  • 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) \...
Matheus Diógenes Andrade's user avatar
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}$ ...
CHE's user avatar
  • 113
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 ...
CHE's user avatar
  • 113
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 ...
somewhere's user avatar
1 vote
0 answers
89 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: ...
Ryan's user avatar
  • 111
1 vote
2 answers
246 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} =...
ephemeral's user avatar
  • 917
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 ...
user16668649's user avatar
7 votes
3 answers
744 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 ...
orpanter's user avatar
  • 517
-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: ...
kontrol-c's user avatar
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 ...
Aldo Leopold's user avatar
3 votes
1 answer
229 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 ...
Dr.PB's user avatar
  • 133
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 ...
CHE's user avatar
  • 113
0 votes
2 answers
78 views

ILP constraint conditional on a value of a variable

If $X_{ijklm}$ are Boolean Variables, where $i,j,k,l,m$ range from $1$ to $n$, then write an ILP constraint to ensure that for each value of $k$, either all the $jth$ variables are set to $0$ or all ...
ephemeral's user avatar
  • 917
1 vote
2 answers
225 views

Efficient ways to do pairwise/multiplicative variables in integer linear programming on PuLP / Python

I'm trying to formulate an LP that is in essence a variant of the sudoku problem, and I've repurposed the code from https://coin-or.github.io/pulp/CaseStudies/a_sudoku_problem.html. The differences ...
Riezz's user avatar
  • 41
1 vote
1 answer
95 views

Setting constant values in constraints depending on actual values of variables

We have a set of constraints in an ILP of the following form : $ \gamma (X_{11} + X_{12} + X_{13}) \leq C_1$ where $X_{ij} \in \{0,1\}$ and the value of $\gamma$ is going to depend on the actual value ...
ephemeral's user avatar
  • 917
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 ...
Jon Knott's user avatar
2 votes
0 answers
77 views

When do two integer linear programs yield the same solution?

This question is cross-posted from math stack exchange An illustrative example Consider an integer linear program $\min -2x_1 + x_2$ subject to $x_1 - x_2 \leq 3$ and $x_1 + x_2 \leq 10$ and integer $...
fool's user avatar
  • 121
2 votes
1 answer
149 views

Conditional constraints in MILPs

I want to understand how to represent iff constraints in MILPs. For example, I want to represent the following as the constraints of a MILP $$ c = \begin{cases} 1 &\text{if } d \geq e \\ 0 & \...
Anonymous Bunny's user avatar
-1 votes
1 answer
68 views

does mTSP/CVRP always minimize number of vehicles used?

Context: I was working on some VRP solvers and realized that tractability deproved when I added Fixed Cost for each vehicle (in an attempt to reduce number of vehicles used). Questions: 1- Due to the ...
Abilash's user avatar
  • 63
0 votes
2 answers
116 views

Assignment problem with multiple precedence constraints

Objective and short problem description The objective is to load as many passenger vehicles as possible on an auto-train. The train consists of multiple wagons with two levels each. The wagons are ...
Christian's user avatar

1
2 3 4 5
8