Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [integer-programming]

The tag has no usage guidance.

2
votes
0answers
12 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 ...
0
votes
0answers
3 views

what can cause the best-bound to get tighter in the first MIP node?

I'm using gurobi MIP optimization engine for solving a mixed integer linear minimization problem. I see that the engine didn't start the branch and bound stage ...
0
votes
0answers
12 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
19 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
40 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
29 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
0answers
17 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
54 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
114 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 ...
0
votes
0answers
6 views

How to understand the separation phrase for generalized subtour constraints?

Suppose the constraints of our integer programming model consist of two parts: the polynomial-size formulations, that have a size (number of variables and constraints) which is polynomial w.r.t. the ...
2
votes
1answer
32 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
37 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
43 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: ...
0
votes
0answers
10 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: $...
1
vote
0answers
59 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
2answers
69 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
0answers
61 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 ...
1
vote
2answers
38 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 ...
0
votes
1answer
52 views

Conditional milp formulation

I have two binaries, $\alpha_{ts,it}$ and $\alpha_{ts,gshp} \in \{0,1\} $, and two reals $T_{it}$ and $T_{ts}$ which have upper and lower bounds. How can I model $\alpha_{ts,it}=1$ if the following ...
1
vote
0answers
56 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 ...
1
vote
2answers
44 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 ...
2
votes
1answer
32 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 ...
4
votes
1answer
49 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 ...
0
votes
0answers
28 views

Does floor and ceiling in LP implies more than $P=NP$?

We know ability to take floor and ceiling in Linear Programming (LP) implies $P=NP$ (just apply floor and ceiling to variable in $(0,2)$ to get binary variable and from this it follows $0/1$ ...
4
votes
2answers
91 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
1answer
106 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 ...
0
votes
0answers
18 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\...
2
votes
0answers
37 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 ...
0
votes
1answer
54 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). ...
-1
votes
1answer
64 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
votes
1answer
111 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 ...
2
votes
1answer
185 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 ...
1
vote
0answers
36 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 \...
3
votes
2answers
204 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?
2
votes
1answer
548 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.
0
votes
2answers
113 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 ...
1
vote
0answers
275 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}\...
1
vote
1answer
45 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$ ...
3
votes
1answer
173 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 ...
1
vote
1answer
33 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 ...
0
votes
1answer
13 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 ...
1
vote
0answers
78 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} \...
1
vote
1answer
79 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 ...
0
votes
2answers
102 views

Interview question (constant-time algorithm, ILP)

A juice machine has three buttons small, medium large. Each size adds an amount of juice in a range to the cup. Eg small might add from 10-20 mL, medium from 30-35 mL, large from 40-50 mL. The exact ...
-1
votes
1answer
891 views

Expressing conditional in linear program [duplicate]

I have two variables $A$ and $B$, with $A$ being binary and $B$ is a real number where $B \ge 0$. My conditions are: if B > 0 A = 1 else A = 0 ...
0
votes
1answer
495 views

Prove that Integer linear programming (ILP) is in NP

Help is needed, I've tried to solve it by myself but I could find any reasonable solution which is solid enough. this is what I've wrote: Consider a 0-1 ILP, where each variable x1,x2...,xn can ...
0
votes
0answers
46 views

How to monitor and alter the value of decision variables using if then else

Assuming I have two 0-1 decision variables X[a,b] and Y[i,j,e,d] where : X[a,b] = 1 if a is in b 0 otherwise Y[i,j,e,d] = 1 if (i,j) is matched with (e,d) 0 otherwise. I need to ensure that if ...
1
vote
3answers
216 views

Modification of dynamic programming for a knapsack problem

We have the following recursive function for the dynamic programming problem for a knapsack problem: \begin{align} V(i,w)=&max[ V(i-1,w), v_i +V(i-1,w-w_i)], \quad 1\leq i \leq n, 0\leq w \leq W \...
1
vote
1answer
440 views

Is 0-1 integer linear programming with only equality constraints NP-Hard?

We know that 0-1 integer linear programming is NP-Hard. What about 0-1 integer linear programming with only equality constraints? If so, how to prove it $$\min c^T x \text{ s.t. } Ax = b \quad x_i \...
1
vote
3answers
102 views

Solving a discrete optimization problem

Assume that $x_1,\dots,x_n$ are $n$ integer variables which takes values in a subset of given numbers, say $x_i\in\{5,6,\dots,5000\}$. Let $f_i(x_i)$ and $g_i(x_i)$ both be non-decreasing non-negative ...