# Questions tagged [integer-programming]

Questions on optimization constrained to integer variables.

1,081 questions
Filter by
Sorted by
Tagged with
8 views

56 views

### Logical OR in the condition of a linear programming constraint

In a linear programming formulation, I have the following linear constraint: $A_{i,a} x_{i,a} \leq x_{j,b}$ where $x_{i,a}$ and $x_{j,b}$ are binary variables, and $A_{i,a} \in \mathbb{R}^{+}$ is a ...
60 views

### How to linearize or formulate optimization constraints that are stated in terms of "if-then" sentence?

I am a engineer who is working on an optimization problem and my constraints are in the form of this statement "if $x_1=1$ then $d_1=1T$" where $T$ is just a given time period. Scenario 1 ...
24 views

### Summations and constraints over sets in ILP problem

In a simplified version of the ILP problem I am trying to formulate, I have the following: A set of elements $A_{i,j} \in \mathcal{A}$. Each element $A_{i,j} \in \mathcal{A}$ has an associated ...
1 vote
38 views

56 views

### How can an algorithm for traveling salesman beat concorde?

I am trying to learn about neural networks. I was reading the paper An Efficient Graph Convolutional Network Technique for the Travelling Salesman Problem which uses graph neural networks such that ...
1 vote
18 views

### Are there any theorems that can be used to judge if an all-integer programming problem has a feasible solution?

Are there any theorems that can be used to judge if an all-integer programming problem has a feasible solution? I am NOT asking if we have any computational solvers that can be used to find a feasible ...
133 views

### Gomory Cut combined with Duality in Integer Programming

Let's say we apply dual simplex method in the process of doing a gomory cut in integer programming. Is the "algorithm" the same when working with the dual problem? I ask this because we ...
93 views

### What after Gomory Cut in Linear Programming?

After applying Gomory Cut (to remove the non-integer solution) in Linear Programming, I don't really know what to do with the new constraint that I get as a result. I have tried to add the new ...
1 vote
28 views

### Is local optima of QUBO can be feasible to its ILP problem, if the global optima of QUBO isn't feasible to its ILP?

I'm new to optimization and I'm reading a paper that they reformulate an ILP problem into QUBO using penalty method. Let's say we use a solver to solve above QUBO, and the global optima of QUBO ...
248 views

### Counting positive integer linear inequality solutions with constraints

The context is Project Euler #600, counting equiangular hexagons. My approach is to first count solutions without congruence/symmetry and then try Burnside's lemma for congruences. The number of ...
112 views

### Maximum independent set relaxation and its dual

The integer program for the independent set is given by \begin{align*} &\max\sum_{v\in V}x_v\\ &\text{s.b.t } x_u+x_v\leq 1, \text{ for all }\{u,v\}\in E\\ &\quad\quad \ x_v\in\{0,1\}, \...
1 vote
16 views

46 views

### Closed form solution to linear optimization problem

Given integers $m$ and $n$, and a vector $\mathbf{v} \in \mathbb{Z}^n \setminus \{ \mathbf{0}_n \}$,  \begin{array}{ll} \underset {\mathbf{w} \in \mathbb{N}^n} {\text{minimize}} & \sum\limits_{i=...
107 views

### Modelling a shift change

I have the following problem. I am currently modeling shift schedules. There is the variable $x_{itk}$ which tells whether the cashier $i$ completes the shift $k$ on day $t$. Now I want to model the ...
44 views

### Problems to find a suitable formulation for a constraint

I have the following problem. I would like to model the following relationship. I have three binary variables $x_1$, $x_2$ and $x_3$. These become either 0 or 1. I need a constraint for a mathemstical ...
1 vote
Good evening, I have the following problem. I want to create a duty roster and model performance losses. For this I have introduced the binary variable $l_{it}$, which takes the value 1 when the shift ...
I'm trying to use ILP to solve the following problem: A series of connected nodes are provided. For the example below, $a$ is only connected to $b$, $b$ is connected to both $a$ and $c$, $c$ is ...