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
1 answer
46 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 (...
Anton Ruby Larsen's user avatar
3 votes
1 answer
107 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 ...
A.Omidi's user avatar
  • 9,046
0 votes
0 answers
37 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 ...
eight3's user avatar
  • 489
0 votes
1 answer
98 views

What is the best open-source solver for large-scale MILP optimization?

Currentlly, I am using ortools with SCIP/CBC solvers for a large scale optimization problem, which turned out to be quite slow. The integer part of my problem is due to a piece-wise linear function in ...
Apostolos's user avatar
0 votes
0 answers
46 views

Cost Function in a Gas Market Model

I am trying to formulate the correct objective function for the following problem: Minimize the total cost in a gas market from the perspective of the consumer. There are storage from which you can ...
Apostolos's user avatar
1 vote
1 answer
52 views

MILP Model for Assigning Unique Number for Each Point

I am trying to solve a problem which is smilar to sudoku. I have a specific device location on map I need to gave them a unique integer numbers. However, as in the sudoku I can assign up to 9 and ...
Serkan's user avatar
  • 11
1 vote
1 answer
135 views

How to avoid division by zero with a binary variable at the denominator in a network assignment problem?

I am currently working with some network assignment problem as a network engineer. My engineering application can be stated as follows: There are $M$ users that needs to be assign to $N$ servers. This ...
Tuong Nguyen Minh's user avatar
2 votes
2 answers
491 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 ...
Erel Segal-Halevi's user avatar
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 ...
Angelo Aliano Filho's user avatar
2 votes
1 answer
61 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
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} \\ \...
superhulk's user avatar
  • 223
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 ...
snek's user avatar
  • 31
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......
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
  • 920
1 vote
1 answer
54 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
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(...
Pavel's user avatar
  • 31
0 votes
0 answers
36 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
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 ...
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
1 answer
61 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
37 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
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/...
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
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= \...
NormalFit's user avatar
1 vote
0 answers
85 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
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$ ...
Optimization team's user avatar
0 votes
1 answer
36 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
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 ...
tr244's user avatar
  • 21
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. ...
Mohammad Samiullah's user avatar
2 votes
1 answer
78 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
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 ...
John's user avatar
  • 51
3 votes
1 answer
113 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
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_{...
mingabua's user avatar
0 votes
0 answers
97 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
  • 9,046
1 vote
1 answer
85 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
57 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
108 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
84 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
106 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
88 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

1
2 3 4 5
21