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
2 votes
0 answers
36 views

Determining the number of nodes within a cycle for an MILP problem

I have a MILP problem that requires knowing the number of nodes within a cycle (there will be multiple depending on inputs). I believe this will involve tracing nodes/values within cycles using the ...
user avatar
2 votes
2 answers
72 views

Docplex : How can I get the objective value of the relaxation of an MILP?

I want to solve a relaxed version of a MILP; I am using docplex.mp. I found LinearRelaxer in docplex.mp.relax_linear , however I keep getting this error message: model model1: found 1 un-relaxable ...
user avatar
  • 367
5 votes
1 answer
169 views

Additional resources for this type of problem formulation

I'm working on a problem with the following formulation: \begin{align} \min&\quad\sum_{i \in N} \sum_{j \in J} V_{ij}x_{ij} \\ \text{s.t.}&\quad \sum_j x_{ij} = 1 \quad \forall i \in N\\ &...
user avatar
2 votes
1 answer
76 views

Transfer an integer model to binary

I have a minimization problem with integer variables and would like to transform it to binary variables. The problem is, that my objective is to minimize the overall waiting time, which consists of ...
user avatar
  • 21
3 votes
1 answer
237 views

Practical, Short example of Mixed Integer Conic Program

Mixed Integer Conic Programs is a family of Mixed Integer Programs which are convex in all non integer variables. I am giving presentation on Mixed Integer technology. A large part of the presentation ...
user avatar
1 vote
0 answers
82 views

Converting quadratic constrains to linear constraint [closed]

I try to convert a quadratic constraint to a linear one: $$ w_j = \sum w_\text{j,i} \\ w_\text{j,i} = \frac{w_j}{D} \times u \\ w_j,D,u \in \mathbb{N} \\ $$ The values for $w_j$ and $D$ are constant ...
user avatar
  • 65
3 votes
1 answer
79 views

gurobi bigM constraint vs. epsilon

I am new to mathematical programming and I am trying to implement case specific constrains in Gurobi with Python. I am wondering about how I can implement my constraints in the fastest or most common ...
user avatar
  • 65
3 votes
1 answer
107 views

Multiprocessor Scheduling Problem: How to modify some constraints after variable changing?

I am thinking about classic problems concerning partitions as the Multiprocessor Scheduling Problem (or Bin Packing or Number Partitioning): Given $n$ tasks, with times $\{t_i\}_{i\in I_n}$, and $m$ ...
user avatar
2 votes
2 answers
206 views

Approximate Speed-Up With Increasing Cores?

First off: I totally understand if "it depends" is the only feasible solution. I'm running a large (to me) MIP using Gurobi in R on my local machine. (~2M binary decision variables, ~15K ...
user avatar
1 vote
1 answer
87 views

Relaxing a relation between variables if one of them reaches its maximal value

I am trying to formulate an optimization problem that can be described as a set of tanks $T$ where each tank $t$ has a maximum capacity of $\overline{r}_{t}$. I want to fill all tanks as much as ...
user avatar
  • 151
2 votes
0 answers
53 views

Type of combinatorial problem

I'm looking at a problem that looks as follows: $$ C = \sum_{i =1}^N\sum_{j<i} ( A_{ij} - B_{{P(i)P(j)}} )^2 $$ where $A$ and $B$ are square matrices and $P$ is a permutation matrix mapping all $i \...
user avatar
  • 29
6 votes
1 answer
331 views

How to Model Path Being Only Through Adjacent Cells

I am trying to develop a MILP for a path planning problem. I am operating on a grid of cells that represents a map. The arrangement of cells in the grid represents the placement of the cells in real ...
user avatar
1 vote
1 answer
134 views

How to model this problem?

I have recently tasked with a problem in which I have to locate electric vehicle charging points (new) keeping in mind that there continue to exist older charging points. The problem is to model the ...
user avatar
  • 121
-1 votes
0 answers
72 views

KKT model of Mixed Integer Model with global optimality

As the Gurobi solver claims, it can provide optimal global solutions to nonconvex quadratic optimization problems. With this in mind, it is possible to write the "KKT" model for "Mixed ...
user avatar
5 votes
0 answers
89 views

Reduce overhead Gurobi Python getting and setting attributes

I am using Gurobi 9.5.1 in Python 3.10. In the context of column generation I request the duals of the master problem and set them in the objective of the subproblem. This is done repeated times. <...
user avatar
  • 51
6 votes
2 answers
518 views

