# Questions tagged [integer-programming]

The tag has no usage guidance.

247 questions
Filter by
Sorted by
Tagged with
146 views

### Approximation algorithm for binary (linear) programs

I am interested in solving the following problem: $$\max c^\top x \qquad\text{s.t.}\\ Ax \le b\\ x \in \{0,1\}^n$$ One can assume that $c$, $A$ and $b$ have integer entries if that simplifies things....
• 555
76 views

• 113
68 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 ...
• 387
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 ...
53 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 ...
1 vote
95 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 ...
1 vote
203 views

• 133
405 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 \...
• 101
588 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$ ...
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 ...