Questions tagged [integer-programming]

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

Filter by
Sorted by
Tagged with
6
votes
2answers
185 views

A heuristic approach to solve a MILP problem?

I have the following optimization problem which is a MILP. I can solve it with a MILP solver. This one I posted here Is there a heuristic approach to the MILP problem? Since I have an additional but ...
10
votes
1answer
416 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 ...
8
votes
1answer
290 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 ...
8
votes
1answer
546 views

How to linearize the multiplication of an integer and a binary integer variable?

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 ...
15
votes
1answer
532 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 ...
5
votes
2answers
339 views

How to establish constraint between variables with multiple indexes using CPLEX in Python

I am new in CPLEX and I am using docplex in Python to solve an ILP. I would like to translate the following constraint in docplex: $$\sum_{c}(X_p{_w}_{cj}+X_{p+1}{_{w'}}_{cj+1})\leqslant T_w{_{w'}}_{,...
6
votes
0answers
114 views

Help in solving resource allocation optimization problem

I've been pondering on this question for some work optimization, and I need some help in being directed to the right direction. I have multiple customers that require an amount of $X$, $Y$ and $Z$ ...
14
votes
4answers
260 views

Does this $0-1$ integer program have any speciality?

Given matrix $A \in \{0,1\}^{m \times n}$ and vector $b \in (\mathbb{Z^+})^m$, where $\mathbb{Z^+}$ is the set of positive integers, $$\begin{array}{ll} \text{maximize} & c^\top x\\ \text{subject ...
17
votes
3answers
753 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 ...
9
votes
1answer
213 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....
10
votes
3answers
138 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 ...
10
votes
1answer
167 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 ...
11
votes
2answers
221 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 ...
10
votes
2answers
803 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 ...
17
votes
3answers
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 ...
8
votes
4answers
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 ...
12
votes
3answers
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 ...
15
votes
3answers
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 ...
12
votes
2answers
324 views

Expressing an implication as ILP where each implication term comprises a chain of boolean ORs

Consider an implication of the form $A \implies B$ where both $A, B$ comprises a chain of Boolean OR variables. For example, $(a_1 \lor a_2 \lor a_3) \implies (b_1 \lor b_2 \lor b_3)$. How can this ...
6
votes
1answer
132 views

Obtaining the intermediate solutions in AMPL

I know that for some solvers, for example, the constraint programming solver in Google OR-Tools, it is possible to see all the intermediate solutions that the solver finds while it searches for an ...
15
votes
2answers
633 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 ...
11
votes
1answer
268 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 ...
5
votes
2answers
395 views

Linear and Integer programming materials

I was wondering if you could refer me to some online video/text resources to learn linear and integer programming. I am intending to work in the field of data science. I greatly appreciate your kind ...
12
votes
2answers
482 views

Expressing a chain of boolean ORs using ILP

How to express a chain of OR operations in an ILP in which each expression is a less than or equal constraint and the left hand side variable in all inequalities is always the same? All the variables ...
5
votes
2answers
276 views

Bridge the gap between theory and practice in Integer Programming

I've finished Wolsey's book on Integer programming. It's a theoretic book. I aim to learn how the ideas presented in the book can be applied to solve real-world non-academic problems. I am looking ...
9
votes
1answer
159 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, ...
14
votes
3answers
2k views

A variant of the Multiple Traveling Salesman Problem

I am trying to find a reference (or a reformulation) of a variant of the multiple Traveling Salesman Problem, where multiple agents need to visit each vertex in a graph with minimal cost. Most of the ...
6
votes
1answer
951 views

What are good reference books for introduction to operations research?

The reference books should cover the wide range of problem-solving techniques and methods.
11
votes
2answers
461 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. ...
13
votes
1answer
741 views

What is quadratization?

In the context of discrete optimization, what exactly does it mean to "quadratize" a function? The term seems to be used mainly by operations researchers, in my experience.
11
votes
2answers
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 ...
11
votes
1answer
92 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 ...
17
votes
1answer
201 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?
27
votes
3answers
499 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 (...
12
votes
1answer
117 views

How to reduce recursion when using Gomory cutting planes to solve an integer program?

Consider the following simple integer program $$\begin{array}{ll} \text{maximize} & 3 x_1 - x_2\\ \text{subject to} & 3x_1 - x_2 \leqslant 3 \\ & -5x_1 - 4x_2 \leqslant -10 \\ & ...
18
votes
1answer
489 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?
18
votes
1answer
251 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 ...
17
votes
5answers
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 ...
13
votes
1answer
198 views

Symmetry-breaking ILP constraints for square binary matrix

Setup I have a binary $N \times N$ matrix. The objective is to minimize the number of ones in the matrix, subject to various constraints. This leads to symmetries by rotating 90 degrees and/or ...
22
votes
3answers
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?
9
votes
1answer
200 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 ...
11
votes
2answers
765 views

In an integer program, how can I “activate” a constraint only if a decision variable has a certain value?

Suppose we have the constraint $$a_1x_1 + \cdots + a_nx_n \gtreqless b,$$ where $a_i$ and $b$ are constants and $x_i$ are decision variables. Suppose also that we want the constraint to hold if $y=1$ (...
23
votes
3answers
4k 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 ...

1 2
3