Questions tagged [integer-programming]

For questions about mathematical optimization problems involving binary or general integer variables.

Filter by
Sorted by
Tagged with
4 votes
2 answers
485 views

Modeling an either-or-constraint

We would like to model a constraint for an assignment problem that dictates that either assign a specific subset of nodes $I\subset\mathcal{I}$ to a specific subset of nodes $J\subset\mathcal{J}$, or ...
user avatar
4 votes
2 answers
1k views

How can we write a binary variable as a power to a constant number?

Let $x_{i,j}$ be a two-dimensional binary variable. Is it possible to write $x_{i,j}$ as a power to a number? For example: $$1- 0.3^{x_{i,j}} $$
user avatar
  • 171
2 votes
3 answers
290 views

How to formulate if-then for two sums in an integer program

I have two sets of Boolean variables, $x_1, \dots, x_n$ and $y_1, \dots, y_m$ and a positive integer $b$. I would like to add the constraint: $$\text{If }\sum_i x_i = b \text{ then }\sum_i y_i > b$...
user avatar
  • 131
0 votes
2 answers
88 views

On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope

Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid A x \leq b\}$ is integer, while $A$ is ...
user avatar
5 votes
1 answer
99 views

Modulo Integer Programming, $m$ equations $n$ variables

I am following 'Application of Number Theory to Numerical Analysis', and there is a section by G.H. Bradley called 'Modulo Optimization Problems and Integer Linear Programming'. There he explains that ...
user avatar
3 votes
2 answers
240 views

Activate Binary if specific pairs of binaries equal 2

I have a problem formulation with binary variables x1,x2,x3,...
user avatar
2 votes
3 answers
118 views

Warm starting ideas for iteratively solving a model with a few additional constraints

I'm trying to solve a MILP model iteratively, and at each iteration a few constraints are added to the problem that cut off the previous optimal solution. I'm trying to figure out ways to implement a ...
user avatar
  • 29
3 votes
1 answer
184 views

Meaning of infeasible model: unsuccessful solving for an IP model with binary variables

For fun, I have modeled the Union-closed sets conjecture for a universe of a given size into a problem with binary variables. Each binary variable $x_k$ is the indicator of the set with elements ...
user avatar
  • 133
2 votes
1 answer
56 views

Load to ship assignment problem

Problem We’d like to optimize the delivery of loads across a network using a fleet of ships. Assume there is a set of $\mathcal{S}$ ships that need to deliver the set of $\mathcal{L}$ loads in a ...
user avatar
  • 129
7 votes
2 answers
472 views

I ran a relaxed MIP and got some integer results; how can I constrain MIP to match those integers?

Suppose I run a relaxation of an MIP. If my result is all integers, I have achieved the same min/max that the MIP would achieve. However, what can I say if some portion of my result is integer? If ...
user avatar
  • 533
0 votes
2 answers
104 views

What kind of problem is this : LP , Multi-objective , other?

I started studying Operations Research (OR) recently and I faced a problem in which I struggled to model it using the traditional LP models. After some attempts, I'm not sure if such a problem is a ...
user avatar
  • 109
0 votes
0 answers
62 views

Decision whether to serve the current table now or skip it

Can the following problem be formulated as a LP/IP problem, where an agent (waiter) that has just arrived at a certain table has to decide whether to visit that table now, or skip the current table ...
user avatar
2 votes
1 answer
55 views

Is it possible to change the underlying field from Euclidean to $\mathbb{F}_p$?

I have an ILP $Ax=b$ that I know has feasible solution(s), and I would like to find a/all feasible solution(s). The issue is that $A,x,b$ are defined over $\mathbb{F}_p$. More specifically, I need the ...
user avatar
3 votes
1 answer
74 views

Are there examples where introducing clusters of binary variables provides a benefit for solving?

I have a larger model with a large number of binary variables among many others. For the purpose of this question, consider the effect that the binary variables impose on the model to be similar to ...
user avatar
  • 303
3 votes
1 answer
61 views

LP Objective function for distributing workload

In this example, we have a group of students that each needs to be paired with a teacher. Each student has a different number of questions to ask the teacher, and each student-teacher pairing has a ...
user avatar
1 vote
0 answers
69 views

Bipartite matching

If I have two matrix $$A = \begin{bmatrix} 1 & 2 \\ 2 & 3 \end{bmatrix} $$ and $$B = \begin{bmatrix} 3 & 4 \\ 5 & 3 \end{bmatrix} $$ We have to make a matching between $A$ and $B$ ...
user avatar
  • 101
5 votes
1 answer
242 views

Writing a specific MILP problem

I would like to choose a set of $\beta_j$s that maximizes a simple linear objective function of the type $$ \underset{\beta_j}{\operatorname{max}}\sum_{j=1}^{J}X_j\beta_j \\ $$ subject to the ...
user avatar
  • 215
