# Questions tagged [integer-programming]

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

157 questions
Filter by
Sorted by
Tagged with
527 views

### Feeding known lower bounds to solvers

Given an optimization problem that aims at minimizing some objective function, a lower bound that is valid for all optimal solutions, and your solver of choice: For what theoretical and/or practical (...
5k views

### In an integer program, how I can force a binary variable to equal 1 if some condition holds?

Suppose we have a binary or continuous variable $x$, a binary variable $y$, and a constant $b$, and we want to enforce a relationship like If $x \gtreqless b$, then $y = 1$. How can we write this ...
3k views

### What is the difference between integer programming and constraint programming?

At first glance both approaches appear to be very similar. What are the major differences between integer programming and constraint programming?
587 views

### What's the difference between Lagrangian relaxation and Lagrangian decomposition?

What is the difference between Lagrangian relaxation and Lagrangian decomposition? Are they the same thing?
263 views

### Combinatorial Optimization: Metaheuristics, CP, IP — “versus” or “and”?

"Recently" someone asked on Twitter whether "people still use genetic algorithms for integer programs". The "majority answer", i.e., 1 out of 1, was: "Yes" . So, my follow-up question is: With all ...
3k views

### When to use indicator constraints versus big-M approaches in solving (mixed-)integer programs

Various optimization modeling languages and solvers allow for both indicator constraints (see for example here, here and here) and traditional binary variable and big-M approaches can be used to model ...
807 views

### Variable fixing based on a good feasible solution

Suppose you have a combinatorial optimization problem that is formulated as a mixed integer linear program (minimization). The problem size is denoted $n$ and the expected $n$ is around $100$. The ...
2k views

### Can an integer optimization problem be convex?

I'm trying to wrap my head around an apparent paradox that I've come across while trying to learn more about optimization algorithms: On one hand several sources state that convex optimization is ...
208 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?
2k views

### Does there exist an aggregation of videos on optimization?

Is there a website or otherwise maintained list of talks regarding mathematical optimization? This would be a big help for the community it seems. I'm most interested in those relating to integer ...
1k views

### How does the search space affect the speed of an ILP solver?

Let us suppose we have an optimization problem which we have modeled as an ILP. Suppose we solve this problem using some set of constraints which restricts the search space. Let us suppose we model ...
718 views

### Divisibility constraints in integer programming

In the study of a certain pure mathematical problem (related to infinite-dimensional Lie algebras) I found myself in a situation where it would be very desirable to be able to solve an integer ...
553 views

### Duality in mixed integer linear programs

I know that the standard duality theory for the linear programming problem does not hold for mixed integer linear programming problems. I was wondering why an integer program does not have a dual ...
278 views

167 views

462 views

### Finding an optimal set without forbidden subsets

Given $n$ items, I want to select a set items $S\subseteq\{1,2,\dots,n\}$ that maximize profit. The profit of item $i\in\{1,2,\dots,n\}$ is given by $p_i$ and may be assumed to be non-negative. ...
227 views

### Generalized Assignment Problem as the sub-problem

I was wondering what is the state-of-the-art for solving the Generalized Assignment Problem (GAP) and if there are special cases that are polynomially solvable? Moreover, is there any usage of this ...
285 views

### Expressing a chain of boolean ORs using ILP involving different variables

How can I express a chain of OR operations in an ILP, given that each operand is an inequality between two binary variables? I have asked a similar question here: Chain of Boolean ORs. In that ...
191 views

### Is deciding the presence of mixed-integer points in the relative interior of a polyhedron in NP?

Given $P = \{x\in\mathbb R^n: Ax \leq b\}$, I want to decide if $(\mathbb Z^\ell \times \mathbb R^{n-\ell}) \cap \operatorname{relint}(P)$ is non-empty. Is this problem in NP? One idea is to check ...
96 views

### Computational complexity to compute an IIS

How hard is it to compute an irreducible infeasible subset (IIS) for a linear program? What about an integer program (e.g., removing the integrality constraint on a single variable may be enough to ...
2k views

377 views

### Are there explainability approaches in optimization?

In the machine learning community there is the big topic of explainability, where you want to make the solution of ML models explainable or derive explainable models. This is also interesting for ...
857 views

### Decision Variable Value from a Set (Gurobi)

Is there a way to set a decision variable to take values from a set? Example: decision variable $x \in \{0,50,100\}$ So this variable can only take one of these three values and not more. I have ...
111 views

### MIP: If integer variable $>0$ it should be equal to other integer variables $>0$

I have an MIP problem where $n$ different types of cars are delivering packages. Sometimes multiple types of cars are required to go to a single location. For example if car $1$ makes two deliveries ...
143 views

### Theoretical results on performance of branch-and-bound

Are there any theoretical results on the performance of branch-and-bound, even for a subset of instances of a particular discrete optimization problem? As an example, does there exist a result of ...
171 views

### Finding the linear functions defining a polyhedron through integer data?

Let's say I have a bunch of linear functions $f_1,\cdots,f_n$ in $k$ variables; then $f_1,\cdots, f_n\le0$ defines a polyhedron $P$ in the $k$-dimensional space. What I'm looking for is going the ...
185 views

### Use integer/quadratic programming to maximize consecutive zeros in a binary array

A binary array $t = [t_1, t_2, t_3, t_4, t_5]$ with each element a binary integer variable taking values 0 or 1. You can think this vector as slots with 1 representing the slot being taken and 0 ...
432 views

### TSP problem: traveller does not visit all nodes - Google OR-tools

Context: I am dealing with a kind of scheduling problem, in which I have a set of tasks and machines. All tasks must be assigned to machines (not necessary all of them). In addition to that, I must ...
407 views

### How to maximize “contrast” between nodes on a graph?

I have an undirected graph such as the one shown below. I can make up to 3 choices about the color of each node. The edge weights are equal to the difference between the nodes, given by the "...
213 views

### How to get bounds on ILP optimal solution quality

Often, ILP formulations are just too complicated to solve optimally in reasonable time. In those cases, you can still run a solver for some fixed time and simply take the best solution that the solver ...
214 views

### Should I factor in time as a parameter or a variable in a scheduling problem with MILP?

I am trying to formulate a problem that will spit out an optimal schedule for my tasks to be completed. To keep the information confidential, I will refer to my tasks as papers that need to be written....
114 views

160 views

### Static stochastic knapsack problem: unbounded version

In the static stochastic knapsack problem (SSKP) the weights $w_i$ of the items are distributed according to a probability distribution. Each item $i \in I$ can be selected at most once. So, ...
74 views

### What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
2k views

### Why is there not a feasible solution for a MIP?

Is there a way to see why a solver (OR-Tools, CPLEX, Gurobi) cannot find a feasible solution when solving a MIP? By that I mean, is there a possibility to show at which constraint and exact indices ...
313 views

### Understanding integer programming solvers

I would like to verify if I understand the nature or workings of integer programming solvers. My understanding is that for integer programming problems like the knapsack problem or the traveling ...
1k views

### How to formulate problems in the language of mathematical programming?

The question says it all. I am having difficulties formulating general problems (meaning no numbers just variables). When I read the solution, I understand but I can't figure how to formulate myself ...
1k views

### Open source MILP solver for quick “good enough” solution

I have a problem that I have already posted elsewhere in OR.stack, but the question is focused around a large binary MILP (about 1 million decision variables). Ultimately, I am more time constrained ...
318 views

### When using docplex.cp is it possible to get all feasible solutions?

I would like to solve an ILP and get all feasible solutions (even the worst one). How could I do that using docplex.cp? I've seen a similar question in: Using CPLEX "solution pool" to count ...
I have the following constraints \begin{align}\sum_{i=1}^{N}{x_it_i}&= M\\\sum_{i=1}^{N}{t_i}&\le S\end{align} where $x_i\ge 0$ is an integer variable, $t_i\in\{0,1\}$ is a binary variable ...