Skip to main content

Questions tagged [integer-programming]

Questions on optimization constrained to integer variables.

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

Characterizing the Result of Lift and Project Method for Integer Programming

I have the following integer linear programming problem: Let $P=\{x\in \mathbb{R}^n\colon Ax\geq b\}\subseteq [0,1]^n$ be a polytope. For a fixed index $j\in [n]$, consider the polyhedron $P^j$ ...
Choripán Con Pebre's user avatar
1 vote
1 answer
63 views

Chvatal-Gomory integer rounding method to find facets of $\operatorname{conv}(S)$

The question: "given a set $S = \{x \in \mathbb{Z}^2 : 4x_1 + x_2 ≤ 28, x_1 + 4x_2 ≤ 27, x_1 − x_2 ≤ 1, x ≥ 0 \}$. we are tasked with deriving each facet of $\operatorname{conv}(S)$ as a Chvatal-...
alex's user avatar
  • 13
0 votes
0 answers
26 views

Existence of a basis of lattice with successive minima norms

Is there an easy way to show that given a lattice $\Lambda \subset \mathbb{R}^n$ of full rank, exists a basis where each vector has norm $\lambda_i$ i.e the i-th successive minima ($\lambda_i(\Lambda)=...
jacopoburelli's user avatar
0 votes
1 answer
31 views

A variant of the partition problem or subset sum problem

Given a target list $T = (t_1, t_2, \ldots, t_N)$ and a multiset $S = \{s_1, s_2, \ldots, s_M\}$, both with non-negative integer elements, $t_k\in \mathbb{N}_>$ and $s_k\in \mathbb{N}_>$, ...
daysofsnow's user avatar
0 votes
1 answer
46 views

Why should Branch&Bound not terminate if the relaxation is an unbounded LP?

In my homework assignment there is a task which wants you to show that for specific integer programs Branch&Bound could run forever. One could just choose the relaxation of the IP to be some kind ...
Sen90's user avatar
  • 453
1 vote
1 answer
90 views

What is the computational complexity of generalized Long Live the Queen?

Consider the following model of computation: The computer's memory consists of $n$ registers denoted $r_1, ..., r_n$, each holding an integer. In the following, an affine combination means an ...
Naomi Zhang's user avatar
3 votes
1 answer
46 views

Can you find a linear system with these integer solutions?

I have this expression $(x \geq 1) \vee(x=0 \,\wedge\, y -z \geq 1)$ which I am solving over the nonnegative integers $x,y,z \in \mathbb{Z}_0^+$. I suspect it is impossible to find a system of linear ...
user326210's user avatar
  • 17.7k
1 vote
1 answer
37 views

Question about a property of the integer-hull

If I have a convex set $Q\subseteq \mathbb{R}^n$ and a cone $E\subseteq \mathbb{R}^n$. Let $Q_I = conv\{Q \cap \mathbb{Z}^n\}$ and $E_I$ respectively. Is it in general the case that $Q_I + E_I \...
Sen90's user avatar
  • 453
0 votes
1 answer
43 views

Correctly understand the implication of approximation ratio for the set cover problem?

I am currently reading this wikipedia article about the set cover problem and it said here that "it cannot be approximated to $\left[ {1 - o\left( 1 \right)} \right]\ln \left( n \right)$ unless $...
Tuong Nguyen Minh's user avatar
1 vote
1 answer
53 views

Is it possible or practical to just solve integer optimization problem by penalizing?

I am an engineer who is currently working in network optimization problem. I have finised my master degree a long time ago. During my studies I have learnt about the penalty technique to turn a ...
Tuong Nguyen Minh's user avatar
2 votes
2 answers
37 views

Explanation of multiple constraints from one rule [closed]

I'm trying to understand this case study: https://github.com/DorisRipley/Art-Exhibition-Optimization-A-BIP-Modeling-Approach/blob/main/Art%20Exhibition%20Optimization.pdf and I'm having trouble with ...
Sergio Morales's user avatar
0 votes
1 answer
45 views

How to write constraints for an indicator function such that if x = 0 then y = 1, and otherwise y = 0?

Currently working on an optimization problem using pyomo. One constraint I need to make is to limit the number of times a situation occurs - Essentially when my variable x = 0. So I would like an ...
Bahumat's user avatar
0 votes
3 answers
103 views

Minimizing linear function with constrains on coefficients

Question: I am faced with minimizing a specific sum: $$ \sum_{i=1}^{L} a_i x_i $$ $L$, $x_i$ and $K$ are given. So the question is reduced to choosing proper $a$. Constrains on $a$: $a_1$ = 1. $a_i = ...
Umbra's user avatar
  • 55
0 votes
0 answers
41 views

Will Branch and Bound always terminate after finite iterations?

I learnt this algorithm by a simple example illustrating the essential ideas of it without analyzing in details. So my questions are Will BB always end after finite iterations? (Both for binary cases ...
Andrew_Ren's user avatar
3 votes
0 answers
47 views

Reference Request: Vertex Enumeration Algorithms That Finds All Integer Points in a Polytope

For fun, I explored vertex enumeration algorithms for linear programs to find all feasible extreme points in a polytope. Naturally, I asked, "Do there exist algorithms that solve for all integer ...
Miss Mae's user avatar
  • 1,939
1 vote
0 answers
97 views

Integer programming problem, with complicated cost function

I need to find the vector $\hat{n}=[n_1 \; n_2 \; \cdots \; n_N]$, all integers,such that $1\leq n_i \leq Z$, $\forall i$ (with $Z$ also integer) that minimizes the following function: $F=\frac{1}{N}\...
Garbt's user avatar
  • 89
1 vote
1 answer
28 views

Integer Linear Programming - Dividing n people into m groups of specific sizes

I've recently asked this question about dividing n people into m groups for the specific model I used to solve the assignment problem of dividing the people into groups (boolean variables xij that ...
Zufra's user avatar
  • 197
1 vote
1 answer
19 views

Searching for an optimal multiple + offset decomposition.

Let us assume I have a sequence of numbers $\{n_1,n_2\cdots, n_k\}$ which I want to approximate / represent like so: $$\hat n_i = a_i x + b_i :,\\ a_i \in \mathbb Z^+,b_i\in \mathbb Z\\\text{so that}\\...
mathreadler's user avatar
  • 26.1k
2 votes
1 answer
61 views

Integer Linear Programming - Dividing n people into m groups

I have modeled the problem of dividing n people into m groups using a binary $nxn$ matrix that we will call X. If $x_{ij} = 1$ it means that person i is with person j in the solution's groups. If $x_{...
Zufra's user avatar
  • 197
0 votes
0 answers
41 views

Does Cutting Plane method always converge in case of Integer Linear Programming?

I learned that the Cutting plane algorithm using Gromory's cut helps in finally reaching an optimum solution in integer linear programming. But I also observed that in the simplex tableau, if the ...
Vinny Dek's user avatar
  • 156
1 vote
1 answer
78 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
3 votes
1 answer
231 views

Largest smallest integer solution

I have the following system of equations, for $i$ in $1,\ldots,n$: $$ \mathbf{a_i} \cdot \mathbf{x} = y $$ The variables are $\mathbf{x}$ - a vector of $n$ non-negative integers, and $y$ - a positive ...
Erel Segal-Halevi's user avatar
0 votes
0 answers
15 views

Are there any theorems about the existence of feasible solutions to the Mixed-Integer Nonlinear Programming (MINLP) problem?

I am just wondering if there are any theorems about the existence of feasible solutions to the Mixed-Integer Nonlinear Programming (MINLP) problem. For example: Theorems about sufficient conditions ...
Shujun Tan's user avatar
6 votes
1 answer
92 views

What was the gap in Ariane Papke's proof that the minimum number of sudoku clues is 17?

I was reading McGuire's paper on why the minimum number of clues in a Sudoku puzzle is 17 when I came across a curious comment: In 2008, a 17-year-old girl submitted a proof of the nonexistence of a ...
Fateh A.'s user avatar
  • 425
3 votes
1 answer
43 views

Does there exist other integer models that contain an exponential number of branches thats not knapsack for the branch-and-bound method?

During a class assignment, I was presented with the following question: Provide an integer program that has an exponential number of branches...(expunged excess) ...
Miss Mae's user avatar
  • 1,939
0 votes
0 answers
78 views

Gram Schmidt swapping two vectors of the basis

I'm trying to understand how the LLL algorithm works and I've stumbled upon the following question: Suppose I have $B = (b_1,\cdots,b_n)$ vectors and I perform Gram Schmidt process obtaining $(v_{1},\...
jacopoburelli's user avatar
0 votes
0 answers
54 views

Number of Patterns in Cutting Stock Problem Grows Exponentially

Consider the cutting stock problem where $L$ is the length of the stock and $n$ is the total number of patterns. If customer demands are any length between $1, 2, \ldots, L$, why is it the case that $...
Anfänger's user avatar
  • 593
1 vote
0 answers
79 views

"Factorization" of the solutions set of a system of linear diophantine equations over non-negative integers

Suppose we have a system of linear diophantine equations over non-negative integers: $$ \left\lbrace\begin{aligned} &Ax=b\\ &x\in \mathbb{Z}^n_{\geq0} \end{aligned}\right. $$ where $A$ is a ...
Alexander's user avatar
0 votes
1 answer
66 views

Linear programming constraint involving maximum

I am trying to formulate a much bigger problem as an integer linear program, but I am stuck with one particular constraint and am not sure how to formulate it. To put it shortly, the problem deals ...
AlaskaYoung's user avatar
0 votes
0 answers
82 views

Dual of LP representation of graph coloring

I have found a representation of the graph coloring problem as an ILP. Given a graph $G = (V, E)$. Let $C$ represent the set of colors. Let $w_c$ be a binary variable that is $1$ if the color $c$ is ...
mNugget's user avatar
  • 511
0 votes
1 answer
62 views

Does finding feasible solution to set cover problem is as hard as SAT problem?

I have a weird feeling that finding a single feasible solution to the set cover problem is as hard as SAT problem. I think that this might be wrong but I am not sure why. To illustrate my thinking, ...
Tuong Nguyen Minh's user avatar
2 votes
0 answers
73 views

Bin packing : item to be packed in a certain bin depend on previously packed items to that bin.

I am working on an engineering problem. I need to implement an algorithm that looks like a certain variant of bin packing. Specifically, in this variant of the bin packing, the size of a certain item ...
Mazen Ezzeddine's user avatar
2 votes
1 answer
107 views

Complexity of solving systems of linear inequalities with two variables per inequality with additional constraints

Consider a system $X$ of linear inequalities containing at most two variables. In the general case, finding a solution over $\mathbb{R}\cap[0,1]$ can be done deterministically in polynomial time due ...
Daniil Kozhemiachenko's user avatar
0 votes
1 answer
105 views

Nonnegative integer solutions, when nonnegative solutions exist and integer solutions exist

I have a set of vectors $v_i$, $1\leq i\leq N$ for some $N$ over the real numbers that are not linearly independent. We will express them as natural-number-valued functions from some integer interval $...
Matt Samuel's user avatar
  • 58.4k
1 vote
1 answer
65 views

Solving an SAT problem with objective

I have 8192 bits, denoted $b_0, b_1, ..., b_{8191}$. The bits are subject to some XOR constraints (e.g. $b_0 \oplus b_3 \oplus b_{42} \oplus \cdots \oplus b_{8191} = 1$). The objective function to be ...
nalzok's user avatar
  • 836
2 votes
0 answers
39 views

Integer points in a closed polyhedron nearest an extreme point

This is a revision of my previous question. The question is motivated by the fact that, for a Linear Program (LP) obtained by relaxing a given Integer Linear Program (ILP), an optimal solution may be ...
avs's user avatar
  • 6,322
1 vote
1 answer
68 views

Formulation of an integer linear programming problem

I want to formulate the following problem in an integer linear programming problem: We have $n$ elements $m_1,\dots, m_n$ elements with $m_i = (m_i^1, \dots, m_i^p) \in \mathbb{R}_{\geq 0}^p$ for all $...
Ferdi 17's user avatar
1 vote
0 answers
37 views

Integer lattice points in a closed convex polyhedron and close to the polyhedron's extreme points

In the 2-D Euclidean space, the angle formed by the intersection of two closed half-spaces, $H_{1}, H_{2}$, with outer normals $\hat{n}_{1}, \hat{n}_{2}$ can be measured as obtuse or acute. It is ...
avs's user avatar
  • 6,322
0 votes
0 answers
28 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
1 vote
1 answer
95 views

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
61 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
58 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
43 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
54 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
  • 316
0 votes
0 answers
24 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
  • 617
1 vote
0 answers
26 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
66 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
114 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
  • 99
0 votes
1 answer
73 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
33 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
  • 99

1
2 3 4 5
23