Questions tagged [integer-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
13 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 ...
0
votes
0answers
32 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, ..., ...
1
vote
0answers
50 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 ...
0
votes
1answer
27 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?
0
votes
1answer
27 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 ...
1
vote
0answers
26 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 &...
0
votes
0answers
18 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 &...
2
votes
0answers
38 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 ...
1
vote
0answers
155 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 $...
2
votes
2answers
61 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$ ...
3
votes
1answer
127 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 ...
1
vote
1answer
43 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 ...
2
votes
0answers
38 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\...
1
vote
2answers
98 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, ...
0
votes
0answers
18 views

Multi-Objective Implicit Hitting Set for Multi-Objective MaxSAT

MaxSAT is a problem related to SAT where there is a finite collection of hard and soft clauses which share boolean variables. The hard clauses must be satisfied while the soft clauses have a weight. ...
1
vote
1answer
48 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 ...
1
vote
1answer
26 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 ...
2
votes
2answers
160 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 $$ \...
2
votes
1answer
97 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 ...
2
votes
1answer
38 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?
3
votes
2answers
175 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, \...
4
votes
3answers
221 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 \...
0
votes
1answer
81 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$ ...
0
votes
1answer
55 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 ...
0
votes
1answer
40 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 ...
0
votes
0answers
28 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 ...
2
votes
1answer
34 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 ...
1
vote
0answers
31 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 ...
2
votes
2answers
80 views

Constraint satisfaction problem: solve system, then evaluate whether many additional constraints are satisfied one at a time

I have a system that consists of binary inequality constraints between variables, plus some indicator variables that can assume only two values: ...
0
votes
1answer
64 views

Integer programming with indicators

I have the following question, and I need to write it as an integer programming problem: A manager of a company wants to by presents to his 100 employers. He can buy the presents from two different ...
0
votes
0answers
59 views

Efficient triangular decomposition of an integer

Euclidean division is an iterative process that has been made super-efficient at the CPU level, right? Its specification is that if I do (q, r) = f(n, d), I get ...
0
votes
0answers
28 views

Formulating if-then constraints in linear binary programming

From a stock of various computer accessories of different brands, the optimization problem requires deciding to keep or discard products. The decision should be made maintaining the following if-then ...
1
vote
2answers
77 views

Linear programming vs integer linear programming

Given $A,b$, let $Ax \le b$ be an instance of linear programming on the variables $x=(x_1,\dots,x_n)$. Assume that the constraints $0 \le x_i$ and $x_i \le 1$ are included in $A,b$. Suppose that ...
0
votes
0answers
19 views

What should I consider to analyze my proposed ILP in a scientific environment?

I am working on an NP-complete problem and, I have proposed an efficient (as I think) Integer Linear programming to find the solutions in some small instances. My algorithm can work on a greater size ...
0
votes
0answers
45 views

How develop a branch and bound algorithm for ILP with black box objective function?

The problem here described was taken from a university exercitation session. A serial production line is made of $K$ workstations: one kind product is manufactured by this line and has to be processed ...
2
votes
1answer
38 views

In what cases is solving Binary Linear Program easy (i.e. **P** complexity)? I'm looking at scheduling problems in particular

In what cases is solving Binary Linear Program easy (i.e. P complexity)? The reason I'm asking is to understand if I can reformulate a scheduling problem I'm currently working on in such a way to ...
1
vote
0answers
28 views

Seeking guidance on what to read for Feasibility Binary IP with ''almost total unimodular'' (-1, 0, 1)-Coefficient Matrix and No Obj Function

I am working on an algorithm in graph theory which I wish to prove it's polynomiality/NP-hardness. I am investigating a binary variable (0, 1) integer program which has the coefficient matrix ...
11
votes
3answers
2k views

Are there competitions for integer programming?

Are there competitions for integer programming like there are for SAT and MAXSAT?
0
votes
2answers
680 views

Intelligent use of XOR operator to find missing number

I've come across the following problem on leetcode & tried to solve it with the following code however there seems to be an even better solution that takes advantage of XOR. Leetcode has a ...
1
vote
0answers
29 views

ILP relaxation for Cluster deletion on C5

I'm looking for additional constraints that get rid of fractional solutions for the LP relaxation of the Cluster Deletion problem: Given an undirected graph $G = (V, E)$, find a min. sized $E' \...
0
votes
1answer
62 views

Binary integer programming problem without exponential memory

Consider binary integer programming problem with n variables. I think the branch and cut algorithm takes exponential memory. What are existing algorithms without much memory? Please suggest.
2
votes
1answer
159 views

Convert propositional logic formulas to mathematical constraints

Brief introduction In all boolean (or more generally mixed-integer) linear programs, constraints are represented as a matrix $A$, a support vector $b$ and is computed by $A^T x \leq b$, where $x$ is ...
5
votes
2answers
111 views

Detecting conservation, loss, or gain in a crafting game with items and recipes

Suppose we're designing a game like Minecraft where we have lots of items $i_1,i_2,...,i_n\in I$ and a bunch of recipes $r_1,r_2,...,r_m\in R$. Recipes are functions $r:(I\times\mathbb{N})^n\...
2
votes
0answers
70 views

Half-integral linear programs

What are some of the known properties of half-integral linear programs? That is, linear programs for which the solution vector always takes its values in the set $\{0, \frac{1}{2}, 1\}^n$. I'm asking ...
0
votes
0answers
30 views

Why are basic feasible solutions the same as vertices geometrically?

The first line on the Wikipedia page for basic feasible solutions reads, ...
2
votes
1answer
141 views

Linear programming over a finite field

I have a system of equations $Ax = b$ over some finite field $\mathbb{Z}_p$ and want to find a feasible solution. I'm sure this problem is NP-hard, but I'm struggling to find any literature on the ...
0
votes
1answer
140 views

Integer Linear programming formulation if then condition

I want to create constraints such that I can implement the following condition: Let A be an integer variable >= 0 with an upper bound of 12 I want to introduce the following variable B also an ...
1
vote
1answer
108 views

Minimum spanning tree formulation

Can any expert explain the reasoning behind the constraint in the following formulation of the minimum spanning tree? To formulate the minimum-cost spanning tree (MST) problem as an LP, we ...
3
votes
1answer
133 views

Integrality gap and LP-rounding

I have a doubt about integrality gap. If I know that there is no integrality gap for a given problem, i.e.: $$\frac{\mathrm{OPT}(\mathrm{ILP})}{\mathrm{OPT}(\mathrm{LP})} = 1 \text{ (right?)},$$ ...
2
votes
1answer
158 views

Enumerate all solutions to integer programming problem

How can I list all feasible solutions to an integer program? Is there an algorithm whose running time is reasonably related to the total number of such solutions?

1
2 3 4 5