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

(Dis-)Advantages of Design Space Exploration Frameworks generating MILPs (e.g. DeSyDe, ArchEx, ...)

Are there still reasons to create MILPs manually from the ground up, or is it more suitable to rely on certain frameworks translating requirements and elements into proper MILPs using a set of rules, ...
baxbear's user avatar
  • 287
0 votes
1 answer
60 views

Converting a piecewise function to linear equations

I am trying to build a MILP model. In this model, I have a dependent variable (alpha) that its value depends on the value of some other variables (or different combination of some other variables). In ...
Sam's user avatar
  • 67
0 votes
1 answer
66 views

Help with implementing my mathematical model in gurobipy

I am using Gurobipy to solve this problem formulation and I have been stuck here for weeks trying to diagnose why I get infeasible solutions. What did I miss ? This is a prize collection VRP model ...
applethal's user avatar
1 vote
0 answers
78 views

Converting a Linear Program with TU Constraint Matrix to a Nonlinear Convex Model: Solver Performance?

I'm currently working on a large Mixed Integer Program (MIP) where the constraint matrix is Totally Unimodular (TU), allowing me to model it as a Linear Program (LP) for efficiency, as total ...
graphtheory123's user avatar
4 votes
1 answer
226 views

Can we add a certain binary row to a matrix which preserves total unimodularity?

Suppose I have a matrix $A\in \{-1, 0, 1\}^{m\times n}$ which is Totally Unimodular (TU), and a vector $b^T \in \{-1, 0, 1\}^{1\times n}$ which has exactly one entry which is $1$ and exactly one entry ...
graphtheory123's user avatar
1 vote
0 answers
33 views

What reasons would cause lazy constraints to degrade the performances when reoptimizing with a different objective?

We are currently solving a hard MILP problem on optimality. Once it has been solved, several times (from 5 to 10 times), we change one coefficient of the objective function and reoptimize. Thus the ...
JKHA's user avatar
  • 679
2 votes
1 answer
143 views

Why would a solver stay on node 0 and still improve the gap?

I understand how exploring the Branch-and-cut tree would help improve the best bound known and the incumbent of a MILP, however, on some instances that I deal with, my solver (Gurobi) seems to keep ...
JKHA's user avatar
  • 679
3 votes
1 answer
112 views

What does a solver do with a MIP warmstart solution?

From what I understand, most solvers use a user provided solution by first detecting if it feasible. If it is feasible, its objective value is used as a first bound for the branch and cut tree, this ...
JKHA's user avatar
  • 679
1 vote
1 answer
55 views

Exploiting identical subproblems in column generation

As suggested, this is a new post. I have the following column generation model. With the following master problem $MP$: \begin{align} &\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\ &\...
nflgreaternba's user avatar
1 vote
1 answer
96 views

Convex approximation of a constraint

I have a constraint given as $ \left|x_n+\beta x_{n+ 1}\right|-\varepsilon_{ky}\left|x_{n}\right|\leq0\hspace{1em}\forall n=1,2...,N $ I need to convert this into a convex form to implement in CVX. $...
Muhammad's user avatar
0 votes
0 answers
44 views

monte carlo for a selection problem

What type of Monte Carlo simulation is suitable for solving this problem? Also, how can we select results after simulation to guarantee feasibility?
Mohammad Reza Salehizadeh's user avatar
2 votes
1 answer
65 views

Workforce scheduling problem difficulty

I am working on a workforce scheduling MIP -- given a set of shift candidates (different shapes and sizes of shifts created out of labor demand) and a set of workers, optimally assign the shifts under ...
SDC's user avatar
  • 33
1 vote
1 answer
106 views

How to turn off tree search in fico xpress ? Couldn't see relevant documentation

trying to solve a very large problem , using heuremphasis as 3 , cutfreq=0 , scaling =4, run time reduced significantly however , solver spends 400 seconds in tree search , but couldn't see any ...
21vs's user avatar
  • 489
2 votes
0 answers
84 views

Re-formulating an LP where a subset of constraints can be loosened?

I have an LP of the structure below (omitting some constraints that are not directly applicable for this question). $$\text{min } c'x$$ $$Ax + By \geq d$$ for a given $A \in R^{m \times a}_{>0}, B \...
Mason's user avatar
  • 515
3 votes
1 answer
110 views

Equivalent constraints in MILP give different answers

I'm getting unexpected results from the HiGHS solver in scipy (scipy.optimize.linprog with integrality constraints). In my mixed integer program one of my constraints is that $x_0 \geq 100$. I get a ...
Hubcity's user avatar
  • 33
0 votes
1 answer
113 views

PuLP is ignoring constraints, and setting everything to 0 for minimization problem

I have a multi-objective optimization problem I am trying to solve with competing objectives. I am trying to model a network of industrial businesses which can share wastewater rather than sending it ...
Caleb O's user avatar
  • 13
3 votes
1 answer
269 views

How to modify master problem and individual sub problems in column generation?

