Questions tagged [integer-programming]

Questions on optimization constrained to integer variables.

Filter by
Sorted by
Tagged with
0 votes
0 answers
8 views

Outer approximation algorithm for non-convex integer nonlinear program

Consider a particular non-convex binary nonlinear problem of the following form: $$ \min_X f(X) \\ \text{s.t. } X = (x_1, \ldots, x_L)^T \in \{0, 1\}^{L \times V } \\ \sum_{j=1}^V X_{ij} = \sum_{j=1}...
Jacques's user avatar
  • 23
-4 votes
1 answer
24 views

If Then statement changed to equation [closed]

I have a issue with making a equation out of this if-then statement: If they watch at least 2 movies out of 24, 34, and 77, then they must not watch movie 27. Premise is I can only watch 20 out of the ...
Edward Yo's user avatar
1 vote
1 answer
24 views
+100

Does total unimodularity for this modified assignement problem still preserve?

For a job assignment problem, total unimodularity would guarantee that the solution from a relaxed problem will be the same as the original integer problem. In my case, the data matrix is given and ...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
57 views

Does this binary integer problem has any special structure that can be exploit?

I am an electrical engineer and currently I am learning some optimization for my research work. Note that this is a follow up question from my previous question at this link. My project requires me to ...
Tuong Nguyen Minh's user avatar
1 vote
0 answers
45 views

How to extract a connected tree of nodes from undirected graph with certain attributes?

I am working on a problem where I need to extract a connected tree of nodes based on certain attributes while optimizing for the minimum number of nodes. Some attributes of the nodes are known in ...
bsha's user avatar
  • 41
0 votes
1 answer
33 views

Operations research | Employee availability problem

So I have a problem with school and I am not sure if it is a employee schedueling problem, here is the situation: We have to minimize the amount of employees at a non profit organization(Sanquin) and ...
Thijssie3032's user avatar
2 votes
1 answer
50 views

Largest integer value of $z=x\times{}y$ given $0<x\leq{}a$, $0<y\leq{}b$, and $z\leq{}c$

What would be an efficient algorithm to find largest value of $z=x\times{}y$ given $0<x\leq{}a$, $0<y\leq{}b$, and $z\leq{}c$, where $a$, $b$, $c$, $x$, $y$, and $z$ are all positive integers? ...
jblood94's user avatar
  • 306
0 votes
0 answers
63 views

Does the following inequality hold when $x_i \geq 1 $?

Does the following inequality hold when $x_i \geq 1$ for $i=1,2..k$ and $\sum_{i=1}^k x_i = n$? $n^2 \sum_{i=1}^k x_i^3 \leq (\sum_{i=1}^k x_i^2)^3$ I observed this while reading an article that this ...
Tiramisu's user avatar
  • 345
0 votes
0 answers
19 views

optimal choice between another unit of expensive and more valuable product or cheaper but less valuable product

I have little knowledge of Operations Research so any directions to reading material book/online will be welcomed lets say that product A have price $p_A$, value(benefit) $v_A$ and we have number of ...
quester's user avatar
  • 607
1 vote
0 answers
17 views

Determining max number of clients a person can have on their caseload based on their schedule & client frequency

I'm not sure if it's possible, and to be clear math is not my strong suit (assume I only know basic high school math, and a handful of excel functions). I'm a therapist supervisor, and I've been given ...
user avatar
1 vote
1 answer
37 views

Indicator function with multiple conditions in optimization

I have the following problem $$\begin{align*} & \min \ f(X) \newline & X = \begin{cases} 1&; x_1 \leq c_1, x_2 \leq c_2, x_3 \leq c_3, \newline 0&; \text{otherwise}. \end{cases} \...
Cherryblossoms's user avatar
-1 votes
1 answer
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 ...
E-O's user avatar
  • 75
0 votes
1 answer
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 ...
Tuong Nguyen Minh's user avatar
2 votes
1 answer
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 ...
E-O's user avatar
  • 75
1 vote
1 answer
38 views

Is this a valid Integer Linear Programming formulation for the minimum vertex colouring problem?

