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
3 votes
1 answer
78 views

Restrict the number of non-zero variables to any constant in MILP

I am designing an MILP in which given a set $[n]$ of $n$ agents, we create for each $i \in [n]$ a real variable $x_i$. The variables $x_i$ are between 0 and 1 ($0 \leq x_i < 1$). I would like to ...
Samuel Bismuth's user avatar
1 vote
1 answer
90 views

Conditional binary programming

I am currently trying to model the relationship that if the binary variables $b_{it}=0$ and $c_{it}=1$, and for the integer non-negative variable $b^{n}_{i(t-1)}=0$, then the new binary variable $a_{...
mingabua's user avatar
0 votes
0 answers
88 views

Tightening a specific constraint

I would like to know if there exists any way to reformulate the following constraint in which one can relax the binary variable $z_{j,m}$, and the solution still being an integer for that. The ...
A.Omidi's user avatar
  • 8,950
1 vote
1 answer
57 views

How to achieve recording the change of objective or primal gap in solving MILP by SCIP?

I am a solver beginner, would like to ask you how to call the solver to achieve second-level recording, as documented in many articles, as shown below.
Paul's user avatar
  • 11
0 votes
0 answers
32 views

How to correctly use legacy callbacks in CPLEX with C++ to generate Benders' cuts?

I've been working on implementing Branch-and-Benders Cut using CPLEX version 20.1 with the C++ API, but I'm encountering some difficulties. I've followed the example provided by CPLEX, specifically ...
Arctic_Skill's user avatar
1 vote
0 answers
54 views

Does getting the second optimal solution in a general MILP require solving a MILP again?

This general question popped into my mind if finding all optimal solutions takes not much more time than finding just one optimal solution in a MILP why not gettting all of them in Gurobi?
Red shoes's user avatar
  • 153
0 votes
0 answers
44 views

Constraint formulation in MILP AGV Scheduling (using CPLEX)

I am currently working on a MILP formulation for optimizing AGV/AMR scheduling. The model aims to optimize task scheduling across multiple missions using a limited set of resources. Parameters such as ...
Rami's user avatar
  • 1
0 votes
3 answers
98 views

How do I convert Integer Programming to Constraint programming?

/********************************************* OPL 12.10.0.0 Model Author: Shahrukh Creation Date: 10-Apr-2024 at 11:55:50 PM The podrace tournament involves n competitors (where n is even) who all ...
Shahrukh Mohd's user avatar
0 votes
0 answers
24 views

Defining augmenting path for Traveling salesman problem

I am currently looking into solving TSP using Branch and Bound method. In the book by Wayne and Winston, they have solved each subproblem (i.e. tree nodes) using Hungarian algorithm. Using the lecture ...
jayant's user avatar
  • 109
0 votes
1 answer
39 views

How can I calculate the UB if I'm using Fischetti's Alternative Cut Generation for Benders'?

Assuming I have a stochastic MIP that I want to minimize using Benders' Decomposition. With the objective of the MP being: $$ Minimize \; cx + \frac{1}{\lvert S \rvert} \sum_{s \in S} \theta_s $$ ...
Arctic_Skill's user avatar
0 votes
0 answers
39 views

Network formulation based side constraints for a workforce scheduling problem

For a workforce scheduling problem, I have formulated the "at most one shift per day" constraint as a network formulation based side constraint (with other constraints like demand coverage, ...
SDC's user avatar
  • 33
2 votes
1 answer
79 views

Is the linearization with first-order Taylor approximation correct?

I have a QP problem as $\min \hspace{2mm} x^TQx-c^Tx$ here $x$ in binary I want to transform it into a MILP by writing the objective function as $\min \hspace{2mm} z-c^Tx$ and then adding a constraint ...
KGM's user avatar
  • 2,297
0 votes
0 answers
102 views

Need Help for building two constraints in MIP model

Really need help for building two constraints with MIP model, I have written the required information and variable information on the diagram below. The way I think of it now is to use two ...
CangWangu's user avatar
1 vote
1 answer
78 views

How to track the first timestep at which a binary variable becomes 1 in an IP? [duplicate]

I have an MIP where I have a binary variable $y_t$ which is set to 1 or 0 and is indexed by time t. It can be set to 1 at multiple timestamps but it is never continuously 1 for more than single ...
Demitri's user avatar
  • 11
0 votes
0 answers
71 views

How to constrain variables to fit a normal distribution

Given a time series $s_t$, I would like to define for each $t$ a perturbation $e_t$ such that the set of all $e_t$ "fits" (within some range) a normal distribution with mean $\mu=0$ and a ...
NormalFit's user avatar
1 vote
1 answer
78 views

How to deal with mixed linear integral optimization problem with extra nonconvex but differentiable constraints?

I got a model of MILP but I want to add extra constraints. $$ \min\{c^T x + d^T y:Ax+By=a,Cx+Dy \leq b,x,y\geq0,y \in \{0,1\}\} $$ More specificlly, I got extra original constraints with indicator ...
Kaiming Zhang's user avatar
0 votes
1 answer
36 views

Add second "constraint" to model a binary variable

in my model I have the binary variable $f_{ij}$ which pushes a time-dependent $j$ integer variable $D_{ij}$ to zero if $f_{ij}$ takes the value 1 and keeps the integer number if $f_{ij}$ equals 0. Yes,...
marvelfab12's user avatar
8 votes
0 answers
83 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
  • 8,950
0 votes
0 answers
40 views

Minimize expenses for workers

My goal is to minimize the labor expenses. Say we have 3 types of workers: x1 = Permanent Driver, rate = 693.875/day x2 = Reliever Drivers rate = 435/day x3 = Crews rate = 400/day There are 6 trucks ...
Siazam's user avatar
  • 1
1 vote
1 answer
82 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
65 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
71 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
47 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
55 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,297
1 vote
1 answer
66 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
115 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,297
0 votes
0 answers
37 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,297
0 votes
1 answer
84 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,297
0 votes
2 answers
72 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
47 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
60 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,297
2 votes
1 answer
114 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
54 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
121 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
96 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
241 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
  • 679
2 votes
1 answer
150 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
126 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
0 votes
1 answer
124 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
109 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
121 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
87 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
116 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
146 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
435 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
2 3 4 5
20