Questions tagged [integer-programming]

The tag has no usage guidance.

Filter by
Sorted by
Tagged with
0
votes
1answer
37 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 ...
0
votes
1answer
48 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 ...
2
votes
1answer
67 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
19 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
58 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
52 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
173 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 ...
0
votes
0answers
18 views

Formulate the mathematical model to find the optimal solution

A, B, C and D are standing on the east bank of a river and wish to cross to the west side using a boat. The boat can hold at most two people at a time. A, being the most athletic, can row across the ...
0
votes
0answers
25 views

Knapsack Problem Via Column Generation

If I were to solve the linear relaxation of a knapsack problem via column generation how could I model the master problem and pricing subproblem? Given a set $N$ of items with value $v_{i}$ and weight ...
4
votes
0answers
43 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
62 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
25 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
72 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
135 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/...
0
votes
0answers
24 views

Flow Free as an integer programming

Flow Free is a popular mobile phone game where the problem is to connect the pieces . Wikipedia suggests this is equivalent to Number Link puzzles and as such is NP-complete. Supppse we wanted to ...
3
votes
0answers
248 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
49 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
106 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
35 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
106 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
63 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
0answers
172 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
27 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
vote
1answer
57 views

Modeling equality in an ILP

Lets say we have integer variables $a \in\mathbb{Z}^n$ and $M \in\{0,1\}^{n\times L}$. I am promised $a_i \leq L$, for some fixed constant $L$. I want to model the constraint $$M_{i,j} \iff (a_i=j)$...
2
votes
1answer
50 views

Logic of multiple variables in ILP

Is there a better way to represent an AND of $n$ variables together other than creating $O(n)$ new variables and constraints?
4
votes
1answer
73 views

Is this problem that's similar to integer linear programming also an NP-complete problem?

