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
1 answer
51 views

Is there a way to find out which original constraints are violated when a feasibility cut is generated in benders?

I've been dealing with Benders Decomposition and I've been wondering, if I have an unbounded solution of the dual subproblem, is it possible to find out which constraint from the original problem is ...
Arctic_Skill's user avatar
-1 votes
1 answer
67 views

MIP formulation for a lower semi-continuous function

How can I formulate in mixed linear programming (a set of constraints) the following issue. I have an objective function $\underset{x}{\max} g(x)$. I need to convert a continuous linear function $f(x)$...
Di Al's user avatar
  • 11
0 votes
0 answers
61 views

Using docplex with mpmath

In Python 3.10, is it possible to use docplex along with mpmath (https://mpmath.org/), e.g., to compute expressions in constraints and objectives with arbitrary precision?
Stencil's user avatar
  • 101
0 votes
2 answers
90 views

How to design a constraint to control flow in a non-network optimization model

I'm working on a production scheduling problem with a MIP model somebody left to me. This is a discrete-time model in which the constraints used to control the production and consumption of product p ...
CangWangu's user avatar
1 vote
1 answer
238 views

What is NoRel heuristic in GUROBI?

There is NoRel (or No Relaxation) heuristic in the Gurobi solver which helps to find very good feasible solutions for Mixed Integer Programs. I couldn't find explanation of its idea. Perhaps anybody ...
Elam Harnish's user avatar
3 votes
2 answers
148 views

Will adding this constraint help my model?

I am solving a maximization problem with continuous variables $x,z\in \mathbb{R}^+$ and binary variable $\delta \in \{0,1\}$. I am maximizing $x$ subject to side constraints and would like to enforce ...
abcd's user avatar
  • 55
1 vote
2 answers
157 views

Workforce scheduling problem

I am working on a employee scheduling problems (assigning shifts to temporary workers) by modeling it as a MIP. There is a one shift per day constraint for the employees. There are overnight shifts ...
SDC's user avatar
  • 33
4 votes
1 answer
144 views

What's the best way to speed up Benders Decomposition for a stochastic vehicle routing problem?

Currently I am working on an implementation of Benders Decomposition that solves a stochastic vehicle routing problem with synchronisation constraints. Sadly, at the moment it is not performing fast ...
Arctic_Skill's user avatar
2 votes
1 answer
219 views

Linearize piecewise function without big-M constraints

I have been attempting to solve a maximization problem where there is a piecewise function in the objective. Something like: $\sum_{n}(1-prob_{n})(1+x_n)$ Where $prob_{n} = $ \begin{cases} 0.25,...
akkha's user avatar
  • 67
0 votes
1 answer
73 views

Problems understanding model notation in LPs

today I came across a paper that uses a type of model notation I have never come across before. These are the objective function and constraints I don't quite understand. I am specifically interested ...
mingabua's user avatar
2 votes
1 answer
78 views

Compute time between tasks

I am trying to solve an optimization problem in which there is a set of tasks, $S$, where $s_i$ and $e_i$ are the starting and ending time of task $i \in S$. Each task $i $ must be done within its own ...
Christopher Expósito Izquierdo's user avatar
0 votes
0 answers
62 views

Travelling Salesman problem and Vehicle routing problems

Can someone explain to me why are we doing the $x_{ij}=1$ and and the constraint $U_j \geq u_i+1-n(1-x_{ij})$ Also do you have any books or sources in mind from where I could learn in more detail from ...
uni_lad's user avatar
  • 39
0 votes
0 answers
42 views

Formulation for data insight

There is an interesting data insight question that I want to solve using mathematical programming. I aim to find the combination of features that has the highest impact on the target indicators. We ...
Ying's user avatar
  • 105
1 vote
1 answer
41 views

Formulation to avoid partial coverage for demand points

I would like to assign items to a box over a time horizon where each box has an associated deadline. I was wondering if my formulation and / or variable definition can be improved. In other words, ...
whitepanda's user avatar
1 vote
0 answers
39 views

Is there a way to calcuate the maximum number of cuts in a Benders decomposition?

Since the benders algorithm is finite, there a maximum number of cuts that could theoretically be added. The worst case is that I add cuts for all extreme points and all extreme rays that are part of ...
Arctic_Skill's user avatar
4 votes
2 answers
231 views

Column generation: set partitioning vs set covering

I am working with a column generation algorithm and have noticed that convergence is much faster when my master is a set covering problem ($Ax\ge 1$) compared to when it is a set partitioning problem (...
Rom's user avatar
  • 41
1 vote
0 answers
81 views

Weird behavior when using Automatic Benders Decomposition in CPLEX

I've encountered some weird behavior when using the Automatic Benders Decomposition in CPLEX. I initially solved the MIP without BD and then I compared the results against the Full, Workers and User ...
CHE's user avatar
  • 113
1 vote
2 answers
213 views

Understanding the L-shaped-method and the different variants of it

I am currently trying to understand the integer L-shaped-method/stochastic version of Benders Decomposition because I have practical problem MIP that is stochastic and thus has very good decomposition ...
Arctic_Skill's user avatar
2 votes
2 answers
172 views

Express cardinality of index set satisfying conditions

I have two sets of binary variables $x_{i,j}$ and $y_{i,k}$, where $i, j, k$ ranges over some index set $I,J,K$, which satisfies the constraint $\sum_j x_{i,j} = 1$, $\sum_{k} y_{i, k} = 1$. How do I ...
TTY's user avatar
  • 223
2 votes
1 answer
205 views

Non-proprietary (Python friendly) alternatives to Cplex and Gurobi

I have implemented a pure binary integer combinatorial optimization routine within a Python module (importing gurobipy), and experimented with relaxing a few ...
Cbhihe's user avatar
  • 123
2 votes
1 answer
99 views

Bin packing problem with multiple dates

Data: I have the following items I need to ship, with the input data as below. Each item needs to be shipped by shipDate at the latest, but can be shipped as early as availDate. Each truck has a min/...
J. Doe's user avatar
  • 53
1 vote
0 answers
137 views

Non-Linear objective function due to piecewise component (part 2)

This is a follow up to this question: Non-Linear objective function due to piecewise component Consider a piecewise function but now with three segments but the objective remains the same as: $\sum_{n}...
akkha's user avatar
  • 67
2 votes
0 answers
28 views

The facet-defining inequalities for a single resource scheduling problem

Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions: $$ \text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, ...
A.Omidi's user avatar
  • 8,642
2 votes
1 answer
124 views

logic constraints for IP model

I have been struggling with the formulation of logic constraints. Is there any source you would recommend to understand the topic better or trick of formulation of the constraints?
uni_lad's user avatar
  • 39
1 vote
1 answer
84 views

Mixed Integer programming, the big M

In the constraints below, why have they used the big M? What do we look for in order to identify the big M in other questions?
uni_lad's user avatar
  • 39
1 vote
1 answer
72 views

How do I check convergence in stochastic Benders?

So in the deterministic version of Benders, the main process works like this: I initialize my x-vector (Integer variables from the master problem) and solve the dual subproblem (SP). I add an ...
Arctic_Skill's user avatar
1 vote
1 answer
88 views

How to understand the basis of LP problems given by HiGHS solver?

Here is part of a ".bas" file given by HiGHS using serial dual simplex method to solve an LP problem: HiGHS v1 Valid # Columns 57471 3 1 1 3 3 1 1 3 3 1 1 3 1 3 3 1 ... What does the number &...
andy's user avatar
  • 67
1 vote
0 answers
62 views

Need help with a model to optimize a trail in directed graph

The graph in the image represents the production sequencing on a machine with production capacity C in volume. Each node N represents a different product with a profit L per volume produced. Every ...
Maria's user avatar
  • 11
1 vote
1 answer
81 views

Recommendations to understand stochastic version of Benders?

I successfully understood and implemented a Benders algorithm for the deterministic version of the problem I am studying. However, I have some issues now diving into the stochastic model. I have the ...
Arctic_Skill's user avatar
0 votes
1 answer
149 views

Production scheduling

I'm formulating a scheduling problem with the following decision variables: $$X_t \space \text{is power sold to market in time period t} \\ Y_t \space \text{is power used for production in time period ...
fikacoder's user avatar
1 vote
1 answer
118 views

Mixed-Integer Programming Model for Scheduling with Dynamic Jobs

I have an optimization problem for deliveries between production lines and a warehouse in a small facility. I need to know how many vehicles and utilities to buy, such that cost and downtime are ...
user18463824's user avatar
3 votes
0 answers
118 views

From Quadratic to MILP?

I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP: (QP) $\min c^T x + x^T Q ...
Matheus Diógenes Andrade's user avatar
0 votes
0 answers
46 views

Distributed coloring of nodes of sensor ntwork

I have the same graph coloring problem as in Coloring of nodes of a sensor network @RobPratt and @prubin have proposed some very good solutions. This time I am or interested in distributed coloring ...
KGM's user avatar
  • 2,211
2 votes
1 answer
78 views

How to define the sequence depending setup time based on a time index formulation

I am working on a scheduling problem in which I have used two different MIP formulations and also based on the time index variable. My problem is in the class $ P_{j} | \ r_{j}, SDST \ | C_{Max} $. ...
A.Omidi's user avatar
  • 8,642
1 vote
2 answers
154 views

Matrix lookup modelling variants

As part of a bigger model I have a matrix of variables $x_{ij} \geq 0$ and a "selector" set of variables $y_j \in \{0,1\}, \sum_j y_j = 1$. From $x_{ij}$ I'd like to get the variables of ...
Christian's user avatar
  • 113
0 votes
2 answers
232 views

How to identify constraints that make problem not solvable in polynomial time?

I am reading this paper, available for free viewing, which contains an example of job shop scheduling, shown below. The details of the variable definitions, etc., can be found in the paper, but it's ...
somewhere's user avatar
-1 votes
3 answers
101 views

mip - mapping of equality to boolean variable

I want to create mip model which assign workers to entities. In case neighbour entities use same worker, objective should be increased by 1. A goal is to maximize total number of same workers for ...
gregy4's user avatar
  • 189
1 vote
2 answers
234 views

How to properly tackle a big model using weak constraints

I'm currently working on a model that has a large number of variables (around 200k), and I don't know what the proper way to handle such a big problem is. One suggestion I got is to use lazy ...
Marco's user avatar
  • 11
0 votes
0 answers
107 views

In routing problems, when is it ever necessary to include both 1) subtour elimination constraints, AND 2) elementary paths constraint?

