Questions tagged [integer-programming]
The integer-programming tag has no summary.
251 questions
4
votes
1
answer
146
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 ...
- 41
0
votes
1
answer
272
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
1
answer
92
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 ...
1
vote
1
answer
206
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 ...
- 11
4
votes
1
answer
635
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 ...
D.W.♦
- 169k
1
vote
1
answer
306
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}...
- 113
2
votes
0
answers
2k
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 \...
- 21
1
vote
0
answers
406
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 ...
- 119
2
votes
1
answer
75
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 ...
- 123
2
votes
1
answer
197
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 ...
- 123
2
votes
0
answers
172
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 ...
- 121
1
vote
0
answers
64
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$ ...
- 11
1
vote
1
answer
535
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
3
answers
176
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
0
answers
167
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$ ...
- 111
1
vote
1
answer
238
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 ...
- 113
1
vote
0
answers
530
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:
...
- 111
2
votes
1
answer
194
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
1
answer
108
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 ...
- 151
0
votes
1
answer
546
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 ...
- 113
3
votes
3
answers
701
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:
An ...
- 163
0
votes
0
answers
87
views
LIP - Minimum Spanning Tree Cutset Formulation [duplicate]
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:
$...
- 163
1
vote
0
answers
452
views
maximizing absolute value in linear programming
I know that similar questions have been answered several times, and based on the answers, I attempted a solution to my problem. But I simply do not get the right results. The problem is as follows. I ...
1
vote
2
answers
853
views
Variant of the Knapsack Problem
I've got problem on integer programming, specifically with the following knapsack problem. I'd be happy to get some suggestions on how to solve the problem in a time efficient way.
There are 120 ...
2
votes
0
answers
124
views
Implementing a linear programming feasibility test in 3D
I have a little problem which requires determining if a system of linear inequalities in 3D is infeasible. The constraints (or oriented planes) are added one by one, so there is an opportunity to stop ...
- 121
1
vote
2
answers
98
views
Better way to formulate these constraints?
I have a binary variable $x_{ijt}^k$ that is $1$ iff job $i$ is assigned to machine $j$ at time $t$ using processor $k$. I would like to express the following constraints:
If job $i$ is assigned to ...
- 1,056
0
votes
2
answers
343
views
Conditional milp formulation
I have two binary integer variables, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\} $, and two real variables $T_{it}$ and $T_{ts}$ which have known upper and lower bounds. How can I model $\...
- 1
1
vote
0
answers
78
views
Can somebody suggest what is wrong with these constraint? [closed]
I have written two constraints for Mixed integer linear problem. I am working on the scheduling problem i.e., Scheduling of hybrid appliances.
For example, the washing machine is appliance indicated ...
- 123
1
vote
2
answers
99
views
How to create constraints for Mixed integer linear problem?
i am a beginner to Discrete optimization domain. I am working on the real world problem, i.e., Scheduling of hybrid appliances. I have hybrid appliances which can ...
- 123
2
votes
1
answer
116
views
Can this Arrow-Ring puzzle be encoded as an integer programming problem?
I would like to write a solver for these kind of Arrow-Ring puzzles. However, I can't encode all the constraints correctly.
I noticed that Sudoku can be solved using integer programming and I am ...
- 1,951
4
votes
1
answer
218
views
Integer Problem Solving with two boolean selection variables
I am trying to solve a two dimensional combinatorial problem.
Hereis my input space {{RA1,RA2},{RB1,RB2},{RC1,RC2}} and i have to choose two out of three elements{A,B,C} and one out of two possible ...
- 41
4
votes
2
answers
169
views
How to model and solve this problem?
I have a matrix $P \in M_n(\mathbb N)$, where
$$ P =
\begin{bmatrix}
0 & P_{12} & \ldots & P_{1n}\\
P_{21} & 0 & \ldots & P_{2n}\\
\vdots & \vdots & \ddots &...
2
votes
2
answers
415
views
Implications of Integral linear program
Let $(P)$ an Integer Linear Program, where we aim to find $x\in \{0,1\}^n$ maximizing a linear function $f:\mathbb{R}^n\rightarrow\mathbb{R}$ under some linear constraints $Ax\le b$
Let $(P^*)$ be ...
- 366
0
votes
0
answers
52
views
Is scalar variable multiplication of $0/1$ variable array possible in $MILP$?
I remember somewhere seeing the following. If $x$ and $y$ are integer variables then we cannot multiply them easily unless we know a bound $B$ on them.
Suppose I have an array $\overline x=[x_1\dots ...
- 2,957
2
votes
0
answers
108
views
IP algorithm for finding path in graph
Suppose for each positive integer $N$, we have a graph $G_N$ with $N$ vertices labelled $1$ to $N$ (so $\log N$ bits are required to specify a vertex). Suppose we have a PSPACE algorithm to determine ...
- 268
0
votes
1
answer
227
views
How do you proceed if your milp is not solvable
We are currently developing an ilp/milp model to fit the best routes with given resources (people) in a given timeframe and given visits and costs to travel from one visit to another (asymetrical).
...
- 113
-1
votes
1
answer
135
views
Can we use ILP here?
Is it possible to encode $y=0\implies G=0$ else $G=x$ by Integer Linear Programming where $x,y,G$ are integer variables?
The answer mentioned below gets to the point of taking absolute value of ...
- 2,957
2
votes
1
answer
214
views
Computational Complexity of a special case of Integer Programming
Integer Linear Programming (ILP) is NP-complete. However, there are special instances that can be solved in polynomial time. I am curious about the following integer program (IP) with equations and ...
- 799
2
votes
1
answer
584
views
Interval scheduling problem with priorities
I have a problem that is similar to the interval scheduling algorithm but it involves priorities. My data sets consist of the following data:
Cars with the start and end time of parking, along with ...
- 123
1
vote
0
answers
132
views
Decide whether a set of inequalities is solvable
Let $\{x_1, ..., x_n\}$ be a set of $n$ distinct variables, and suppose given a finite set of $m$ inequalities such that, for all $1 \leq i \leq n$, the $i$-th inequality is of the form: $$y_i + a_i \...
pbaren
4
votes
2
answers
995
views
How to check if a specific ILP problem can be solved in polynomial time or not?
How can we know that a specific ILP problem is solvable in polynomial time or not given the constraints?
- 173
3
votes
1
answer
4k
views
Why is integer programming more difficult than (real) linear programming? [duplicate]
Why is integer programming (IP) more difficult than (real) linear programming (LP)?
I searched a lot on the web, but I didn't find an answer.
- 341
1
vote
2
answers
653
views
ILP runtime seems to be linear?
I have a variation the shortest path problem, formulated as an ILP.
The system model is as follows:
There is a connected digraph consisting of 20 nodes, with each link having an associated weight ...
- 175
1
vote
0
answers
2k
views
Restriction for greater than constraint in linear programming
I have a model that considers real values and that uses a binary variable $x$. In this model, the following conditions should apply:
\begin{equation}
x=
\begin{cases}
0, & \text{if}\...
- 11
2
votes
1
answer
123
views
Portfolio allocation with a few twists
A similar question has been asked here, but this one is more complicated and has more constraints.
I'm trying to find an algorithm to solve the following (real-life) problem:
A customer has $M$ ...
- 123
2
votes
1
answer
1k
views
Are there practical methods for solving ILP?
Recently I encountered some papers in which the most important part seems to be writing an Integer Linear Program for a problem for which there exist some exact or heuristic algorithms!
Is solving an ...
- 287
1
vote
1
answer
83
views
Example of $c^Tx' = c^Tx$ where x is the optimal solution for the linear relaxation (LP) of x' (ILP)
I am looking for an example where the optimal solution for the LP problem is equal to the optimal solution of the ILP problem, but the solutions are different.
All I managed to think of was the ...
- 21
0
votes
1
answer
43
views
Relating indexes for parameters and variables
I am trying to solve a referee assignment problem, but I simply can't think of a way to relate my variable to one of the parameters, and I hope that someone in here can help.
I have the following ...
- 45
1
vote
0
answers
255
views
LP realaxation for multicut problem with polynomial number of constraints
The integer linear programming formulation for the multicut problem for the given graph $G = (V,E)$ and distinguished source-sink pairs of vertices $(s_1,t_1),...,(s_k,t_k)$ is:
\begin{alignat}{3}
\...
- 287
1
vote
1
answer
531
views
Computing overlap of intervals in an integer programming framework
Suppose I have 2 intervals C1 = [x1, x2] and C2 = [y1, y2], where x1,x2,y1,y2 are variables in an Integer program, I want to compute the overlap of C1 and C2. I am interested in a tight formulation ...
- 403