The problem is such that a 2 vertices which are connected by an arc, must have different colours. Is the following a valid ILP formulation? $$ \min\sum_{i=1}^{n} x_i $$ $$ A^Tx = 2 ​$$ $$ x_i \in \{...
Gabe's user avatar
  • 15
1 vote
4 answers
161 views

Find combinations of 3 values that add to final value

So I only took math up to high school level and a bit during uni, but I do code a lot and can figure out a lot of algorithms and formulas to get what I want, but this stumped me... I never had to ...
ItsKazBorn's user avatar
0 votes
1 answer
65 views

Placing numbers of 1-9 so that the six equations hold

Place the numbers 1 to 9 into the nine positions in such a way that, the 6 equations are valid. Each position must have a distinct value. Multiplication and division have priority over addition and ...
Oytunxxx's user avatar
4 votes
1 answer
138 views

Solving a system like $\lfloor x / a_i \rfloor = b_i \pmod M$

Suppose I have a system of equations like this: \begin{cases} \lfloor x / 100 \rfloor = 4 \pmod 8 \\ \lfloor x / 101 \rfloor = 2 \pmod 8 \\ \lfloor x / 105 \rfloor = 3 \pmod 8 \\ \lfloor x / 106 \...
Lynn's user avatar
  • 3,248
0 votes
0 answers
18 views

Linear vs Quadratic integer programming on the example spread vs variance

I consider the following two instances of the same problem, computing the spread as the difference of the highest and lowest occurrence of something in a set. Further, I compute the variance of the ...
baxbear's user avatar
  • 233
1 vote
1 answer
44 views

Linearizing SOS1

Guys, I am trying to find ways of linearizing the operator Special Ordered Set Type 1 (SOS1). In order to understand what is my goal, I will, firstly, describe the problem I am facing. Let's consider ...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
68 views

Optimization of Dynamic Warehouse Delivery

I have an optimization problem for the delivery of boxes between warehouse and production lines within a small facility. I need to determine how many transport vehicles and utilities to buy, such that ...
user18463824's user avatar
0 votes
1 answer
34 views

How to apply integer cut to a simple MILP?

I'm self-studying on cutting plane methods, and I'm reviewing the following problem from Bertsimas' book (see below). I know what cutting plane methods do, and how they eliminate infeasible solutions ...
somewhere's user avatar
1 vote
1 answer
33 views

Constraint formulation with binary variables if-then

I am working on an optimization problem which has the following constraint: Let $x_{j}, y_{j}$, $j=1, \ldots, J$ be a set of binary variables, it holds that, for $j', j'' \in J$ fixed, if $$\sum_{j' &...
user326159's user avatar
  • 2,669
2 votes
0 answers
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 ...
edamondo's user avatar
  • 1,187
1 vote
0 answers
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 ...
Shujun Tan's user avatar
2 votes
1 answer
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 ...
Ronald's user avatar
  • 61
3 votes
1 answer
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 ...
Ronald's user avatar
  • 61
1 vote
1 answer
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 ...
Tam Nguyen's user avatar
2 votes
1 answer
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 ...
qwr's user avatar
  • 10.5k
2 votes
1 answer
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\}, \...
Proper Illumination's user avatar
1 vote
0 answers
16 views

How to find lattice vector with minimal projection along given vector?

Suppose I have a Construction A lattice $$\mathcal{L} = \left\{\left[G |2\mathbb{I}_n\right]z\ :\ z\in\mathbb{Z}^{n+k} \right\}$$ where $G$ is a $n\times k$ matrix generating a binary linear code and $...
frrz's user avatar
  • 51
1 vote
2 answers
66 views

Greedy solution for a variant of complete Knapsack problem

I'm dealing with a variant of the Knapsack problem: Given $n$ distinct types of items, each with a value $v_i$ and weight $w_i$ (both being positive integers), we can select an infinite number of each ...
maplemaple's user avatar
  • 1,135
0 votes
0 answers
31 views

Determining all monic integer polynomials with real zeros in given intervals

For a given integer $n\geq1$ and a bounded interval $I\subset(1,\infty)$ the goal is to determine all monic polynomials $P\in\mathbb{Z}[X]$ of degree $n$ with $n-1$ zeros in the interval $(0,1)$ and ...
SmileyCraft's user avatar
  • 6,647
0 votes
0 answers
43 views

