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
0 votes
0 answers
1 view

Limit the time in the root node

I have a hard problem where I fix some variables to solve it. However, the time elapsed in the root node is high. Is there a way to limit this time anf force the Gurobi start the ramification? I have ...
Angelo Aliano Filho's user avatar
1 vote
1 answer
28 views

Optimal way to formulate a piecewise linear function

I am working on LP problem whose objective function includes a piecewise linear function. I would like to figure out the optimal way to formulate the piecewise linear function in order to minimize the ...
Apostolos's user avatar
2 votes
0 answers
35 views

Total Unimodularity of constraint matrix

Given a directed graph $G=(V,E)$, I have the following integer program- \begin{align} \max & \sum_{(u,v) \in E} \sum_{s \in S} w_{uv} z_{uv,s} + \sum_{v \in V} \sum_{s \in S} b_{v,s} x_{v,s} \\ \...
superhulk's user avatar
  • 203
3 votes
1 answer
62 views

Enforcing Order in a Linear Programming Question

I have an optimization model to fulfill the water requirements of a city's distribution network. The model includes water sources from rainfall collection, river extraction, reservoir storage, and ...
snek's user avatar
  • 31
1 vote
1 answer
38 views

Multi-Commodity Flow with "group edges"

I'm currently working on a special variation of the Multi-Commodity flow problem. My goal is to solve this variation via column generation, because the graph can become very large. Description Given......
jatsqi's user avatar
  • 13
0 votes
0 answers
28 views

What are the "cutoff values" in Hybrid Branching?

In "Hybrid Branching" by Achterberg and Berthold, we have this line: the number of subproblems that could be pruned due to branching on this variable, called the cutoff values Can you ...
Brannon's user avatar
  • 900
1 vote
0 answers
37 views

The first reference which formulated k-means problem as MIQCP using big-M constraint

k-means, or MSS (minimum-sum-of-squares) clustering is a basic problem in statistics. To remind, for a set of points $P_1, P_2, \dots, P_N$ in $\mathbb{R}^d$, the problem is to find $K$ centres $Q_1, ...
MindaugasK's user avatar
3 votes
0 answers
34 views

To "fix" continuous variables in Benders decomposition