I've come across this problem while trying to work out a table-formatting algorithm. It's very similar to standard linear programming (though it uses $>$ instead of $<$; I'm not extremely ...
0
votes
0answers
49 views

Traveling Salesman Problem with profit and time limit as ILP formulation

How to formulate the following problem? The salesman gains a profit $p_{i}$ when visiting a city i, trip between city i and city j costs $c_{ij}$ and takes $t_{ij}$ time. The trip must not exceed a ...
1
vote
1answer
59 views

ILP representation of the number of maximal 1 sequences in a row

I am currently using an ILP to model events which occur on some input sequence from $1...n$. These events modify the input sequence in order to obtain a desired sequence. Each event can happen on some ...
4
votes
1answer
40 views

Why does it take so long to prove optimality when warm-starting from optimal solution

So I'm solving bigger instances of some binary-linear-program using cplex. The formulations of the problem I am using is integer friendly, meaning nearly all of my instances can be solved at the root ...
0
votes
1answer
131 views

Modified Knapsack Problem

I have a problem with the following optimisation problem: In total there are $n=100$ items. A quality level $L_i \in \{0,1,2,3,4,5\} $ must be selected for each of these items. The greater $L_i$ is, ...
0
votes
1answer
42 views

Modelling of minimal NOR-circuit problem with CP

I'm currently working on a Constraint Programming problem which I find difficult to model. Here 's the definition of the problem : " Given a specification of a Boolean function f(x1, ..., xn) in the ...
0
votes
0answers
28 views

Handling $AND$ and $OR$ cases in MILP?

Suppose I want to have an integer program for handling the cases $x_1>1\wedge x_2>1\wedge x_3>1\wedge\dots\wedge x_n>1\iff\delta=1$ $x_1>1\vee x_2>1\vee x_3>1\vee\dots\vee x_n&...
1
vote
1answer
54 views

Check a variable within a range with a binary variable [closed]

I have a value, a, it can be any value from 0 to 1. In an integer linear program, how can I formulate a constraint that uses a binary variable, y, to determine whether a is within a range of 0 and 1 ...
2
votes
1answer
137 views

Boolean variable that captures whether an inequality holds

I have an integer linear program with variables $x_1,\dots,x_n$. I have an inequality $a_1 x_1 + \dots + a_n x_n \ge b$ that I care about; it may or may or not hold. I want to introduce a boolean ...
1
vote
1answer
64 views

How to model a logical indicator when two inequalities hold in Integer Programming?

I have an IP program where $\forall i \in I, j \in J$ my decision variables are $x_{i,j}$. I have two sets of inequalities (one inequality for every $i,j$ pair) that are of interest which are $$a_{i,j}...
1
vote
0answers
267 views

“Greater than 0” condition in integer linear program with a binary variable [duplicate]

How can one model the following condition in an integer linear program? $$ y = \begin{cases} 1 & \text{if } x > 0\\ 0 & \text{otherwise}\end{cases} $$ Where $y \in \{0,1\}$ and $x \in \...
1
vote
0answers
160 views

Travelling Salesman problem using Guided Local Search

I am doing Week_4 of https://www.coursera.org/learn/discrete-optimization/ stuck in solving TSP. As there are a lot of methods to solve this problem, I am currently coding Guided Local Search as ...
2
votes
1answer
41 views

List of algorithm problems in term of ideals

I am new in algorithm and studied about some problems in algorithm related to graph theory. These problems we can transform to some polynomials and if for each set of polynomials related to a problem ...
2
votes
1answer
46 views

How to efficiently specify a MILP constraint with nested AND and ORs

Let's say I want to set x1=1 if (x2=1 AND x3=1 AND x4=1) or (x5=1 and x6=1) or (x7=1) else x1=0 All of the xs are binary ...
2
votes
0answers
52 views

Relaxations for MILP with logical constraints

I have an LP with a (non-fixed) number of logical constraints in the form of $X_1 \rightarrow X_2$ (where $X_1$ and $X_2$ are linear functions inequalities of the $n$ input variables). To express ...
1
vote
0answers
21 views

Given a set of solutions, find an IP formulation with the same solution set

Input: A list of integer variables $x_1, ..., x_n$. A finite set of feasible solutions $S \subset \mathbb{Z}^n$. Task: Find an integer linear program (IP) on the integer variables $x_1,...,x_n$ ...
1
vote
1answer
117 views

Representing chained XOR operations as linear inequalities

I'm trying to solve an integer linear program (ILP) in which a constraint of the following kind must be met: $x_1 \oplus x_2 \oplus \cdots \oplus x_n = 1$ where $\oplus$ is the binary xor operator. ...
-1
votes
2answers
53 views

Solve this integer program (problem: Travelling salesman problem)

How do one solve the following integer program? $$ \begin{align*} \text{minimize} \quad &\sum_{(i,j) \in E} d_{ij} x_{ij} \\ \text{subject to} \quad & \sum_{j \in V} x_{ij} = 2 \;\; \forall i ...
1
vote
0answers
73 views

Big M method for continuous variables

Is there any way to model the big M method for continuous variables? Something similar to this but $B, C \in \mathbb{R}_{\geq 0}$ and $A\in\{0,1\}$. Due to the precision problem, when the $B$ and $C$ ...
1
vote
1answer
74 views

(M)ILP overlap of two intervals

I got an ILP Model where $c_i$ represents the starting time for a visit$_i$. $c_i$ is already constraint by a number of constraints, one is $c_i > 0$. I have now outside of my model 0 or multiple ...
1
vote
0answers
144 views

How does prefix summing the count histogram in counting sort result in an array of output indices?

My implementation of counting sort is based on the description I found here. I've also included my code in this REPL, but here it is: ...
2
votes
1answer
128 views

What is the right term/theory for prediction of Binary Variables based upon their continuous value?

I am working with a linear programming problem in which we have around 3500 binary variables. Usually IBM's Cplex takes around 72 hours to get an objective with a gap of around 15-20% with best ...
2
votes
1answer
39 views

Computational complexity of maximizing sum of rational functions

I have a optimization problem: $$\max_z\ \sum_{i=1}^n \frac{W_i}{D_i - z_i} \quad \text{s.t.}\ \sum_{i=1}^n z_i \leq k, z_i \in [0,k],$$ where each $W_i$, $D_i$ are constants and $z_i$ are integer ...
0
votes
1answer
326 views

How to write an if then logical constraint given part of the input related to a decision variable?

I am trying to solve an assignment problem-like from a bi-objective persepctive where I have a marketplace of vendors proposing different machines with different types and specs. The goal is to select ...
2
votes
3answers
211 views

Need Help Understanding MST Cutset Formulation

I just started learning about linear programming in my class, and I'm having some trouble understanding the MST Formulation Integer Linear Programming (Cutset Formulation). This is the definition: ...