Questions tagged [integer-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
3 votes
2 answers
26 views

Run-time complexity of solving a system of integer linear equations

Given an integer $n$-by-$n$ matrix $A$ and an integer $n$-by-$1$ vector $b$, what is the run-time complexity of finding an integer solution $x$ to the system $A x = b$? In general, integer linear ...
Erel Segal-Halevi's user avatar
0 votes
1 answer
39 views

Regular branch and bound vs integer programming branch and bound

In the context of linear integer programming, we have a branch and bound algorithm described here. This involves solving the non-integer constrained linear program and successively introducing ...
Rohit Pandey's user avatar
0 votes
0 answers
22 views

Placement of Tasks from Dataflow Graph on a Physical Graph

I have a dataflow graph where a set of different types of tasks are placed in corresponding types of nodes. Say the task types are called A, B, and C. A-type tasks are placed in all the leaf nodes of ...
bsha's user avatar
  • 1
0 votes
0 answers
16 views

Given objective value for ILP find parameter is NP hard?

For an integer linear program: Given a matrix $A \in \mathbb{Z}^{n\times d}$ and two vectors $b \in \mathbb{Z}^{n}$, $c \in \mathbb{Z}^{d}$, compute $max\{ c^{\top}x|Ax \leq b, x\geq 0, x\in \mathbb{Z}...
wsz_fantasy's user avatar
3 votes
1 answer
61 views

What is the complexity of minimising a convex quadratic function over the integers?

The problem of interest is $$ \min_{x\in\mathbb{Z}^n} \frac{1}{2}x^\top Q x + c^\top x $$ where $Q$ is a positive definite matrix. I am reasonably sure this can't be solved in poly-time, since the ...
Sriram's user avatar
  • 133
0 votes
0 answers
45 views

Complexity of $a\binom{x}{2} +by = c$

Manders and Adleman showed that it is NP-complete to decide given integers $a, b, c \geq 0$ in binary encoding whether $ax^2 + by = c$ has a solution over the non-negative integers. What is known ...
Tim Seppelt's user avatar
0 votes
3 answers
49 views

Which algorithms could be suitable for solving my disjunctive programming problem?

Following a previous post on the cs stack exchange (link to question), I have been searching to no avail for an implementation of a disjunctive programming solver in C# (or wrapped in C#). In this ...
Ed_Silver's user avatar
1 vote
1 answer
91 views

Integrality gap and complexity classes

I would like to know if there exist some complexity classes that are defined according to the integrality gap of their problems? In particular, is there a class of problems for which their integrality ...
Samuel Bismuth's user avatar
1 vote
1 answer
153 views

Boolean constraints for a connected component of a graph

Suppose I have an undirected graph $G=(V,E)$, and boolean variables $x_v$ (one for each vertex $v \in V$). These variables select a subset $S \subseteq V$ of vertices, namely the vertices $S=\{v \mid ...
D.W.'s user avatar
  • 159k
6 votes
1 answer
243 views

Can we compute in polynomial time, an upper bound on an optimal solution of an integer linear program?

Consider the following integer linear program (where $A$ is an integer matrix, $b$ an integer vector, and $c$ a positive integer vector): $$ \text{minimize}~~~ c\cdot x \\ \text{subject to}~~~ A\cdot ...
Samuel Bismuth's user avatar
1 vote
2 answers
344 views

Can the optimization version of a problem be NP-hard while its decision version is in P?

I have formulated an instance of a 0-1 Integer Program (IP), which I am trying to determine the complexity of (can this instance be solved in polynomial time or not). As we know, the 0-1 IP is NP-...
joachimkristensen's user avatar
1 vote
0 answers
34 views

Are there any Indicators that this specific Integer Linear Program is solvable in polynomial time

I have a pretty complex problem and I am using a rather complex ILP to solve it. In a special case of the problem the ILP is reduced to the following "simple" ILP. Additionally, I know that ...
Philip Mayer's user avatar
0 votes
1 answer
63 views

Given required total area and capacity, choose an amount for each of three given modules

Suppose you have three modules $m_1,m_2$ and $m_3$, each with a capacity of $c_i$ and area $a_i$. You are also given $A$ and $C$. How can you find some of the solutions to choose an amount of each ...
raibd's user avatar
  • 9
0 votes
1 answer
112 views

To write an IP and relax it to LP for finding a multi-set in a graph

I am new to Linear Programming and Approximation algorithms. and I am trying to do this exercise for writing an IP and relax it to LP. What I am given: A digraph ...
ConScience's user avatar
1 vote
1 answer
86 views

Boolean Integer Linear Optimization/Programming

Trying to solve an ILP optimization problem with a number of potential boolean variables and then express constraints on these variables based on those boolean results. Let's say I am doing 5 coin ...
B.D.'s user avatar
  • 11
2 votes
1 answer
45 views

minimum number of 2d elements whose sums across both dimensions satisfy some threshold

I have the following problem formulated as a linear integer program: \begin{align} & \text{minimize} && \sum_{i \in n} x_i\\ & \text{subject to} && \sum_{i \in n}{a_i}x_i \ge ...
TonyMontana18's user avatar
1 vote
1 answer
51 views

Modified set cover to identify "orthogonal" partitions

Setup I have a non-empty set of elements $U$ that are arranged spatially. I would like to partition $U$ into $N$ non-empty, disjoint subsets, $A_i$, having up to $M$ elements each. Each subset is only ...
user155171's user avatar
1 vote
1 answer
51 views

Possible to solve a combinatorial game with integer programming?

I recently had the idea that it would be neat if it were possible to make a SAT solver play combinatorial games. To start, I'm trying a relatively simple case of solving single-stack Misère Nim ...
Exalted Toast's user avatar
2 votes
1 answer
172 views

Integer linear programming formulation of boolean selection

Given a boolean variable $x$ and nonnegative integer variable $s$, I want to select $y = \begin{cases} 0 & \text{if} \ x = 0 \\ s & \text{if} \ x = 1 \end{cases}$. Currently in the ...
Wentinn Liao's user avatar
1 vote
1 answer
65 views

Why do we round from 1/2 when converting the LP to ILP for the weighted vertex cover problem?

I understand that to approximate a solution to the weighted vertex cover, we need to relax the integer linear program to a linear program which can be solved in polynomial time, but why do we round ...
Intradiction's user avatar
1 vote
0 answers
99 views

Solution methods for this Weighted Partial Set Cover-ish problem

Given a set of subsets $S_1, ..., S_N$ of a finite universe $E$ of elements $e_1, ..., e_n$ and mapping of those elements to an integer 'weight' $w_1, ... w_n$, select the subset of subsets which ...
Matt D's user avatar
  • 313
1 vote
1 answer
1k views

If greater than or equal to zero then binary variable equals 1: integer linear program

I have a variable $d_{i} \in \mathbb{Z}$ with an upper and lower bound. I also have a binary variable $v_{i}$ which I want to $=1$ if $d_{i} \geq 0$; else $v_{i} = 0$. How do I enforce this as a ...
Alex Pharaon's user avatar
0 votes
0 answers
25 views

Finding all integer solutions of an equality

I want to generate all solutions of $x_1+x_2+\ldots+x_{100}=6$ where $x_i$s are non-negative integers. Finding the number of such solutions is not difficult. But is there any easy way to get all ...
user12290's user avatar
  • 195
1 vote
1 answer
90 views

Can't figure out decision variable

Good Evening, I am trying to solve an exercise related to my algorithm designing course. I have understood the question and what it asks. I am required to formulate an ILP and then relax it to ...
ConScience's user avatar
0 votes
0 answers
86 views

ILP - Maximize the number of pairs of variables with the same value

I have a 0-1 integer linear program for a set of $2n$ variables $S = \{x_1, ..., x_n, y_1, ..., y_n\}$. My objective is to maximize the number of pairs $(x_i, y_i)$ such that $x_i = y_i$, $i = 1, ..., ...
Null_Space's user avatar
1 vote
0 answers
66 views

Does the standard 4/3 integrality gap for TSP example work for Euclidean TSP?

The standard LP gap example for the held karp relaxation for TSP min $ c^tx $ $x(\delta(S)) \geq 2 $ $x(\delta(v))=2 $ $x \geq 0$ Is to have two triangles and three long paths connecting the ...
Hao S's user avatar
  • 83
0 votes
1 answer
186 views

Is integer multicommodity flow problem is NP-hard?

As Wikipedia states the time complexity of Integer Linear programming(ILP) is NP-hard, so this means integer multicommodity flow problem is also NP-hard?
Munawar's user avatar
0 votes
1 answer
67 views

Encoding a binary sequence with shift in MILP

I would like to know if it's actually possible to encode a (binary) sequence with rotations in MILP/MIP. Given a binary sequence $(0,1,1,0,0,0,0,1)$ and variables $x_0,x_1,x_2,x_3,x_4,x_5,x_6,x_7$ I ...
DuckyQ's user avatar
  • 1
1 vote
0 answers
36 views

Selecting sets that maximise the cardinality of the union minus the cardinality of the difference

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. $$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
Alex Pharaon's user avatar
0 votes
0 answers
19 views

Selecting five binary vectors that when multiplied elementwise are most similar to another vector

I have a sparse $60000\times10000$ matrix where each element is either a $1$ or $0$ as follows. $$M=\begin{bmatrix}1 & 0 & 1 & \cdots & 1 \\1 & 1 & 0 & \cdots & 1 \\0 &...
Alex Pharaon's user avatar
2 votes
0 answers
43 views

Path that stays within a convex polyhedron

Let $\mathcal{P},\mathcal{Q}$ denote two convex polyhedra in $\mathbb{R}^d$, which can be represented by a set of linear inequalities. Let $A \subset \mathbb{R}^d$ be a finite set of vectors. The ...
D.W.'s user avatar
  • 159k
1 vote
0 answers
202 views

Fixed Parameter Tractable for Special Vertex Cover using ILP

The problem I'm trying to solve reads as follows: Given a graph $G=(V,E)$ ,a parameter $k$ and two values $U^\star, P^\star \in \mathbb N$, where every vertex $v\in V$ has a utility and a pollution $...
giorgioh's user avatar
  • 317
2 votes
2 answers
124 views

Efficient Algorithm to Find the Closest Integer Representation, in the Form $A\times\frac{N}{D}$ for a Value

The Problem I am working on a problem that boils down to finding the closest representation of an arbitrary number ($x$) in the form: $$x = A\times\frac{N}{D}$$ Where $A$ is a 32-bit integer, and $N$ ...
Mark Omo's user avatar
  • 123
3 votes
1 answer
467 views

Why is it useful to transform 0-1 integer programming problem into SAT problem?

There are several researches studying translating 0-1 integer programming into CNF form. For example, this paper and this C++ library. As the lecture notes here goes, translating 0-1 integer ...
Slangevar's user avatar
1 vote
1 answer
46 views

Find optimal play by optimizing orders of each player alternatingly

A zero-sum game for two players allows a player to take no action during a turn. Can I reach optimal play (where both players always choose the best possible action in each turn) by the following ...
Qurious Cube's user avatar
2 votes
0 answers
43 views

Efficient solution to this scheduling problem or integer optimization problem

Context: Suppose I have a matrix $P_k\in\mathbb{R}^{n\times n}$ that evolves in time $k$ according to $$ P_{k+1} = H_{\sigma(k)}^TP_kH_{\sigma(k)} $$ where $H_{\sigma(k)}\in\{H_1,\dots,H_L\}$, $H_i\in\...
FeedbackLooper's user avatar
1 vote
2 answers
213 views

Linear program for min-length pair of edge-disjoint paths problem

Consider a problem: we have an undirected graph $G = (V, E)$, function $l: E \to \mathbb{Z}_{+}$ where $l(e)$ is edge's length $e \in E$, and two vertices $s$ and $t$. And we want to find a pair $(A, ...
envy grunt's user avatar
1 vote
1 answer
492 views

Reduction from SUBSET-SUM to 0-1-INT-PROG

The 0-1-INT-PROG problem is given an integer $m \times n$ matrix $A$ and an integer $m$-vector $b$, is there an integer $n$-vector $x$ with $A \cdot x \leq b$. I am trying to prove that 0-1-INT-PROG ...
Tom Finet's user avatar
  • 258
1 vote
1 answer
124 views

Converting 4 variable if else condition to Linear integer program

There are four variables: $x_1, x_2, x_3, x_4$. If you choose either $x_3$ or $x_4$ or both — then you should choose exactly one of $x_1$ or $x_2$. If you choose neither $x_3$ or $x_4$ — then there is ...
Nishant Jalasutram's user avatar
2 votes
2 answers
359 views

Maximum weight perfect matching in general graphs

Let $G(V,E)$ be a graph (not necessarily bipartite), where edge $e \in E$ has weight $w_e$ (non-negative real). Then one can write the LP relaxation for maximum weight perfect matching as follows $$ \...
advocateofnone's user avatar
3 votes
1 answer
710 views

When LP solution is ILP solution?

For many discrete problems, it's natural to consider their continuous relaxations. A common case is when instead of $x_i \in \{0, 1\}$ we allow $x_i \in [0, 1]$. In certain cases, the original problem ...
user avatar
2 votes
1 answer
42 views

Expressing a constraint of the form $\max(x_1,x_2) \ge q$ in a linear program

I am trying to solve an LP in which one of the constraints is mentioned below, $$\max(x_1,x_2) \ge q,$$ where $x_1 \ge 0$ and $x_2 \ge 0$. Is it possible to do in linear programming?
Shiv Krishna Jaiswal's user avatar
3 votes
2 answers
193 views

Find a vector of non-negative integers $b$ that minimizes $\prod_{i = 1}^{D}\left(a_i + b_i\right)$ such that the product is a multiple of $c$

I'm trying to come up an efficient algorithm that, given a list of positive integers $a = \left(a_1, \ldots, a_D\right)$ and positive integer $c$, finds a list of non-negative integers $b = (b_1, \...
jodag's user avatar
  • 133
5 votes
3 answers
387 views

Algorithm for solving a mixed integer programming problem in polynomial time?

I have the following mixed integer programming (MIP) problem: $$ \begin{array}{rll} \text{Maximize } & z=k \\ \text{subject to } & a_ik - m_i \geq 0 & (i=1,\dots,n) \\ & b_ik - m_i \...
HelloGoodbye's user avatar
0 votes
1 answer
493 views

XOR Statement in integer programming

How can I convert a XOR statement into linear constraints for integer programming ? The expression is $(x_1 \geq 1)$ XOR $(x_2 \geq 1)$ where $x_1$ and $x_2$ are integer. It means that if $x_1 \geq 1$ ...
xavier laurens's user avatar
0 votes
1 answer
149 views

Convert an IF statement in Mixed Integer Programming

I want to convert an IF statement for my optimization problem. I want to minimize the total price. I want 800 tones of salt and 3 suppliers offer me their prices. Supplier $1$ offers me $100$ tones at ...
xavier laurens's user avatar
0 votes
1 answer
91 views

Combinatorial optimization algorithm with constraints and objective function

I'm looking for an algorithm that will let me optimally select items from a set. These items have properties which are involved in defining constraints as well as the objective function. .e.g Say each ...
Kedar's user avatar
  • 103
0 votes
0 answers
42 views

IF THEN condition in Linear Program

I have the following condition in an LP problem. I have a variable $x_i \in i = 1,2,..7$ and I need to constrain the problem via: if $x_1$ >5 then $x_2 \leq 30$ I'm stumped on how to formulate that ...
meb33's user avatar
  • 1
2 votes
1 answer
59 views

What is the best algorithm to find the optimal path in reducing company's real-estate footprint?

I was hoping someone could point me in the right direction in terms of what type of problem I am describing and what type of algorithm I should use to answer it. Here is the problem: A company is in ...
JuanC's user avatar
  • 23
1 vote
0 answers
35 views

IP Programming - objective function ist not a function BUT a table

Here is a short description of my problem: Part of my objective function is not a regular function. Instead it's a table. You can see a short extract here: So if the height is smaller or equal to 300 ...
Sina's user avatar
  • 11

1
2 3 4 5