Questions tagged [mixed-integer-programming]

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

Filter by
Sorted by
Tagged with
3
votes
1answer
50 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 ...
1
vote
2answers
85 views

How to find an optimal solution (out of many optimal sols) of an MILP, which satisfies a condition (maximizes a variable) in GUROBI?

I have an MILP problem with an objective of the type $\max z(x,g(x))= X - \varepsilon\cdot g(X)$, where $\varepsilon$ is a penalty term determined through an iterative process. What I want is to find ...
4
votes
3answers
202 views

VRPTW: is there a way to prevent waiting at a node before starting service?

In a typical VRPTW MIP formulation there are constraints that keep service at each node between node-specific lower and upper bounds. Using $x_{ijk}$ as a binary variable representing whether or not ...
2
votes
2answers
188 views

Piece-wise linear approximation of a constraint

We have a decision variable $0<y<1$ and the following constraint $$z=\frac{y^2-y+1}{y(1-y)},\tag{1}$$ We also have another constraint $$y=f(x),\tag{2}$$ where $f(x)$ is a linear function of $x$. ...
4
votes
1answer
113 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. ...
-3
votes
1answer
90 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 ...
11
votes
5answers
1k views

Dividing machines into groups of equal sizes so that each group has approximately same productivity

I have set of machines with varying productivity. I want put the machines in different groups so that the groups have approximately equal productivity. Lets say, we have $M$ machines. and we want to ...
8
votes
1answer
263 views

Modelling stronger binary expression