How to solve Rogo Puzzle with an extra constraint?

Given a n×m grid with numbered cells and forbidden cells, the objective of the Rogo puzzle is to find a loop of fixed length through the grid such that the sum of the numbers in the cells on the loop ...
user avatar
2 votes
1 answer
94 views

Restriction on gurobipy problem

The main problem is the optimization of the filling of a tank, filling it in cheap periods and extracting in expensive periods to sell. I am using Python and gurobipy. I am not able to model this ...
user avatar
  • 49
4 votes
2 answers
171 views

Identifying problem: Assignment + Job Shop Scheduling

I am new to OR. Hence, I want your advice on the problem I am trying to solve: Given: $O_1 \rightarrow O_2 \rightarrow O_3 \rightarrow ... \rightarrow O_n$: the sequence of operations to produce $1$ ...
user avatar
3 votes
2 answers
122 views

Impact of soft constraints in MILP

I'm wondering about the impact of soft constraints, since no one mentioned that in Soft constraints and hard constraints. My team makes all the constraints soft in MILP, so that a feasible solution ...
user avatar
  • 381
2 votes
3 answers
298 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
3 votes
1 answer
159 views

Solving a MIP by Relaxation

I have tried to understand the method of relaxing an integer program. I am in the process of implementing and solving a MIP for the FJSSP. For this I use the python-MIP package to solve it. From my ...
user avatar
2 votes
2 answers
62 views

WIP Inventory Level Constraint?

I'm modeling a continuous-time, two-stage manufacturing process with an MIP. There are about 100 finished-goods SKUs, and each of those belongs to about 25 different semi-finished categories in a ...
user avatar
5 votes
2 answers
389 views

Quadratically constrained convex optimization

I have tried to convert the following constraint into SOCP form but can't figure it out. My issue is that whenever I create the norm, the other side has to be square rooted which invalidates the SOCP ...
user avatar
4 votes
2 answers
124 views

crew scheduling problem with shift priority hard constraints

I am working on a crew scheduling problem formulated as a MIP binary optimization where each employee is represented by a binary variable $X_{ids}$ s.t. $i \in I$ is $i$th employee, $d \in D$ is the ...
user avatar
4 votes
2 answers
260 views

Trying to accelerate MILP solution