In many routing problems, it is fairly common to include a constraint that ensures all vehicles follow an elementary path, meaning that no vertices are repeated. However, when an elementary path is ...
IsalanOnkar's user avatar
0 votes
0 answers
98 views

How should one proceed with column generation when the subproblem generates only columns with positive reduced costs?

I try to solve a MILP with Column generation. The Master Problem is a minimization problem with " $\le$ " constraint which lead to non-positive dual values. The problem is that the ...
Nada.S's user avatar
  • 409
3 votes
1 answer
227 views

Formulation of binary constraint with the least binary variables for linear programming

I am currently working on a formulation for a linear program of a complex problem. At the moment I am facing to formulate the following logical condition: There are two binary variables. Let's name ...
Nicolas Kaiser's user avatar
2 votes
1 answer
121 views

How to change the variable bound from an interval to its lower and upper bound in JuMP?

When I read a model from a ".mps" file using "read_from_file" in JuMP and print it, I find that many bounds are written in the interval format like "x \in [0, 1]". I want ...
andy's user avatar
  • 67
0 votes
1 answer
93 views

Is an insanely high number of feasibility cuts normal while solving a VRP with Benders?

I am in the process of trying to solve a VRP with synchronization constraints with Benders Decomposition. I am programming in C++ and my approach seems to be really slow for the following reason: My ...
Arctic_Skill's user avatar
1 vote
1 answer
41 views