This is a follow-up post regarding this one. I deleted this new post once before, as I was unhappy with the formulation. I have the following basic nurse scheduling MILP, which tries to cover the ...
nflgreaternba's user avatar
1 vote
1 answer
113 views

How to model the following Constraint

I would like to model the following: $B \le \alpha \implies \sum_i W(i) \ge \beta$, where $B$ a continuous variable, $W(i)$ binary variables, $\alpha$ a real constant number, $\beta$ an integer ...
Clement's user avatar
  • 2,224
0 votes
1 answer
58 views

Formulation of a stepwise linear approximation

I am currently trying to solve an MILP in Gurobi. Unfortunately, Gurobi does not support non-linear functions and I would like to do the following. I currently have the following constraint. It ...
nflgreaternba's user avatar
3 votes
2 answers
213 views

Convex equivalent of a constraint

I have a constraint as follows in my MILP model: $$ \sum_{e} (a_1(e) - a_2(e))^2 \leq M $$ Where, $a_1(e)$ and $a_2(e)$ are binary variables. Would you please guide me how can I find the equivalent ...
Mohammad Reza Salehizadeh's user avatar
2 votes
1 answer
59 views

How to Group IDs Based on the Difference of Each ID’s Min and Max Value?

I have a dataset that contains IDs along with their corresponding minimum and maximum values. Here’s a sample of the data: ...
Shibaprasad's user avatar
0 votes
1 answer
28 views

Grouping of a list of elements in fixed order to maximize the total return of all the groups