4 votes
1 answer
52 views

Can we reformulate a min-max nonlinear integer programming problem with the same optimal solution?

I'm trying to solve the below min-max nonlinear integer programming problem with the following objective functions: $$\min_{x_i,y_i} \max_i \left\{\frac{x_i}{2+3y_i} + \frac{2x_i}{4+7y_i}\right\} \\ \...
user avatar
6 votes
1 answer
164 views

Binary decision variable to indicate whether a continous decision variable is equal to its upper bound

Given a continuous nonnegative decision variable $x\in [0,T]$ bounded by $T$, how can we enforce a relation between $x$ and another binary decision variable $y$ such that when $x$ is equal to its ...
user avatar
  • 147
4 votes
1 answer
110 views

Binary decision variable to indicate whether an inequality is satisfied or not

I have a problem where I have a continuous decision variable (let's call it $m$) that is bounded between $(0, T]$ where $T>0$ is a predefined parameter. I also have another binary decision variable ...
user avatar
  • 147
-5 votes
1 answer
106 views

How to make Gurobi solve huge LP/IP model with only using A,b,c matrices?

I work on the scaling of MIP. I have scaled the A,b,c matrices of the huge original model. These matrices have more than 25000 rows and columns. I need to make Gurobi solve the scaled model. Normally, ...
user avatar
  • 105
2 votes
1 answer
35 views

How does a ratio of fixed cost to variable cost affect the problem difficulty?

I am working on an OR scheduling problem where OR opening cost is considered a fixed cost when a surgery is scheduled. If OR is used beyond a certain time, overtime cost is incurred. I would like to ...
user avatar
11 votes
5 answers
1k views

How to compute all paths between two given nodes in a network?

In this post, Erwin Kalvelagen describes a method to compute all paths between two nodes in a given network, such that: no arc is used more than once a given path does not contain more than $M$ arcs ...
user avatar
  • 10.1k
3 votes
2 answers
133 views

How to formulate and solve a variant of the Cutting Stock Problem

I should mention up front that I'm new to this forum and operations research in general. A problem has come up recently at work that I'm having a tough time solving. Our machine shop acquires many ...
user avatar
3 votes
1 answer
56 views

How to optimize two partitions at the same time under non linear constraints?

Let : $G$ be a undirected graph with nodes $a_1, \ldots, a_n$ $x_1, \ldots, x_m$ a set of real values $\epsilon > 0$ Var the variance function $d$ the "distance" between sets : $d(X_1, ...
user avatar
1 vote
1 answer
74 views

Taking derivatives of objective function with a binary variable to find minimum

I transform my minimization problem into one with only an objective function (no constraints). I only have one variable, which is binary. Can I derivate the objective and make it equal to 0 to find ...
user avatar
  • 323
5 votes
2 answers
273 views

Assembly line balancing: What does machine precedence mean?

I am looking at the looking at the following classical integer programming model for assembly line balancing: R.R.Vemuganti's "Applications of Set Covering, Set Packing and Set Partitioning ...
user avatar
2 votes
1 answer
53 views

Ensure that scheduled repeating maintenance has to be completed

I'm trying to model the scheduling of maintenance in some machines, and was wondering how I could ensure that, if maintenance is planned to start in period $t$, then it has to be carried out until ...
user avatar
4 votes
1 answer
86 views

Minimum up time for a machine in a linear program?

If we let $x_i$ = 1 if a machine is on during hour $i$, and 0 if the machine is off, how would we enforce a constraint that requires the machine to be “on” for a minimum of at least $M$ hours? For ...
user avatar
  • 433
6 votes
1 answer
152 views

Binary variable switch constraints

I have a set of binary variables $X = \{ x_1, x_2, x_3, ... x_N \}$ which are connect and used with the rest of the model. I want to define a set of binary variables which represents the change ...
user avatar
5 votes
2 answers
229 views

Confusion Between Different Types of Optimization Problems

I do not have a background in optimization and I am trying to teach myself more about this topic. I find myself having a lot of trouble understanding the different "types" of optimization ...
user avatar
  • 1,839
5 votes
2 answers
961 views

Is Traveling Salesman Problem "Combinatorial Optimization" or "Integer Optimization"?

I am looking at the Traveling Salesman Problem and I can not figure out if this problem is a type of "Integer Optimization Problem", or is a type of "Combinatorial Optimization Problem&...
user avatar
  • 1,839
6 votes
2 answers
467 views

Integer Programming Constraints - Min/Max Days Between Deliveries

I'm starting a consulting project for a client who manufacturers perishable food. They want to optimize their delivery schedule to each of their DSD (Direct Store Delivery) customers. For each store, ...
user avatar
4 votes
1 answer
106 views

How do you know if Column Generation is any faster than standard MIP formulations?

I'm currently in the process of learning about column generation, so I apologize in advance if I show a gross lack of understanding about it. Anyways, what I've gathered so far is that Column ...
user avatar
4 votes
1 answer
116 views

Exploiting ordering to removing infeasible solutions in MILP

I kindly ask for some ideas or references to exploit ordering in MILPs. In particular, there are resources $ r = [r_1, r_2, ..., r_K] $ such that $r_{i} \leq r_{i+1} $. These are input to the problem. ...
user avatar
  • 303
-3 votes
1 answer
97 views

Modelling constraint

I have the following problem statement: A company is considering to hire more operators. Starting with four machine operators in May, the company wants to investigate if it pays off to hire more. Each ...
user avatar
3 votes
1 answer
111 views

Dichotomic search for biobjective linear program, max flow problem for hospital patients

I recently asked this question about formulating a max flow diagram for hospital patients. I am now considering a secondary objective which is to maximize the effetiveness of the scheduled treatment. ...
user avatar
3 votes
1 answer
530 views

Complicated constraint with logical operators in PuLP

I have an optimization problem that I am trying to solve with PuLP. All the variables are Booleans. The variables that are "selected" will be true, all others false. Objective function is ...
user avatar
  • 33
2 votes
0 answers
33 views

How to construct a restriction for a blending problem that has 2 inputs that are blended, and as result we get 2 outputs?

THE PROBLEM A refinery has 10 million barrels of type A crude and 6 million barrels of Type B crude oil. The refinery has 3 plants to produce Gasoline (it makes a profit of 2 USD / barrel) and Naphtha ...
user avatar
  • 67
3 votes
1 answer
184 views

How to construct the linear programing representation of a blending problem?

THE PROBLEM A refinery has 10 million barrels of type A crude and 6 million barrels of Type B crude oil. The refinery has 3 plants to produce gasoline (it produces a profit of 2 USD / barrel) and ...
user avatar
  • 67
4 votes
1 answer
157 views

Adding a group constraint to binary decision variables

I have a problem where I have N binary decision variables where each one of them belongs to a group (Where the number of groups G is less than N) and I have to choose a subset of them to maximize some ...
user avatar
  • 147
2 votes
1 answer
137 views

Is this integer optimization problem still NP?

I have the following integer optimization problem \begin{align}\min&\quad\sum_ix_i\\ \text{s.t.}&\quad Ax \geq b\\ &\quad x \geq 0,\\ &\quad x \in \mathbb{Z}^n\end{align} where $b$ is ...
user avatar
3 votes
1 answer
61 views

Maximizing the number of nonnegative coordinates of $Wx$

I want to find good incumbent solutions to the following problem: $\newcommand{\RR}{\mathbb{R}}$ $\newcommand{\norm}[1]{\left\Vert#1\right\Vert}$ Given a matrix $W \in \RR^{m \times n}$, find the ...
user avatar
6 votes
2 answers
218 views

Multi-commodity Network Flow: Convert a node-arc solution to an arc-path solution

For a logistics optimization problem I am working on, the most natural expression of the problem is using a node-arc formulation of the MCNF. It is solved using an LP/MIP solver like CPLEX/Gurobi. ...
user avatar
  • 109
3 votes
3 answers
235 views

Scheduling for the shortest days using ILP

I've tried Or-Tools and MILP solvers a couple of different ways on this, but they take a surprisingly long time to realize that the solution they generated fairly quickly is in fact minimal. Is there ...
user avatar
5 votes
2 answers
336 views

The importance of evaluating the number of constraints

If I introduce a problem, say as an ILP formulation, should I also discuss the number of introduced constraints? If yes, why?
user avatar
1 vote
0 answers
37 views

Product allocation to vendor according to their demand

Company X has 3 types of products and due to the limited availability of raw materials, the production of products are also limited. They have partnered with Store A for them to sell their products. ...
user avatar
5 votes
1 answer
272 views

Is it possible to identify all possible Irreducible Infeasible Sets (IIS) for an infeasible Integer Linear Programming problem? (ILP)?

For an Integer Linear Programming problem (ILP), an irreducible infeasible set (IIS) is an infeasible subset of constraints, variable bounds, and integer restrictions that becomes feasible if any ...
user avatar
3 votes
1 answer
122 views

Conditional constraint with a strict inequality

It's almost this question: Formulating the conditional constraint But there they have non-strict inequality. I have $x_i$ a boolean decision var and $Q_i$ as a nonnegative integer decision variable ...
user avatar
  • 143
5 votes
1 answer
128 views

What fraction of the search space has been searched for ILP?

Is there a way to make Gurobi output (an estimate of) how much of the search space has already been cut off as infeasible? If not with Gurobi are you aware of any binary only (912 of them) ILP solver ...
user avatar

1
2 3 4 5