In nearly all applications I have seen, the master problem variables $x$ that define the subproblem are binary. (Logic-based) Benders decomposition can applied to a problem of the form: $$\min_{x,y} f(...
Pavel's user avatar
  • 31
0 votes
0 answers
32 views

Reformulations for a linear program with absolute values in the objective function

I am looking for suggestions on improving the formulation of the following problem: $\max_{\vec{x} \in \mathbb{R}^{2^n}} \sum_{i=1}^{2^n}\lvert x_i \rvert$ such that $\vec{x}$ is in the feasible ...
jtamiyo's user avatar
  • 11
2 votes
1 answer
121 views

Avoid double counting in objective function for a maintenance scheduling problem

I have a problem to do with machine maintenance scheduling which I have formulated as a MIP where I have a binary variable $x_{ijt}$ which is 1 if the maintenance job j is scheduled on the same ...
Demitri's user avatar
  • 33
6 votes
2 answers
1k views

Multiple Travelling Salesmen - How to make the second slowest salesman matter?

I'm building a Mixed Integer Linear Program for a variant of TSP I'm dealing with, where there are multiple salesmen. The way I have formulated the problem is that each agent has a time variable $T_i$ ...
John Smith's user avatar
2 votes
0 answers
40 views

Optimization under cardinality constraint

When we consider the following optimization problem: \begin{equation}\label{P}\tag{P} \begin{array}{ll} \displaystyle\min_{x \in \mathbb{R}^n} & f(x) \\ \text{s.t.} & Ax = b,~ x \geq 0, \\ &...
Optimization Online's user avatar
1 vote
0 answers
37 views

Using the Alternative Cut Generation Problem in Benders, why do I get different results?

I am using Benders' Decomposition to solve a stochastic MIP. To improve cut selection, I implemented the Alternative Cut Generation Problem as proposed by Fischetti et al. (2010). I will summarize the ...
Arctic_Skill's user avatar
0 votes
0 answers
23 views

Getting solution status as Unknown status value in callback (lazyconstraints) for docplex with Python to solve MILP

from docplex.mp.model import Model from cplex.callbacks import LazyConstraintCallback from docplex.mp.callbacks.cb_mixin import * p_id is the list of lists of customers, n is the set of vehicles, dth ...
Mohammad Samiullah's user avatar
0 votes
1 answer
41 views

Column Generation for non/single capacitated routing problems

Introduction The strategy here documented was applied before for the TSP: Column generation for TSP https://coin-or.github.io/jorlib/manual/manual.pdf (Section 4, page 18); And https://www.jstor.org/...
Matheus Diógenes Andrade's user avatar
1 vote
1 answer
30 views

Traverse discrete approximations to a continuous system

I have a system of equations looking like $$ \frac{2.8 R_{6}}{R_{4} + R_{6}} = \frac{5.2}{\left(\frac{1}{R_{2}} + \frac{1}{R_{1}}\right) \left(R_{7} + \frac{1}{\frac{1}{R_{2}} + \frac{1}{R_{1}}}\right)...
Reinderien's user avatar
3 votes
1 answer
195 views

How to linearize the following logical constraints?

I am having trouble linearizing the following logical constraints. $x,y,z$ are non negative continuous variables such that $x=y+z$, and $A$ is a positive parameter. I would like to linearize $$ y= \...
NormalFit's user avatar
1 vote
0 answers
84 views

what should I do to avoid scipy.minimize solver from computing infeasible models as much as possible

Python==3.9.5, scipy==1.13.0 My model has some variable coefficients in each round of calculation. for example, for a four-dimensional decision variable ...
CangWangu's user avatar
3 votes
2 answers
817 views

How to avoid similar solutions?

I have a problem like this $x_1 +x_2 +x_3 =10$ let's assume $0 \leq x_i \leq 10$ It is obvious that this problem has more than one solution For example : Solution 1 : $x_1 =0 , x_2= 1 , x_3 =9$ ...
Optimization team's user avatar
0 votes
1 answer
28 views

Adding additional coordinating constraint to a decomposed model

As suggested by @RobPratt, here is the new opened question. I have these decomposed master and subproblems: \begin{align} &\text{minimize} &\sum_t \sum_s \text{slack}_{ts} \\ &\text{...
nflgreaternba's user avatar
8 votes
1 answer
1k views

Why do I get a binary solution even when I solve an LP problem with continuous variables?

I have a MILP in the following form maximize $${\bf c}^T{\bf x}$$ subject to $${\bf Ax}\le {\bf b}$$ Matrix ${\bf A}$ is a binary matrix, and very sparse. It is a larger matrix with 300 rows and 1000 ...
KGM's user avatar
  • 2,377
2 votes
2 answers
87 views

Optimizing calls to a separation problem in branch and cut

I have a MIP in which I am able to generate cuts at intermediate relaxation solutions using the context class. These cuts are derived from a separation problem. However, after adding them, the code ...
tr244's user avatar
  • 21
1 vote
0 answers
62 views

Getting error in callback (lazy constraints) for docplex with Python to solve MILP

I am trying to use lazy constraints to solve my MILP problem. The details are given as follows. ...
Mohammad Samiullah's user avatar
2 votes
1 answer
75 views

Minimizing sum(abs(Ax-c)) for binary decision variables - terminology and methods?

My problem requires choosing a fixed number of vectors from a large set of vectors such that the sum of these vectors is close to some known target vector. That is, given known parameters: $$ l, m, n \...
G_B's user avatar
  • 1,857
5 votes
0 answers
57 views

Gurobi - Is finding a feasible solution when optimizing a lot harder than finding a feasible solution?

The code is working fine but I feel as my intuition could be wrong. I first set up my problem as: $$\min_{f(x)\leq F} g(x) $$ and gurobi was unable to find a feasible solution. I then relaxed ...
John's user avatar
  • 51
3 votes
1 answer
104 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
94 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
96 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,960
1 vote
1 answer
79 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
43 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
56 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
45 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
107 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
42 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
40 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
81 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,377
0 votes
0 answers
104 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
86 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
  • 33
0 votes
0 answers
74 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
1 answer
128 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,960
0 votes
1 answer
63 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
86 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
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
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
58 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
67 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

1
2 3 4 5
21