# Questions tagged [integer-programming]

The tag has no usage guidance.

239 questions
Filter by
Sorted by
Tagged with
37 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 ...
36 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
76 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
44 views

353 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 \...
344 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$ ...
104 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 ...
78 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 ...
36 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 ...
52 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
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 ...
99 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: ...
133 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 ...
66 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 ...
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 ...