if else condition with multiple criteria in MIP

I have problem like below Decision variable x1 >= 0 But it depends on selection variable s1 as binary variable If s1 = 0 then x1= 0 and if s1 = 1 then x1>0 how I can write this as constraint for ...
IEOR's user avatar
  • 13
1 vote
1 answer
76 views

How to calculate the duration of a task in each shift?

I am solving a job scheduling problem with three shifts, the duration of all shifts are assumed to be known (and might be equal): The tasks can start from any shift We know the duration of each task ...
Optimization team's user avatar
2 votes
1 answer
120 views

How to select intermediate nodes in a network?

I have a network where nodes are connected as shown in the Figure . Nodes 2 and 4 have a connection to the cloud node. I am writing constraints where at least one node with a connection to the cloud ...
bsha's user avatar
  • 81
2 votes
1 answer
99 views

Formulation for choosing how many items to manufacture

I am working on a scheduler for a manufacturing plant. I have currently set it up so the decision variables are set up as binary variables: $x_{m,p,s}$ = 1 if machine m is running part p on shift s ...
Dano's user avatar
  • 55
0 votes
1 answer
59 views

For an ILP relaxed to LP is the LP solution objective always less than the ILP solution?

If an Integer Linear Programming (ILP) problem is relaxed to a Linear Programming (LP) problem, is the objective value of the LP always less than the same ILP problem? Why?
ephemeral's user avatar
  • 897
1 vote
1 answer
41 views

Activating a sequence of the binary variables in a multi-dimensional array

Suppose we have an array of binary variables $\{x_{i,t,n}, \ \forall i \in I, t \in T, n \in N \}$. If we want to define a condition as, if any of $x_{i,t,n} = 1$ in an arbitrary index $i$, then the ...
A.Omidi's user avatar
  • 8,642
0 votes
0 answers
47 views

MILP: Linearization / approximation of mean and variance

My question- What is the standard practice to linearize / approximate computations of mean and variance using MILP solvers? Edit: referencing comments, an idea was proposed to set an upper limit and ...
jbuddy_13's user avatar
  • 519

1
2
3 4 5
20