Questions tagged [integer-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
2
votes
1answer
31 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
32 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
1answer
137 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
165 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
29 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
18 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
31 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
26 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
28 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
28 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
65 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
41 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
44 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
27 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
34 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
18 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
42 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
33 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 ...
0
votes
0answers
60 views

Is it possible to form this as a linear program?

My problem is as follows: I have some number $n\in \mathbb{N}$ of items all of size $s\in \mathbb{N}$ that need to be fit into a distributed storage of sizes $[b_1, b_2, ..., b_m], \forall i, b_i \in \...
1
vote
0answers
27 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
270 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
17 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
55 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
49 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 ...
0
votes
0answers
32 views

Fractional knapsack with setup costs

I am considering a variant of the classical fractional knapsack problem, it's written in the following integer programming form Here $v_i, c_i, w_i, b$ are all positive. $c_i$ can be interpreted as ...
5
votes
2answers
67 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
41 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
17 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
80 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
74 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
81 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
105 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
62 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?
3
votes
0answers
153 views

Finding all feasible solutions to a multiple-knapsack program

How can I find all feasible solutions to a 0-1 integer program that I have based on a knapsack-style problem? I have $n$ items and $m$ knapsacks. Each knapsack has a space limitation and each item ...
1
vote
1answer
141 views

Integer programming to MAX-SAT translation

Reading A Comparison of Methods for Solving MAX-SAT Problems, I can see that a MAX-SAT problem can be translated to an integer programming (IP) problem. Definition of MAX-SAT [Wikipedia]: The ...
2
votes
3answers
1k views

Linear programming maximizes the minimum distance problem

I have a problem with creating an equation for linear programming solver. Company wants to open stores in k cities. For the purpose of even coverage of the entire ...
4
votes
0answers
50 views

Convex quadratic approximation to binary linear programming

Munapo (2016, American Journal of Operations Research, http://dx.doi.org/10.4236/ajor.2016.61001) purports to have a proof that binary linear programming [1] is solvable in polynomial time, and hence ...
0
votes
1answer
127 views

“Greater than AND smaller than” condition in integer linear program with a binary variable

I found this related question, but that's not quite it Is it possible to model this with integer programming: $$A = \begin{cases} 1 & \text{if } B \geq C \geq D \\ 0 & \text{otherwise}\end{...
1
vote
0answers
30 views

How do you solve a general linear diophantine equation in polynomial time (with minimization constraint)?

Given $$ a_1 X_1 + \dots + a_n X_n = b $$ where $a_i, b \in \Bbb{Z}$. How do you come up with a clearer picture of the solution set in polynomial time. Also, what I really want is to do the above,...
1
vote
1answer
93 views

If Then Constraint Linear Programming

I want to write the following constraint: If A=1 and B <= m then C=1 ( where A and C are binary, m is a constant and B is continuous).
1
vote
0answers
227 views

Time Complexity of Binary Linear Programming

As far as I know, Integer Linear Programming(ILP) problem is NP-complete. According to the following paper, Binary Linear Programming problem(BLP) can be solved in Polynomial time. http://dx.doi.org/...
3
votes
0answers
566 views

Minimum clique cover

How can the problem of finding the minimal clique cover be solved using linear/integer programming in a reasonable amount of time? Having an undirected graph, I am trying to partition all its ...
0
votes
0answers
70 views

What is the most efficient way to solve a workshop scheduling problem?

I am trying to design an algorithm to solve a workshop scheduling problem. The problem is as follows: I have to schedule a workshop consisting of a finite number of time slots, and a finite number of ...
4
votes
2answers
183 views

Does real linear programming produce bipartite perfect matching using maxflow reduction?

Given a bipartite graph the standard reduction to max flow is with the construction similar to following diagram: We can formulate max flow as an linear programming problem with integer variables in ...
2
votes
1answer
53 views

Linear programming IFF with equality constrain

Is it possible to write the following logical constrain in linear programming? Let $v$ be an integer variable and $k$ an integer constant. Let $y$ be a binary variable. The logical constraint is $y=...
1
vote
1answer
228 views

If-Then with disjunctions (OR) in Integer Linear Programming (ILP)

I have the following constraints I'm trying to model in Linear Integer Programming. I will try out diverse solvers for this later, but first I need to model the problem. Given the integer variables: ...
0
votes
1answer
95 views

How to model equality in Integer Linear Programming

How to implement v=(a==b) using Linear Programming? $$ v= \begin{cases} True, a=b\\ False, a≠b\\ \end{cases} $$ Until now I tried the big M-Method. To show a≤b: $$a-b+Mv≤M$$ $$-a+b-Mv≤-1$$ To show ...
1
vote
1answer
203 views

Mixed Integer Linear Programming application problem

I have a Mixed-Integer Linear Programming question. There's this game called Islanders. Pretty graphics, it's about maximizing your score building a small city in a confined island. Here's a quick ...
1
vote
1answer
34 views

Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?

Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem? I saw this Gurobi post that uses Integer Linear Programming to solve the traveling ...

1
2 3 4 5