I'd like to ask about if there's an existing type of problems that fits to my question. (Searching it for a while but cannot get to the point) Basic Problem Description: Given a sequenced list (order ...
X.Arthur's user avatar
  • 103
0 votes
0 answers
51 views

Better formulation of bilinear terms

I am working on an optimization problem where I need to formulate a constraint that represents the total sales value under specific conditions. The challenge lies in creating an expression that ...
Lemma's user avatar
  • 23
1 vote
1 answer
119 views

How do I linearize such a constraint?

I was wondering, how one would linearize such a constraint, to make it applicable to LPs. $ a_{i}=(a_{i-1}+b_{i})(1-c_{i})-d_{i}$ $a_i$ gives information of the number of assigned jobs to machine $i$. ...
manofthousandnames's user avatar
2 votes
3 answers
155 views

Grouping values based on a difference constraint

I am trying to write an MILP to do a grouping (clustering) given one difference condition. Suppose, I have the following elements in a list: 1,2,3,4,6,8,9,10. My goal here is to group them so that the ...
Shibaprasad's user avatar
0 votes
1 answer
51 views

Warehouse placement problem in

I’m curious about the warehouse placement problem. Suppose N nodes exist, each with average demand across all products (or a single product for simplicity.) the problem is to position M warehouses ...
jbuddy_13's user avatar
  • 519
1 vote
1 answer
91 views

Logical conditions

This is similar to question I asked here: Priotization rules for variable allocation in linear programming. In an optimization problem, the goal is to manage the purchase and sale of items under ...
Lemma's user avatar
  • 23
0 votes
0 answers
70 views

Cost function value of relaxed ILP after rounding is less than or equal to the optimal one

I have a minimization problem for which I am having some misunderstandings and confusions with regard to some results I am getting for an ILP and its LP relaxation. In the ILP I have two decision ...
LyLa's user avatar
  • 1
1 vote
2 answers
113 views

Priotization rules for variable allocation in linear programming

I’m working on an optimization problem and need help with correctly prioritizing the allocation of certain variables in a constraint. The rules are: Only one of the variables $y_{t}$, $zn_{t}$ and $...
Lemma's user avatar
  • 23
1 vote
1 answer
52 views

Modelling set of binaries as SOS1

H.P. Williams states in his book "Model Building in Mathematical Programming: "An SOS1 is a set of variables (continuous or integer) within which exactly one variable must be non-zero." ...
Clement's user avatar
  • 2,224
2 votes
2 answers
69 views

Algorithm for Shortest Path in a DAG with Multiple Transportation Modes and Associated Setup Costs

I am working on a problem involving finding the shortest path in a Directed Acyclic Graph (DAG), where each edge's cost depends on multiple transportation modes, each with its own setup cost. I am ...
Changxin Cao's user avatar
0 votes
0 answers
71 views

Removing min operator from max objective

I am reading a paper where the authors made the following statement on page 16: I wonder why dropping the 'min' operator inside a 'max' objective function is a valid operation here. Any explanation ...
Apurba Saha's user avatar
2 votes
2 answers
318 views

How to model weekend constraints in a nurse rostering problem?

I have the following problem. I have a Nurse rostering problem and want to model the following. I have the indices $D$ (days), $I$ (nurse), $S$ (shift). My planning period $D$ is 28 days. Now I want ...
Uni ewr's user avatar
  • 21
2 votes
1 answer
76 views

Help with choosing the penalty parameters in the objective function

I'm working on a MIP optimization problem where I'm trying to reorganize a list of purchases (negative integer numbers) and requests (positive integer number) to maximize the number of positive values ...
Caterina De Franco's user avatar
1 vote
0 answers
43 views

How to model membership to a set using MILP?

Consider the following problem. I have two regions $X1=[a,b]$ and $X2=[b,c]$. Notice that they are disjoint except for point $b$. I have a continuous variable $x$ and two binary variables, $y_1,y_2$ ...
k88074's user avatar
  • 1,661
0 votes
0 answers
54 views

Dealing with a problem that contains a specific structure with a standard MILP solver

Suppose we have a specific formulation in which contains a special structure. For example, the formulation has a block diagonal format with some linking constraints. As far as I know, this format ...
A.Omidi's user avatar
  • 8,642
1 vote
2 answers
114 views

Capacited Vehicle Routing Problem with flow formulations

I'm trying to solve the CVRP based on flow-formulation. In such a model, we have a decision variable with two-index, $x_{ij}$, where I'm using the MTZ formula to eliminate sub-tours. We have then a ...
MAYA's user avatar
  • 125
0 votes
2 answers
89 views

Extracting a sequence as a decision variable from a matrix (PuLP)

I am solving a sequencing problem x[i][j], i.e. a binary matrix indicating that product i is followed by ...
Jigeli's user avatar
  • 11
1 vote
1 answer
105 views

Column generation for solving minimum cost multicommodity flow problem with additional edge disjoint constraints

I'm working on an integer programming problem that's fundamentally a minimum cost multicommodity flow (MCMF) problem with additional constraints. I'm exploring the use of column generation to solve it,...
Sina_Alef's user avatar
0 votes
0 answers
55 views

Workforce scheduling optimization using ML model output

I am working on a workforce scheduling problem where we want to come up with an intelligent way to identify a set of shift candidates that is just enough to cover all labor demand but also flexible ...
SDC's user avatar
  • 33
1 vote
3 answers
179 views

Formulating a constraint to select the minimum value of an index

To provide a clear description of my problem, let me outline the scenario. I have a binary variable $\phi_{k,c}$ where $k$ is an index belonging to the set $\{1, 2, 3, ..., 9\}$. As an example, for a ...
Liu Fan's user avatar
  • 11
0 votes
1 answer
61 views

MIP binary decision value under a condition if else

In MIP, I have a constraint that is validated only if the demand $d_i\leq Q$: C1 : $d_i \leq x_i \leq Q$ where $x_i \geq 0$. I tried to introduce big M with binary variables as follows: $My \leq x_i \...
MAYA's user avatar
  • 125
0 votes
1 answer
123 views

Question on Column generation

I am implementing a Column Generation algorithm to solve a set partitioning problem. The master problem takes the form : $\min \sum_{i \in I} c_i \lambda_i$ s.t $\sum_{i \in I} a_{ji} \lambda_i = 1, \...
CHE's user avatar
  • 113
1 vote
0 answers
33 views

Calling Cplex from R through a MPS-like file

I have a working - and long - R code to generate a mps file to be read by cplex. Because I work with large instances I am finding troubles (too much time) in producing a large mps file. Is there a way ...
Di Al's user avatar
  • 11
3 votes
1 answer
93 views

How to modify Benders decomposition to handle overlapping or shared variables among the subproblems

I have a problem that can be separated into a master problem and two subproblems, SP-A and SP-B. SP-B share some variables with SP-A, and the shared/overlapping variables from SP-A cannot be fixed for ...
user4444's user avatar
1 vote
1 answer
115 views

Which of these formulations has the tightest linear relaxation ? (Part 2)

This is a follow up question of this question, in which it was asked to compare the "tightness" of two models: I have a sequence of binary variables $x_i$ and want to enforce consecutive $1$...
abcd's user avatar
  • 55
1 vote
2 answers
221 views

Which of these formulations has the tightest linear relaxation?

I have a sequence of binary variables $x_i$ and want to enforce consecutive $1$'s of length at least $3$. I have $2$ formulations: Model $1$ (from here): \begin{align} x_i \le x_{i-1}+x_{i+1} \tag{1}\...
abcd's user avatar
  • 55
5 votes
2 answers
197 views

How to combine MIP solver with a CP one?

I am working on the scheduling problem in the class of parallel resource scheduling models. When I have studied some papers regarding that, I see the method that combines an MIP with a CP. The ...
A.Omidi's user avatar
  • 8,642
3 votes
0 answers
123 views

Continuous optimization with a Euclidean TSP objective

I am trying to solve a problem of the form $$\min_{x_1,\dots,x_n} f(x_1,\dots,x_n)$$ subject to a constraint that $\mathrm{length}(\mathrm{TSP}(x_1,\dots,x_n))\leq c$, where $x_1,\dots,x_n$ are all ...
Tom Solberg's user avatar
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
2 3 4 5
20