Questions tagged [integer-programming]

Integer programming regards optimization problems, where one seeks to find integer values for a set of unknowns, that optimizes the objective function. A common subset of this type of problems are integer linear programming problems, where all inequalities, equalities and the objective function are linear in the unknowns.

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

Showing that one of the inequalities representing a facet is necessary to describe a polyhedron

As stated in Lecture 3 of "Integer optimization" on Page 2, for each facet $F$ of $P$, at least one of the inequalities representing $F$ is necessary in any description of $P$ where $P =\{x \...
0
votes
0answers
63 views

On number of facets in projected polytopes of certain sparseness

$\DeclareMathOperator\Set{Set}$ Let $Set=\{x\in\mathbb Z^{n}:\exists y\in\mathbb Z^m\text{ satisfying } A[x,y]'\leq b\}$ where $A$ has $r=km$ rows and $k=O(1)$. I am trying to write $$ Set=\{x\in\...
1
vote
1answer
80 views

Allowing an “OR” option between equations in a linear program

I am looking for a way to express an "or" option in a system of linear inequalities for a linear program I am working on. I will explain what I mean precisely: Lets say I have a set of ...
0
votes
0answers
14 views

Is it valuable for MIP solves to make redundant variables?

I'm writing an integer programming model, and coming from constraint programming I'm thought to put as much redundancy in as posible. But I'm not sure how much of that logic is correct for MIP. ...
2
votes
0answers
82 views

Complete graph invariant based on integer programming?

Roughly speaking, we are trying to find complete graph invariant as the lexicographically first matrix from the permutations of the adjacency matrix. Let $G$ be graph, possibly directed graph, of ...
0
votes
0answers
53 views

Solutions to matrix equations in the non-negative integers

For an integer matrix $S$, and an integer vector $y$, I'm looking for solutions to $xS = y$ where the entries in $x$ are in the non-negative integers. I've been doing this with Sage's mixed integer ...
0
votes
0answers
61 views

On two dimensional integer programming with Euclid

I frequently hear LLL algorithm is generalization of Euclidean algorithm for GCDs. LLL algorithm is utilized in Lenstra's fixed dimension integer programming. Is there a way to perform two dimensional ...
-1
votes
1answer
78 views

How to solve MILP problem on several linear subspaces

I have a set of close mixed-integer programming problems. More exactly, all the problems share the same set of (binary and continuous) variables, the same set of linear inequality constraints, and the ...
1
vote
0answers
55 views

Does Barvinok's algorithm apply to convex integer program?

Barvinok provided a counting algorithm to count number of integer solutions to integer linear program that runs in polynomial time if the number of integer variables is fixed. If we have convex ...
2
votes
0answers
54 views

Linear functions in Lenstra's algorithm (integer programming)

I'm working on implementing Lenstra's algorthm. At the bottom of p.5 (at ``construct $n+1$ linear functions''), he says to constrain each $g_i:\mathbb{R}^n\to\mathbb{R}$ by its value on each of $n+1$ ...
0
votes
0answers
21 views

Binary optimisation to maximise covariance or L2-error, is it even possible? Could it be solved by relaxation?

I have a matrix A and a vector y, given A invertible the solution to find x is simple, however if we restrict x to be a binary vector i.e. $$ x_{i} \in \{0,1\} \quad \forall i $$ then we are not ...
1
vote
0answers
36 views

Structural properties of polytopes for mainstream integer or linear programs

Are there any papers/textbooks/monographs that describe distinguishing properties of the polytopes that arise when solving the linear relaxation of well-known integer programs? For example, it is ...
2
votes
1answer
112 views

Constructivity of two problems on a standard simplex?

Maximizing a hyperplane $\sum_i a_ix_i$ where $a_i\in\mathbb R$ and each $a_i$ are fixed and non-negative and $x_i$ are variables over a standard simplex $\sum_i x_i\leq 1$ with $0\leq x_i$ always ...
0
votes
0answers
46 views

Gröbner basis and integer programming

I was studying about grobner basis and observed one application of it in integer programming which is pretty much amazing but tougher than available methods like branch bound. Then what is the benefit ...
2
votes
1answer
70 views

Maximizing the length of a sequence under constraints

Fix $\{w_n\}_n$ a sequence of positive real numbers, fix positive integers $N,K$, and fix $\eta>1$. I'm looking for a sequence of integers $\{k_n\}_n$ optimizing the following problem: $$ \begin{...
1
vote
0answers
49 views

Pros and cons of using integer programming alone or combined integer and global optimization?

First, I am not sure if this is the right question to ask in this forum. But I have been looking for answers for a long time and I have been also asking my university's "engineering" professors but I ...
2
votes
0answers
49 views

Deciding whether a system of linear integer inequalities has infinitely many solutions

I have a quick question that I am struggling to find a solution to: Given a system of linear integer inequalities $A\textbf{x} \leq \textbf{b}$, where $A\in \mathbb{Z}^{m\times n}$ and $\textbf{b}\...
0
votes
0answers
68 views

Maximize sum of supermodular functions over nested sets

Let $R$ be a function that maps a set and a positive integer to a real positive number. We have that for any positive integer $t$ and $S \subseteq \{1, \ldots, t\}$, $R(S, t)$ satisfies: For all $t &...
1
vote
2answers
94 views

Integer linear programming (ILP) formulation of connectivity of induced subgraph

Can anyone assist me to find out what should be the ILP formulation of a case when I try to label vertices by say $0$, $1$ and $2$ and want the subgraph of graph $(V,E)$ made by same vertex set but ...
0
votes
0answers
19 views

How do you refer to the feasible set of solutions to a mixed-integer program?

I frequently want to refer to the feasible set of solutions to a mixed integer programming instance. Is there a name for a subset of $\mathbb{R}^n\times\{0,1\}^m$ of the form $\{(x,a)| Ax + Ba\leq b\}$...
1
vote
1answer
136 views

Gröbner basis via integer programming

I have studied some papers related to solving integer programs via Gröbner bases. I wonder if the other way is possible or not — i.e., given any ideal, can we find the Gröbner basis by translating ...
0
votes
1answer
142 views

What are all the possibilities of $A$ s.t. $\det(A)=k$?

Suppose we have $A \in M_3(\Bbb N\cup\{0\})$ s.t. sum of the elements of each row is $k $ for some fixed $k\in \Bbb N\cup\{0\}$. What are all the possibilities of $A$ s.t. $\det(A)=k$? We can start ...
0
votes
1answer
66 views

How do I solve this integer programming problem with non convex constraints?

I am not sure if this is the right place to post this question, please point me to the correct forum if I posted in a wrong place. I have an optimization problem like this ...
5
votes
1answer
149 views

Is Binary Integer Linear Programming solvable in polynomial time?

The paper Solving the Binary Linear Programming Model in Polynomial Time claims that Binary Integer Linear Programming is in P. However, it seems that no subsequent literature in the mainstream has ...
0
votes
1answer
80 views

Integer programming problem

I have an integer optimization problem with a non-linear function ($F(X)$) in the objective and one of the constraints. $F(X)=x_n^{i,j}\Big[\sum\limits_{\forall s\neq i}\sum\limits_{\forall m\in\...
1
vote
0answers
32 views

Modelling exact unions of polytopes in homogeneous case?

We can model disjunctions (note I am not looking for convex hull) of $t$ unbounded convex polyhedra given by $A^{(1)}x^{(1)}\leq b^{(1)}$,$\dots$,$A^{(t)}x^{(t)}\leq b^{(t)}$ exactly with a mixed ...
1
vote
0answers
75 views

Mixed integer formulation of union of polytopes?

Given $t$ different unbounded polyhedra $P_1:A^{(1)}x^{(1)}\leq b^{(1)},\dots,P_t:A^{(t)}x^{(t)}\leq b^{(t)}$ we are looking for the representation of $\bigcup_{i=1}^tP_i$ (not their convex hull) with ...
0
votes
1answer
169 views

Convex integer program with totally unimodular constraints

Suppose I have a convex (nonlinear) integer program with totally unimodular linear constraints. What are sufficient conditions one can impose on the convex objective function such that relaxing the ...
1
vote
1answer
81 views

Algorithm for (binary) integer programming

I am looking for an algorithm that can solve the following (binary) integer programming problem. The problem description is given below: \begin{align*} &\max\sum_{i\in I}\sum_{j\in J}g_{ij}w_{ij} \...
6
votes
0answers
230 views

Efficient solutions to general Bézout’s identity $a_1 b_1 + \dots + a_n b_n = 1$

Suppose I have integers $a_1, \dots, a_n$ which are coprime, meaning that $$a_1 b_1 + \dots + a_n b_n = 1$$ has a solution in integers $b_1, \dots, b_n$. I would like to get a bound saying ...
1
vote
0answers
34 views

Fast certficate of negativity for objective value of mixed-integer linear program

Let $c \in \mathbb R^n$, $A \in \mathbb R^{m \times n}$, $b \in \mathbb R^m$, and $I \subseteq \{1,2,\ldots,n\}$. Consider the Mixed integer linear program (MILP) $$ \begin{split} f^* = &\max \; ...
1
vote
0answers
89 views

Smallest integer lattice point by box measure in a polytope?

Given an integer lattice $\mathcal L\subseteq\mathbb Z^n$ represented by basis $\mathcal B$ and an integer linear program $Ax\leq b$ where $x\in\mathbb Z^n$ is unknown with $A\in\mathbb Z^{m\times n}$ ...
2
votes
1answer
289 views

Numbers that are the sum of 2 distinct nonzero squares in exactly 1 way [closed]

I need to emulate this sequence for a program: http://oeis.org/A025302 Stuff that I've taken into account: After finding the prime divisors of a number. I take any divisor as p and apply the ...
1
vote
1answer
255 views

Minimizing sum of ratio of linear functions (Sum of Linear Ratios Problem)

Given constants $c_i \in \mathbb{R}$ and $d_i \in \mathbb{R}$ and variables $x_i \in \mathbb{R}$, where $c_i > 0, d_i > 0, x_i > 0$ can we easily solve the following optimization problem: $$...
1
vote
0answers
87 views

When are quadratic integer programs “easy to solve”?

Let $N_i=\{0,1,\dots,\bar{n}_i\}$ and define $N=N_1\times \dots \times N_I$. I want to maximize $f$ on $N$. $f$ has the following form $$ f(n) = \sum_i A_i n_i -\sum_i \sum_{j\neq i} B_{ij} (n_i-n_j)^...
1
vote
1answer
139 views

How good is the LP relaxation?

Consider the optimization problem \begin{align} \max_{x\in\mathbb{R}^n}~c^Tx~, \text{ s.t. } Ax=b,~x_i\in\{0,1\}~\forall i \end{align}where $c,b\in\mathbb{R}_{+}^n$ and $A\in\mathbb{R}_{+}^{n\times n}$...
5
votes
2answers
467 views

What are the definable sets in Skolem arithmetic?

Definable subsets of $\mathbb N$ in the language of Presburger arithmetic are exactly the eventually periodic sets and quantifier free part corresponds to Integer Programming with linear inequalities ...
1
vote
0answers
95 views

How to solve such integer program problem?

Consider a $3$-tuple $(a,b,s)$ with $a,b\in\mathbb{Z}_+,s\in\mathbb{Q}_+$. Denote $ab-s$ by $\Delta$. Let $A$ be a positive number. What are the values of $A$ such that for any $(a,b,s)$ with $\Delta\...
1
vote
0answers
58 views

How to minimize n-polytope's bounding box with linear transformation?

I am working on an exact algorithm for integer linear programming for my master's thesis: $Ax\leq b, x \in \mathbb{Z}^n$ $cx\rightarrow min$ For my idea to work out, I need a guarantee that n-...
0
votes
1answer
217 views

Relax a rectangular linear assignment problem

I wonder if there is any literature on the following problem $$\begin{array}{ll} \underset{X \in \mathbb R^{m\times n}}{\text{minimize}} & \displaystyle\sum_{i,j} C_{i,j} X_{i,j}\\ \text{subject ...
1
vote
1answer
321 views

Feasibility Mixed integer Linear programming with quadratic constraints?

Consider the mixed integer program $$Ax\leq b$$ $$By\leq c$$ $$\begin{bmatrix}x&y\end{bmatrix}C\begin{bmatrix}x\\y\end{bmatrix}+D\begin{bmatrix}x\\y\end{bmatrix}\leq d$$ where $x$ are integer ...
-1
votes
2answers
89 views

On OR condition in Linear Programming with exponentially many constraints [closed]

Suppose we have two linear programs $Ax\leq b$ and $Bx\leq c$ is there a way to combine them into one program of possibly a larger dimension $Cy\leq d$ such that projection of vectors $y$ into a ...
2
votes
1answer
63 views

Clarification on FPTAS optimization in a paper

In the abstract of this paper by Hildebrand, Weismantel & Zemmer it is stated that they provide an FPTAS for $$\min x'Qx$$ over a fixed dimension polyhedron when $Q$ has at most one negative or ...
1
vote
1answer
87 views

Convex integer programming on totally unimodular polytope?

If $$\min x'Qx + Rx$$ $$Ax\leq b$$ $$x\in\mathbb Z^n$$ is a quadratic program with $x'Qx$ is convex is there a polynomial time algorithm for this if $A$ is totally unimodular? In particular if we ask ...
0
votes
0answers
209 views

Finding a point in the relative interior of the convex hull of a set of integer-valued vectors

Let $X \subset \mathbb{Z}^n$ be the set of integer-valued vectors satisfying a system of linear constraints. We can suppose that $X$ is the set of integral points in a given polyhydral set $Y \subset \...
2
votes
0answers
74 views

What does Lenstra's MILP do?

Honestly I do not understand why Lenstra's MILP is in $P$ if the number of integer dimensions is fixed. Here is what Lenstra says in 'http://people.csail.mit.edu/rrw/presentations/Lenstra81.pdf' in ...
2
votes
1answer
220 views

Bit complexity of Barvinok's algorithm

I have seen many references which state Barvinok's algorithm has polynomial time complexity for counting integer points of polytopes in fixed dimension. What exactly is this arithmetic complexity? ...
2
votes
1answer
149 views

On software for ILP

In 'Computational Experience with Lenstra's Algorithm' by L Gao, Y Zhang it is claimed that they have an implementation of Lenstra's fixed dimension integer programming algorithm. Is this available ...
0
votes
0answers
67 views

Discrete primal-duality in optimization

I would like to inquire about the existence of something perhaps similar to the duality theorem in the convex analysis or convex programming in the discrete setting. Here is a concrete example. Let $...
1
vote
2answers
152 views

Detection of gaps in binary vector through linear methods

Suppose I have a binary vector a = (0,1,1,1,0,0) of length $N$. I want to detect in a linear way whether a has any gaps in ...