I developed a mathematical model that contains several thousand of binary variables (in addition to several thousand continuous variables). The binary variables model different things, say $X(i)$, $Y(...
user avatar
  • 1,936
6 votes
1 answer
246 views

Books for integer and mixed integer programming

I would like to know which is a good theoretical book to study integer programming and mixed integer programming. Searching I found a large number of books, however each with different approaches. The ...
user avatar
7 votes
1 answer
99 views

What insights/info can be gathered from visualizing the Branch & Bound tree

What insights/info can be gathered from visualizing the Branch & Bound tree. Some commercial solvers (FICO Xpress) don't seem to provide any API to readily visualize the tree. It has to be ...
user avatar
9 votes
2 answers
464 views

Dealing with Symmetry. Commercial solver defaults vs manual implementations

Since the modeler has domain/business knowledge of the problem being solved, is it possible to manually implement Isomorphism Pruning or Orbital branching and beat the default methods implemented by ...
user avatar
3 votes
2 answers
127 views

How does the VRPTW model ensure the arrival time at next station tightened?

In VRPTW problem, given $[a_i, b_i]$: the time window for node $i$ $x_{ijk}$: a binary variable that represents that the vehicle $k$ travels from node $i$ to $j$ (yes 1 otherwise 0) $s_i$: the ...
user avatar
  • 133
3 votes
2 answers
255 views

Activate Binary if specific pairs of binaries equal 2

I have a problem formulation with binary variables x1,x2,x3,...
user avatar
3 votes
1 answer
209 views

How do I turn off preprocessing in pulp?

there is an inbuilt preprocessing in CBC solver , which affects the optimality of my solution , I get the optimal output by turning this off in command prompt . How do I turn this off using pulp ?
user avatar
  • 459
6 votes
1 answer
101 views

Strong branching scores when objective function is constant

I have a MILP feasibility problem, so the objective function is constant (0). I have read that strong branching scores measure changes in the objective value. So my question is, what would be the ...
user avatar
  • 221
4 votes
2 answers
229 views

The variable splitting scheme in the context of Lagrangian relaxation

I am interested to know solving the generalized assignment problem (GAP) using the variable splitting scheme, specifically, in the context of Lagrangian relaxation. The problem is stated as follows: (...
user avatar
  • 5,833
1 vote
1 answer
51 views

Literature on fixed-charge network flow problems with inventory levels

I'm looking for optimization problem classes with inventory control constraints. Given a directed graph $G(V,A)$ where vertex set $V$ consists of production nodes and demand nodes. The arc set $A$ ...
user avatar
2 votes
2 answers
219 views

Find the list with the fewest elements whose cumulative sum reaches threshold

I have a question with which I am stuck and would be very grateful for help: I have multiple lists of non-negative numerical values (all of the same length) I want to find the list with the lowest <...
user avatar
  • 151
2 votes
3 answers
120 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
1 vote
1 answer
115 views

MILP constraint modelling

Lets assume $x$, $y$ are non negative continuous variables and $P$ an integer variable assuming either the value $1$ or the value $2$. How could I possibly model the relation If $x = y$ then $P = 2$ ...
user avatar
  • 1,936
1 vote
0 answers
33 views

Blended or hierarchical objectives if solving speed is more important

When optimizing a two objective task assignment problem, is it generally better to use blended objectives or hierarchical objectives if the speed to obtaining a near-optimal solution is more ...
user avatar
  • 179
6 votes
2 answers
305 views

How to measure the tightness of MILP models?

Suppose we have a MILP model. How can we say this model is tight or not? How to make it more tight? Any advice or example?
user avatar
2 votes
1 answer
88 views

Binary/integer variables get real values in docplex

I have an MILP model, in which I am handling all Big M constraints with add_if_then constraints (following this topic). I generate this model only once (to save time) and solve it iteratively with ...
user avatar
  • 293
5 votes
1 answer
102 views

Tightening constraints for better formulation

Lately, I have been reading a lot of papers where the constraints have been tightened to include better formulations leading to decrease in optimiality gaps and also the time for solving the ...
user avatar
  • 121
7 votes
1 answer
212 views

MILP - quantify magnitude of overlap

I'm building a manufacturing line optimization model. Part of the model is (lightly) penalizing running the line on the weekend. With time in minutes and t=0 ...
user avatar
2 votes
1 answer
101 views

Strong branching

Within B&B when it comes to select variables to branch on, I can use the concept of "strong branching". The optimizer, in my case CPLEX, then performs branching on variables it selects. ...
user avatar
  • 1,936
3 votes
3 answers
399 views

Converting if conditions to linear constraints

I have an optimization problem and I want to convert the following if conditions to linear constraints: If $(y_1 > U_1)$ and $(m_1)$ and $(E_1)$ then $x_1=1$ If $(y_2 > U_2)$ and $(m_2)$ and $(...
user avatar
  • 77
4 votes
2 answers
84 views

How to bundle pairs of trips?

I have a database of real-time optional trip demands. Each with a load that needs to be delivered from a departure point to a destination: ...
user avatar
  • 41
-4 votes
1 answer
43 views

MIP gives out zero as best solution when trying to optimize MIP model for flexible job-hop

I have implemented an existing MIP Model into python with the python-mip solver and somehow I only get '0' as a solution to my minimization problem. What could be the problem? I am fairly new to LP ...
user avatar
3 votes
1 answer
57 views

Determining constraint relevance in crew scheduling problem

I am working on a crew scheduling problem formulated as a MIP binary optimization where each employee is represented by a binary variable $X_{ids}$ s.t. $i \in I$ is $i$th employee, $d \in D$ is the ...
user avatar
1 vote
1 answer
113 views

How to get negative shadow price for minimization problem in Gurobi?

I am currently working on a scheduling problem (MIP) to minimize cost, and my idea is to first generate a set of discrete initial solutions, and build an LP model with the discrete initial solution to ...
user avatar
  • 19
4 votes
1 answer
136 views

Mathematically formulating formal problem of a cloud service scheduler

So, I have been tasked to create a formal mathematical description of problem statement on a cloud service scheduler for my team's university project, which is, honestly, a little weird of a thing to ...
user avatar
  • 79
2 votes
1 answer
80 views

Robust way to implement $(x=0) \Rightarrow (y=0)$, with $x$ nonnegative and $y$ binary

I am formulating a MILP in which there is a continuous variable x and a binary variable $y$. In the program formulation there are the following constraints: $Ay\leq x \leq By$ (with $0\leq A\leq B$). ...
user avatar
  • 414

1
2 3 4 5
13