Mathematical Reasoning for Solving Integer Programming

For an integer programming problem, I found that using the integer programming function intlinprog in matlab (based on branch and bound) is the same as using simple mathematical reasoning. For the ...
Cathy's user avatar
  • 1
0 votes
0 answers
16 views

Show that the relaxation of the clique formulation for the simple circular interval packing problem does not always describe the integer hull.

Today I have found this problem that really intrigues me while studying for an optimization exam: Show that the relaxation of the clique formulation for the simple circular interval packing problem ...
luna's user avatar
  • 43
3 votes
0 answers
79 views

Subset sum problem with $F_m^2 F_n^2$ (Fibonacci square) weights

Suppose $$N = \sum_{i=1}^{k} \sum_{j=1}^{k} x_i \cdot y_j\cdot F_{c_i}^2 \cdot F_{c_j}^2 ; (x_i, y_j, c_i, c_j \in \mathbb{Z}, c_i, c_j \ge 1) \tag{1}$$ and $F_k$ is the $k$-th Fibonacci number. The ...
vvg's user avatar
  • 3,205
1 vote
0 answers
34 views

What is the name of this type of network flow problem?

I encountered a specific type of network flow problem, and I want to know if this type of problem has already been studied before. However, I have been unable to find relevant literature because I don'...
Bosnicht's user avatar
1 vote
1 answer
42 views

Condition of constraint in BILP

I have a set of $n$ activities $a_i \in A$. Each activity $a_i$ has a set of child activities $C_i \subset A$, an associated cost $k_i$, and a start time $t_i$. In the BILP model I use, I consider a ...
E-O's user avatar
  • 75
0 votes
0 answers
40 views

basis of monoid of integral vectors

Suppose that $M\in\mathbb{Z}^{n\times k}$ is a matrix of rank $k<n$. How can I obtain a set of vectors $b_1,\ldots,b_k\in\mathbb{Z}^k$ (if exists) such that each row of $M$ is a non-negative ...
Brauer Suzuki's user avatar
0 votes
1 answer
231 views

An integer quadratic optimization problem

Suppose that $m \ge 1$ is a given positive integer, and $n \ge 1$ is a given even integer. Let $R$ be the set of vectors $\vec{r} = (r_1, r_2, \cdots, r_n)$ such that every coordinate $r_i$ is a non-...
Matthew Kahle's user avatar
1 vote
2 answers
70 views

Max condition in Integer programming and MILP

Assume you have 2 binary variables $b$ and $c$. Suppose you want another binary variable, $a$ to be $\max(b,c)$ always. How would you represent this in the constraints of an integer program or of a ...
Anonymous Bunny's user avatar
1 vote
1 answer
60 views

Integer programming cuttings plane: code to find and explain strong cuts

My question has to do with integer programming and having a code that helps a researcher derive cutting planes. Has anyone written some code, potentially interactive, to generate and explain cutting ...
Robert Hildebrand's user avatar
1 vote
1 answer
65 views

When do two integer linear programs yield the same solution?

This question was cross-posted to operations research 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$ ...
user's user avatar
  • 199
1 vote
1 answer
31 views

Minimizing maximum distance for integer case

I am working with different facility location models giving its single (only one center help a demand zone) and multi-source models (multiple centers can help a demand zone). My decision variables are ...
Noah's user avatar
  • 169
1 vote
1 answer
33 views

Modeling AND of implication in integer/binary linear programming

Problem statement Let $\beta \in \{0, 1\}$ for brevity. A set of $K$ numbers $M_k$, represented as individual bits $B_{ik} \in β $, must be distributed to a set of $ J \le K$ pairs $F_j = (c_{ij} \in ...
Astrinus's user avatar
  • 131
0 votes
1 answer
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=...
Rosalyne Kruzchka's user avatar
0 votes
2 answers
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 ...
manofthousandnames's user avatar
0 votes
1 answer
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 ...
manofthousandnames's user avatar
1 vote
2 answers
116 views

Problem with case distinction in a programming problem

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 ...
themaneater22's user avatar
0 votes
1 answer
70 views

ILP constraints for connectivity in a matrix

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 ...
Amanli's user avatar
  • 11

1
2 3 4 5
22