Skip to main content

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
8 votes
1 answer
137 views

Is there any way to use Lazy constraints in Pyomo?

I would like to know if there is any way to implement a Lazy constraint in the Pyomo package. (As far as I know, the only way to implement such a constraint is by ...
A.Omidi's user avatar
  • 9,046
0 votes
1 answer
75 views

Minimize Expenses For Workers

My goal is to minimize the labor expenses. Say we have 3 types of workers: $x_1$ = Permanent Driver, rate = 693.875/day $x_2$ = Reliever Drivers rate = 435/day $x_3$ = Crews rate = 400/day There are 6 ...
Siazam's user avatar
  • 1
1 vote
1 answer
88 views

How to model $\max\limits_{x\in X} \min\limits_{y\in Y} \max\limits_{z\in Z} f(z)$ as single MILP

I have the following optimization problem: \begin{align*} \max\limits_{x\in X} &\min\limits_{y\in Y} \max\limits_{z\in Z} & f(z) \\ &\text{such that} & (x, y, z)\in P \end{align*} ...
graphtheory123's user avatar
2 votes
1 answer
66 views

How to deal with performance bottlenecks in Stochastic Vehicle Routing Problem with Benders' decomposition?

I've been working on solving a stochastic vehicle routing problem using Benders' decomposition with CPLEX in C++. Initially, my implementation struggled with larger instances, but I've made ...
Arctic_Skill's user avatar
0 votes
0 answers
73 views

Improving the lower bound

Good afternoon. I have a very difficult to a MIP model. I have tried several different strategies to reduce the gap. I am using Gurobi and in this case, I already have an incumbent solution. I've set &...
Angelo Aliano Filho's user avatar
0 votes
1 answer
51 views

multiple shifts per day constraint for a workforce scheduling problem

This is an extention to the workforce scheduling problem discussed in this thread Workforce scheduling problem. Adding a new post to discuss an important new requirement in this model. So the new ...
SDC's user avatar
  • 33
0 votes
1 answer
59 views

How to linearize this L0 norm of a vector?

I have an QP optimization problem. $\bf x$ is the binary optimizaion variable of size $12\times 1$. One of the constraints is non-linear/non-convex. The constraint is L0 constraint. The constraint I ...
KGM's user avatar
  • 2,377
1 vote
1 answer
68 views

Connections between Bounds in MIPs

we are currently learning about MIP/MILP minimization at university and have become familiar with the branch-and-bound algorithm. Unfortunately, the relationship between upper bound, lower bound and ...
Vv J's user avatar
  • 19
2 votes
1 answer
120 views

Modelling L-0 norm of a vector

I have a binary variable $\bf x$ of length 4000. Let ${\bf x}=[x_1,x_2,\cdots, x_{4000}]$. Let's say we have ${\bf y}=[y_1,y_2,y_3,y_4]$, where \begin{align} y_1&=x_1+x_5+x_{9}+\cdots+x_{3997} \\ ...
KGM's user avatar
  • 2,377
0 votes
0 answers
40 views

Projection of QP problem solved with Gradient Descent

Lets say we have a QP problem as shown below $$\min {\bf x}^T {\bf R}{\bf x}+{\bf c}^T{\bf x}$$ subject to $${\bf A_{eq}x}={\bf e}_{eq}$$ $${\bf Ax}\le {\bf e}$$ $${\bf x}\in \lbrace 0,1\rbrace$$ ${\...
KGM's user avatar
  • 2,377
0 votes
1 answer
89 views

How to model this constraint for a QP problem?

I have a system with 100 users. There are 6 resources. At any point of time, only 2 resources are made available and those resources can be shared among the users. Some users may not get any resource, ...
KGM's user avatar
  • 2,377
0 votes
2 answers
75 views

How to write a If then else constraint with continuous variables

I have a problem under investigation which requires if, elseif and else conditions to implement as a constraint in a mixed integer program. Any leads will be appreciated. Thanks a lot. Let $x_t$, $y_t$...
Srinivasan B's user avatar
0 votes
0 answers
50 views

Local Branching in Branch-And-Price

Is it somehow possible to apply local branching in branch-and-price? In branch-and-bound it is easy to add a constraint that allows at most k decision variables to change compared to a given solution. ...
GeoRie's user avatar
  • 1
0 votes
0 answers
116 views

why this little constraint changes my whole program?

I'm trying to linearize a CP in ILOG CPLEX. I have the following constraint that I want to linearize (I already simplified it with the big M) : ...
Marcocorico's user avatar
0 votes
0 answers
62 views

How to model constraints without introducing additional variables?

I have a binary variable $\bf x$ of size $12\times 1$, such as ${\bf x} =[x_1\hspace{1mm} x_2\hspace{1mm} x_3\hspace{1mm} x_4\hspace{1mm} x_5\hspace{1mm} x_6\hspace{1mm} x_7\hspace{1mm} x_8\hspace{1mm}...
KGM's user avatar
  • 2,377
2 votes
1 answer
121 views

Optimizing a Route Selection Problem with Multiple Constraints and Objectives

I'm developing a solution to optimize a vehicle routing problem where each stop has an associated score (priority), specific geo coordinates, and a required stop duration. The goal is to maximize the ...
Rastislav's user avatar
  • 131
2 votes
1 answer
55 views

Temporal changing model parameters/constraints/variables in MILPs

In general, I can compute an MILP using a solver of my choice (Gurobi, ...) and stop it at any time, change parameters/constraints add variables. Take the so far best solution computed based on the ...
baxbear's user avatar
  • 319
1 vote
0 answers
24 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
  • 319
0 votes
2 answers
126 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
  • 97
1 vote
0 answers
101 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
244 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
41 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
  • 741
2 votes
1 answer
153 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
  • 741
3 votes
1 answer
133 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
  • 741
0 votes
1 answer
127 views

Exploiting identical subproblems in column generation

As suggested, this is a new post. I have the following column generation model. The notation is as follows: $i\in I$ refers to the nurses, $t\in T$ to the days and $s\in S$ for the shifts. With the ...
nflgreaternba's user avatar
1 vote
1 answer
112 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
46 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
101 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
128 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
90 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
  • 525
3 votes
1 answer
125 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
186 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
464 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
116 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,252
0 votes
1 answer
67 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
232 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
65 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
30 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
58 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
141 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
166 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
57 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
  • 551
1 vote
1 answer
97 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
75 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
117 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
79 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,252
2 votes
2 answers
87 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
72 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
335 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
  • 71
2 votes
1 answer
94 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
2
3 4 5
21