Questions tagged [integer-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2 votes
1 answer
26 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 ...
user avatar
1 vote
1 answer
18 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 ...
user avatar
  • 13
1 vote
0 answers
46 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 ...
user avatar
  • 183
0 votes
1 answer
86 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 ...
user avatar
0 votes
0 answers
22 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 ...
user avatar
  • 195
1 vote
1 answer
20 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 ...
user avatar
0 votes
0 answers
39 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, ..., ...
user avatar
1 vote
0 answers
56 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 ...
user avatar
  • 83
0 votes
1 answer
44 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?
user avatar
0 votes
1 answer
28 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 ...
user avatar
  • 1
1 vote
0 answers
30 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 &...
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 &...
user avatar
2 votes
0 answers
39 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 ...
user avatar
  • 141k
1 vote
0 answers
169 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 $...
user avatar
  • 317
2 votes
2 answers
72 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$ ...
user avatar
  • 123
3 votes
1 answer
169 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 ...
user avatar
1 vote
1 answer
44 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 ...
user avatar
2 votes
0 answers
40 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\...
user avatar
1 vote
2 answers
119 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, ...
user avatar
1 vote
1 answer
116 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 ...
user avatar
  • 248
1 vote
1 answer
46 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 ...
user avatar
2 votes
2 answers
194 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 $$ \...
user avatar
2 votes
1 answer
174 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
40 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?
user avatar
3 votes
2 answers
182 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, \...
user avatar
  • 133
4 votes
3 answers
255 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 \...
user avatar
0 votes
1 answer
145 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$ ...
user avatar
0 votes
1 answer
72 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 ...
user avatar
0 votes
1 answer
46 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 ...
user avatar
  • 103
0 votes
0 answers
30 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 ...
user avatar
  • 1
2 votes
1 answer
43 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 ...
user avatar
  • 23
1 vote
0 answers
33 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 ...
user avatar
  • 11
2 votes
2 answers
86 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: ...
user avatar
0 votes
1 answer
72 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 ...
user avatar
  • 119
0 votes
0 answers
63 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 ...
user avatar
  • 195
0 votes
0 answers
37 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 ...
user avatar
1 vote
2 answers
99 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 ...
user avatar
  • 141k
0 votes
0 answers
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 ...
user avatar
  • 21
0 votes
0 answers
55 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 ...
user avatar
2 votes
1 answer
44 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 ...
user avatar
  • 123
1 vote
0 answers
29 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 ...
user avatar
  • 111
11 votes
3 answers
2k views

Are there competitions for integer programming?

Are there competitions for integer programming like there are for SAT and MAXSAT?
user avatar
0 votes
2 answers
837 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 ...
user avatar
1 vote
0 answers
31 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' \...
user avatar
0 votes
1 answer
65 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.
user avatar
  • 33
2 votes
1 answer
209 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 ...
user avatar
5 votes
2 answers
115 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\...
user avatar
  • 153
4 votes
0 answers
89 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 ...
user avatar
0 votes
0 answers
44 views

Why are basic feasible solutions the same as vertices geometrically?

The first line on the Wikipedia page for basic feasible solutions reads, ...
user avatar
2 votes
1 answer
167 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 ...
user avatar
  • 121

1
2 3 4 5