$\delta_1, \delta_2, ..., \delta_k, W$ are binary variables and the constraint $δ_1 + δ_2 + \ldots + δ_k ≤ W$ holds. Is it better to write $$\delta_1 + \delta_2 + \ldots +\delta_k \leq W$$ or \begin{...
5
votes
1answer
264 views

CPLEX gives different solutions of MILP every run

I am solving a mixed-integer (binary) linear problem using CPLEX as a solver (branch-and-bound method). But I encountered the following issue. Each run I get a different solution at a different node ...
3
votes
1answer
114 views

If-then condition formulation to avoid variable multiplication

I'm trying to formulate the following logic: If $y_i =1$, then $c_i \leq x_i$ If $y_i =0$, then $c_i \leq 0$ Where $y_i$, $c_i$, and $x_i$ are decision variables. The easy way would be to write: $$c_i ...
3
votes
1answer
209 views

Constraint on groups of variables

Assume a LP/MILP with a large number of variables. It is easy to formulate constraints to group variables such that each variable in a group takes the same value, if we know which variables are in a ...
22
votes
5answers
4k views

Why is open source operations research software so far behind open source statistics and machine learning software?

Like many who participate in this site, I work on projects in both operations research (OR) and statistics/machine learning (ML). The different states of open source software in these fields are often ...
1
vote
1answer
73 views

Custom lazy callback constraints using Google OR-Tools linear solver?

Is it possible to implement custom lazy callback constraints using OR-Tool's base linear solver? Through Google's docs, I've seen their TSP examples using the constraint solver ...
6
votes
3answers
1k views

Solving Logic puzzles through optimization

I have the following "logic puzzle" (I think this is considered as a "scheduling problem"): In this problem, there are 5 basketball players - provided some clues about their ...
2
votes
1answer
140 views

Linearizing division of two variables

For all $i \in I,j\in J$ and $k\in K$, define variables $x_{ij}, z_{ijk}\in\{0,1\}$, $y_{ij}\geq 0$ and constants $c_j, e_{ijk}, d_j, f_j >0$. We have the following constraint $$\sum_{j\in J_1}c_j\...
2
votes
0answers
29 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 ...
1
vote
0answers
51 views

Meaning of zeros in the column best bound in docplex?

I am trying to solve a large-scale MIP problem in docplex(python). I give to the model a MIP start solution, I remark that after 20 hours, the best integer still the cost of the MIP start and the best ...
3
votes
1answer
239 views

Mixed Integer Programming/Optimization using the Genetic Algorithm

I am working with the R programming language. Given a data set ("my_data"), I am trying to use an mixed integer optimization algorithm (e.g. genetic algorithm) to find out which filters ...
4
votes
1answer
150 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 ...
4
votes
1answer
118 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 ...
2
votes
0answers
64 views

Minimizing the number of machine starts

Please, if somebody has another approach to a similar MIP problem... Assume we have some machines $m$ and their activity could be interpreted by the boolean decision variable $x_{i,j} \ i \in m, j \in ...
4
votes
1answer
206 views

Can we simplify (perhaps linearize) this constraint?

We are dealing with a stochastic model and one of the constraints is \begin{align} y_j=\frac{\sum_{i \in I}\sum_{k \in K}\mathbb{E}\left[X_{ik}^2\right]x^k_{ij}}{\sum_{i \in I} \sum_{k \in K} \mathbb{...
2
votes
0answers
42 views

Indeterminacy Reduction for MINLP

I am considering a Mixed Interger NonLinear Program (MINLP), and using a solver to obtain admissible solutions. Is there a general method to reduce indeterminacy of solutions (e.g. by adding ...
2
votes
2answers
609 views

How to write "discount above a certain number sold" constraint?

In a simple cost minimizing problem, how do I model the following constraint? A dealer can supply up to 100 units at a cost of \$1240 per unit and a one time delivery fee of \$900. If however, 100 to ...
2
votes
1answer
226 views

mixed integer programming with if then statement for two binary sequences

I have two random binary sequences of the same size, denoted as P1 and P2 respectively here. Let's say they are both the size of ten, like P1 = [1,0,1,1,0,0,0,1,1,1], P2 = [0,1,1,0,0,1,0,0,1,1]. I ...
6
votes
1answer
392 views

RAM requirement for optimization problems

I understand that RAM required for optimization problem is problem specific and some problems require much more memory. I am thinking how much RAM I need for my system and need to decide between ...
2
votes
0answers
59 views

How to make a constraint for consecutive zeros in the mixed integer programming problems

I intend to generate a binary sequence with a size of N = 10, for example, [1, 0, 0, 0, 0, 1, 1, 1, 0, 0]. The constraint is that when 0 appears, it must appear for at least two consecutive times, ...
3
votes
1answer
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 ...
5
votes
1answer
133 views

How to construct my mixed integer programming problem with constraint of minimum consecutive ones

My target is to formulate a binary sequence with fixed size $N$ = 10, such as $[1, 0, 0, 0 ,1, 1, 0, 1, 0, 0]$. However, I want to constrain this sequence so that when 1 appears, it has to appear at ...
4
votes
1answer
113 views

Can you calculate the mean of some MIP variables using linear constraints?

got a lingering question from a graduate course in integer programming that's been bugging me ever since. Is it possible to find the mean of some variables in a MIP without resorting to quadratic ...
5
votes
1answer
70 views

How to transfer an optimization problem written with GUROBI (in python) in a grammar that can be readily solved with another solver?

Trying to use an opensource optimization tool in python (having used only gurobi for years) I see that the whole code (representing the optimization problem in pythonic language) must be written ...
2
votes
3answers
110 views

How to say to Gurobi solver with Python API to start from a given solution?

I have a binary linear program, where all my variables are binary. So, I have implemented the problem on python with Gurobi solver. I have implemented also a heuristic to find a near-optimal solution. ...
3
votes
1answer
172 views

If variable falls below a certain value, include difference to set value in objective

I think its easiest to describe my goal first and continue with my implementation and the resulting problems! My goal: Using Pyomo as interface and Gurobi as solver, if a variable $x_{i,t}$ falls ...
7
votes
0answers
92 views

Network design problem with rounded capacity constraints

I have a network design problem with complicating capacity constraints which I'm trying to model through a Mixed Integer Programming formulation. The problem is defined on a directed, incomplete graph ...
5
votes
1answer
262 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 ...
2
votes
1answer
52 views

Capacitated Facility Location problem with a dynamic set up cost

I am trying to solve a Capacitated Facility Location Problem (CFLP) with a dynamic setup cost in R. The problem statement is this: I have the transport cost The ...
2
votes
1answer
171 views

How to linearize the product of two integer variables?

Given two integer variables $L_x \leq x \leq U_x$ and $L_y \leq y \leq U_y$, how can we linearize the product $x \cdot y$?
3
votes
0answers
59 views

Is there any open source solver for MILP that can output the top N best results instead of the global best?

I am working on an MILP problem, and the project needs to output the top N best results rather than the global best. I am looking for an open source solver which has a callback function. Can anyone ...
2
votes
1answer
76 views

Linearize product of $x\cdot y \text{ with } x,y \in \{-1,0,1\}$ for MILP

I have a problem where I have many products between variables drawn out of $\{-1,0,1\}$. Could you suggest a linearization in terms of variables in $\{-1,0,1\}$ or $B_1 - B_2$ where $B_i \in \{0,1\}$ ...
1
vote
1answer
47 views

Rule of thumb for introducing known constraints in Mixed Integer problem when they grow the formula

When encoding a problem into a Mixed Integer formula one faces a trade-off between embedding domain knowledge which might require new helper variables to express the constraints thereby growing the ...
6
votes
1answer
653 views

Linear Programming: Integer and non-integer decision variables

I am looking for an answer to a question I can't quite get behind. I am given the following mathematical optimization problem: \begin{align}\min&\quad\sum_{t\in T}s_t\cdot z_t+h_t\cdot i_t+p_t\...
3
votes
1answer
73 views

Docplex : model is infeasible

I have implemented a model in cplex and even if I give it an initial feasible solution of a heuristic programmed elsewhere, it gives me the error "the model is infeasible". Please if someone ...
1
vote
1answer
52 views

KPIs in Docplex?

I want to add a KPI to calculate the percentage of occupancy of vehicles: the total travel time of occupied arcs (where the capacity of a vehicle is non-zero) over the total travel time. How can I ...
1
vote
1answer
50 views

Convex Optimization with Variable Dependency / no unmet demand carry forward

I'm running into an issue with a Linear Optimization Problem. The ultimate goal is to come back with an optimal production quantity (prod_qty) across several items ...
3
votes
1answer
57 views

How to build a contiguous path?

In my (simplified) problem I have a grid. Given an origin cell, I'd like to find a minimum-length path on this grid that connects to one or more target cells. My idea is to use a series of binary ...
1
vote
0answers
74 views

How to figure out integer variables in the relaxation set?

Suppose, there is mixed-integer programming as follows: $(1)$ $$\begin{aligned} \min&\quad c^{\top} x\\ \text{s.t.}& \quad A x \geq b \\ &\quad B x \geq d \\ &\quad x \geq 0 \\ &...
3
votes
1answer
293 views

Implement if-else without then part using int variables {0,1}

I have 6 binary variables $a_i$ for $i$ from 0 to 5. I would like to model the next if-else statement using only MILP constraints   if $(a_0+a_1+a_2)\mod 2=1$ then $(a_3+a_4+a_5) \mod 2 = 0$ I tried <...
5
votes
2answers
245 views

Combinatorial Feasibility Cuts for Benders Decomposition

Are there any advantages of adding constraints in Bender's master problem that ensure the feasibility of the subproblems? This would not add any feasibility cuts. Or is it beneficial to have a master ...
4
votes
1answer
182 views

How do constraints become redundant in a Big-M conjunction?

The following Big-M conjunction appears on page 14:3 of The Path&Cycle Formulation for the Hotspot Problem in Air Traffic Management: \begin{align*} \text{(i)} \quad t_{(g, \; s)} - t_{(f, \; s+...
4
votes
0answers
65 views

Modeling question on continuous variable that dependens on binary variables

Given a model with a binary variable $b_s$ that describes whether taking an item $s$ from a set $S$ or not. Consider that some other constraint in the model depends upon whether all items of the set ...

1
2 3 4 5
11