# Questions tagged [mixed-integer-programming]

For questions about mathematical optimization problems involving both continuous and binary or general integer variables.

1,026 questions
Filter by
Sorted by
Tagged with
72 views

### How to reformulate the BigM constraints into its equivalent Convex-hull formulation?

I am trying to work on a scheduling problem based on its polyhedron reformulations. For that, I would like to reformulate a BigM model into its equivalent C-hull formulation. The transforming map is ...
43 views

### Linearization of two constraints: one with a conditional max and one with a sum with a variable as index

I have these two quite nasty constraints I have tried to linearize. I am trying to dynamically control if you are allowed to plan producing product p. You are allowed to do it if the product arrived (...
36 views

### Mixed integer optimization: what if X has to be a rounded multiple of a fixed value? [duplicate]

I am working on a Mosek project. The utility function is to maximize u^{t} x where x is a vector of N There is a tricky constraint: the first 3 items of X must be ...
185 views

488 views

### Can I tell a MILP solver to prefer solutions with fewer fractions?

I have a linear program $$\max c^T x \text{ s.t. } A x\leq b, x\geq 0.$$ I would like a solution that, among all optimal solutions, has the largest number of integer variables. For example, if the ...
61 views

### Optimization under cardinality constraint

When we consider the following optimization problem: \label{P}\tag{P} \begin{array}{ll} \displaystyle\min_{x \in \mathbb{R}^n} & f(x) \\ \text{s.t.} & Ax = b,~ x \geq 0, \\ &...
36 views

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{...
1 vote
54 views

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, ... 0 votes 0 answers 52 views ### 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 ... 2 votes 1 answer 58 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 ... 8 votes 1 answer 135 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 ... 4 votes 0 answers 43 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} \\ \... 3 votes 1 answer 87 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 ... 1 vote 1 answer 47 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...... 1 vote 1 answer 126 views ### How to linearize the waiting time My question is this: I want to express the time it takes for multiple servers to complete tasks for multiple users. I divide the time intot$time slots, and each task may occupy multiple time slots. ... 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 ... 3 votes 0 answers 38 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(... 0 votes 0 answers 35 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 ... 2 votes 1 answer 123 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 ... 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 ... 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 ... 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 ... 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 ... 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)... 0 votes 2 answers 108 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 ... 0 votes 1 answer 42 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/... 3 votes 1 answer 199 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= \... 3 votes 2 answers 834 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 ... 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 ... 2 votes 2 answers 91 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 ... 2 votes 1 answer 76 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 \... 1 vote 0 answers 70 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. ... 1 vote 3 answers 219 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 ... 1 vote 2 answers 102 views ### In a routing and scheduling problem with break consideration, How can I determine whether a node is met before a break or after it? I'm working on a routing and scheduling problem in the home care services context. I consider a break as a dummy patient, so routing and scheduling are also implemented for the break node (with some ... 5 votes 0 answers 58 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 ... 3 votes 1 answer 111 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 ... 5 votes 1 answer 162 views ### Numerically stable way to optimize a lexicographical preference between two objective functions? I am solving a mixed-integer program whose decision variables are$x \in \{0, 1\}^n$and$y \in \mathbb{R}^m$, where$0 \leq y_j \leq u_j$for constant upper bounds. My primary objective function is ... 1 vote 2 answers 185 views ### Help with Mathematical Formulation for VRP with Specific Constraints I am currently working on a Vehicle Routing Problem (VRP) with a set of specific constraints. I have a total of 19 nodes, each representing a customer location, and a depot. There are also 7 pickers ... 1 vote 1 answer 97 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_{...
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 ...