Questions tagged [integer-programming]

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

199 questions
Filter by
Sorted by
Tagged with
76 views

Hospital treatment problem: Writing max-flow objective and maximize effectiveness of treatment objective

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 effectiveness of the scheduled treatment. ...
81 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. ...
81 views

Linear functions in Lenstra's algorithm

I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to constrain each $g_i:\mathbb{R}^n\to\mathbb{R}$ by its value on each ...
148 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 ...
114 views

Contiguous service area constraint

Background: I have a set of ZIP codes (e.g., all of the state of Wisconsin), and am trying to figure out an optimization-based approach to identify a subset of these ZIP codes for a logistics service ...
27 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 ...
146 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 ...
117 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 ...
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 ...
123 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 ...
58 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}{\left\Vert#1\right\Vert}$ Given a matrix $W \in \RR^{m \times n}$, find the ...
191 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. ...
225 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 ...
333 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?
34 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. ...
257 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 ...
99 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 ...
98 views

Deriving order/rank variable from another decision variable

There is a decision variable $x_i$ which denotes the time when a person is allowed to do his work. The objective function is $\min (x_i - a_i)$ where $a_i$ is the time when the person arrives at the ...
123 views

Constrain Mixed-Integer problem such that a graph is fully connected

I have a problem (see my questions about Architectural layouts which poses an interesting abstract question) where there exists an implicit (symmetric) graph whose values in the adjacency matrix are ...
292 views

When is a formulation with min function an ILP problem?

Consider a simple formulation like the one below. \begin{align} \max&\quad\sum_i x_i\\ \text{s.t.}&\quad x_i \leq \underset{\forall j<i}{\text{min}}\ f(x_j) \end{align} I am just wondering ...
52 views

Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case

Consider the following mixed-integer linear programming (MILP): \begin{equation*} \begin{array}{ll@{}ll} \text{maximize} & 1 & \\ \text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\ ...
86 views

Linearization of constraints in a ILP

I have been working on a Graph Theory problem for my thesis and got stuck about the linearization of some constraints. I am hiding everything, constraints, variables and so on, of my problem not ...
267 views

Issue in solving a large scale MIQP problem

I am solving a large scale MIQP optimisation problem at each step of a model predictive control problem. The problem description is as below. \begin{align} \min_{u} \quad (x_{k}&-x_\text{ref})^{T}...
339 views

Mixed-Integer Linear Programming With Free Variables

In the classic Mixed-Integer Linear Programming (MILP), the variables are fixed to be either integer or real. I am interested in the following MILP variant, where only one thing different from the ...
98 views

I am solving an OR scheduling problem where I assign the patient to (day,OR) tuple in Master Problem. Once the assignment is made, a subproblem can be solved for each (day,OR) tuple independently ...
72 views

R package for multi objective integer evolutionary algorithm

I have a discrete event simulation (simmer package) based on probability distributions in R. I would like to optimize the variables according to several (2 or more) objectives. I used the NSGA-II ...
46 views

Building blocks for unimodular matrices

I read Chapter 19.4 of Schrijver(1986) and get to know that every totally unimodular matrix can be produced by taking operations on network matrices and two certain matrices. I find that some paper ...
175 views

In a MIP, how to force a decision variable to be zero unless the sum of specific other decision variables is equal to a certain number?

In an MIP, how can I formulate a constraint such that a decision variable is only greater (or equal to) zero if (and only if) the sum of different decision variables is equal to something. I'm working ...
379 views

0 1 solution of linear programming problem with only equality constraints

I have a linear programming problem $LP$ where all the variables $x_{i}$ take value in $\left[0, 1\right]$ (that is $0\leq x_{i} \leq 1$). All the constraints are as follow: $a_{1}+a_{2}+a_{3}=1$ that ...
75 views

What if anything do linear relaxations of "nearby" MILP nodes tell us about other MILP nodes

Assume we are given MILP where $y \in (\mathbb{R}^+)^n$, $x_1, x_2 \in \{0, 1\}$ are the integer variables. It is obvious that this problem when solved via branch and bound has a 2 deep b&b-tree. ...
92 views

111 views

Is there any academic reference which suggests/uses dual values as initialization of Lagrangian multipliers?

The Lagrangian relaxation approach is used to generate lower (upper) bounds for minimization (maximization) problems by moving some constraints to the objective function and multiplying them by "...
138 views

What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?

I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
306 views

Scheduling optimisation constraint on consecutive shifts & consecutive night shifts (python)

I am trying to write a program to schedule a team of 8 individuals into shifts. I want to know how to model that every individual must get at least one night shift break, and must not work two ...
My question is about how to construct a mixed integer programming to model that there is no feasible solution to a given linear system. Specifically, given $x\in \mathbb{R}^{n}$ and $z\in \{0,1\}^{d}$,...