Questions tagged [mixed-integer-programming]
For questions about mathematical optimization problems involving both continuous and binary or general integer variables.
140
questions with no upvoted or accepted answers
12
votes
0
answers
165
views
which method has been used to automatically reformulate logical constraints in a standard MIP solver?
There are many of the formulations to linearize logical constraints by introducing new auxiliary binary or any appropriate variables and adding the corresponding constraints to the model. It can be ...
- 8,450
9
votes
0
answers
214
views
Solving large-scale stochastic mixed integer program
What are some methods or algorithms for solving a large-scale stochastic mixed-integer optimization problem that runs on an hourly dataset for a year? Do we employ some kind of decomposition? (the ...
- 793
8
votes
0
answers
108
views
For subset selection regression as a mixed integer program, how tightly should the bounding box be set?
When solving best subset regression as a mixed integer program, how do you decide how tightly to bound the range of values of the $X$ values? When the box is tight, the solver finds a solution ...
- 261
7
votes
0
answers
99
views
MIP formulation for graph planarity test
In this question, it was asked wether a MIP formulation exists to test for a graph's planarity. The inputs are the graph's nodes and edges, and the output would be a certificate which guarantees that ...
- 12.9k
7
votes
0
answers
91
views
Building the Scheurman's Model II constraints for a multi period linear program
Scheurman's paper discusses Model I and model II Formulation to solve harvesting and scheduling problems. It is a specific implementation to solve multi period linear programs. Both models are also ...
- 153
7
votes
0
answers
81
views
Modelling a simple ordering problem to have balanced delivery days
Assuming that I should buy 50 items from 25 different vendors with pre-known delivery duration between 2-7 day for each, which day of a week should I place each order so that the delivery days be even ...
- 159
6
votes
0
answers
208
views
Benders decomposition for a dense MILP
I am trying to solve a large MILP, but it seems like dense problems can be very difficult for moderns solvers. I tried to solve the problem described below considering only constraints (1) and (2) ...
- 109
6
votes
0
answers
86
views
Issue of Dense columns in the formulation
I'm working on a price-selection model where we need to identify price point for each time-period (could be day/week). Objective of the model is to figure out optimal price-point for each time-point ...
- 974
6
votes
0
answers
126
views
Water quality component optimization
I have an optimization problem that I'm attempting to tackle. As you can see in the image below, there's a graph network through which water flows. I've drawn out the problem in the image to explain ...
- 61
6
votes
0
answers
53
views
What are useful plots/statistics/metrics when analyzing the solution sensitivity in multi-objective optimization?
Consider an optimization problem with $n>3$ objectives.
For handling this there exists often two approaches:
a) some weighting of the objectives,
b) fix an order of objectives and then optimize ...
- 3,635
6
votes
0
answers
174
views
Benefits of removing slack variables during presolve
I was reading Tobias Achterberg's thesis, and on page 138 he mentions the following presolving technique for linear equations (I'm slightly paraphrasing Example 10.2):
Consider the equation $4x_1+...
- 11.9k
6
votes
0
answers
81
views
Data Formulation for Mixed-Integer-Programming Models
Until now, I have used the Gurobi, CPLEX and OR-Tools (GCO) interface to formulate mixed-integer-programming models.
Recently, I have discovered MiniZinc and want to utilize it to formulate big ...
- 1,193
6
votes
0
answers
585
views
Cplex is stuck after root node relaxation solution
I am solving an MIP through Benders decomposition (coded both generic and legacy callback versions), by employing Java with Cplex 12.9. For some of the instances, Cplex is stuck for two hours (time ...
- 61
5
votes
1
answer
88
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 ...
- 534
5
votes
0
answers
120
views
Reduce overhead Gurobi Python getting and setting attributes
I am using Gurobi 9.5.1 in Python 3.10. In the context of column generation I request the duals of the master problem and set them in the objective of the subproblem. This is done repeated times.
<...
- 51
5
votes
0
answers
61
views
Reference request — fishery yield optimization
I'm looking for references to do a review of research on managing fisheries in industry. I've seen adaptions of
population growth models which include some harvesting constant or function and was ...
- 309
5
votes
0
answers
170
views
Are there any good models for min-max vehicle routing problem?
I am trying to model a min-max VRP problem with multiple delivery vehicles and I have come up with a model using branch and cut but I do not think it is strong enough as it takes lot of time to ...
- 253
5
votes
0
answers
1k
views
What is the difference between root relaxation and LP relaxation
(I apologize. I saw this question but, I do not know these may be the same or not.)
I am trying to solve a MIP problem and have an issue about that. The problem's LP relaxation has the objective ...
- 8,450
5
votes
0
answers
110
views
Complexity of determining whether a LP or MIP is infeasible
What is the best complexity for the worst case scenario and the algorithm associated with it to determine if a linear programming (LP) is infeasible ? Further, what if we consider a mixed integer ...
- 51
5
votes
0
answers
677
views
Solver for Go Programming Laguage
Has anyone used MIP solvers (open source or commercial) with Go language https://golang.org/? I am looking for a solver for simple linear MIPs for network flows and set cover types of problems.
- 131
4
votes
1
answer
120
views
What's the best way to speed up Benders Decomposition for a stochastic vehicle routing problem?
Currently I am working on an implementation of Benders Decomposition that solves a stochastic vehicle routing problem with synchronisation constraints.
Sadly, at the moment it is not performing fast ...
- 161
4
votes
0
answers
156
views
Stochastic optimization for inventory management
The deterministic problem is to minimize operational cost subject to constraints in demand, supply and capacity. The ordering policy is periodic review, order-up-to.
The stochastic version of the ...
- 119
4
votes
0
answers
119
views
Modeling question on continuous variable that dependens on binary variables
Given a model with a binary variable $b_s$ that describes whether taking an item $s$ from a set $S$ or not. Consider that some other constraint in the model depends upon whether all items of the set ...
- 313
4
votes
0
answers
241
views
Simplified risk game: writing a pratical Minimax objective for mixed integer programming
Problem
To ensure fairness of the game, I am writing a bot that plays against itself. I have trouble rewriting a minimax objective to a practical maximization in mixed integer programming. The amount ...
- 523
4
votes
0
answers
76
views
Adding redundant inequality to a model
The following relationship is part of my optimization model ($W_k$ denotes a binary variable)
$$W_{1} \le \cdots \le W_{k-1} \le W_{k} \le W_{k+1} \le \cdots \le W_{k^{\max}}$$
My question is, do ...
- 2,180
4
votes
0
answers
71
views
Continue on "Is there a known MILP to schedule routes after routes are made"
I have made some progress on my previous question (Is there a known MILP to schedule routes after routes are made).
I have derived the sets of the problem, which are:
1) Itineraries of vehicle: $i \in ...
- 483
4
votes
0
answers
1k
views
cvxpy: Code that works for default solver doesn't work for cp.GLPK_MI
The following code works:
...
- 343
4
votes
0
answers
169
views
Publishing paper that uses LP solver to solve equation
I was reading this paper by Cerna et al. (2018)1. In the paper there are only CPLEX-solvable equations given by the authors and the results.
How valuable is this paper, and what is its quality? Can ...
- 1,589
3
votes
0
answers
111
views
From Quadratic to MILP?
I am playing around with some Quadratic Programs (QPs), and I want to check if my reasoning is right concerning a re-modeling from QP to MILP. So, let's consider the below QP:
(QP) $\min c^T x + x^T Q ...
- 1,208
3
votes
0
answers
114
views
Creating Disjunctions for MIP Model. Code taking too long to execute
I am currently following this guide in the hopes of building a linear programming model in python and solving using gurobi.
https://towardsdatascience.com/schedule-optimisation-using-linear-...
- 31
3
votes
0
answers
55
views
Separating two LP solutions at the same time
In a cutting plane algorithm for integer linear programming problems you would usually use an LP solver to get an extreme point of the polyhedron corresponding to the LP relaxation. Let's call that ...
- 6,352
3
votes
0
answers
124
views
When and where the cutting plane method should be applied?
As the cutting plan algorithm is a method to strengthen the feasible space of the linear programming, specifically in the MILP problems to invoke the integer solutions, it may be a problem-based ...
- 8,450
3
votes
0
answers
49
views
PWL constraints efficiency
So, I'm trying to optimize MILP, which has PWL constraints. I use gurobi, and when I'm optimizing model without those constraints, gurobi finds solution in a matter ...
- 161
3
votes
0
answers
56
views
Indeterminacy Reduction for MINLP
I am considering a Mixed Interger NonLinear Program (MINLP), and using a solver to obtain admissible solutions.
Is there a general method to reduce indeterminacy of solutions (e.g. by adding ...
- 424
3
votes
0
answers
98
views
Polynomial Time Solution For a Mixed-Integer Linear Programming Specific Case
Consider the following mixed-integer linear programming (MILP):
\begin{equation*}
\begin{array}{ll@{}ll}
\text{maximize} & 1 & \\
\text{subject to}& x_{i} \geq 0, &i=1 ,\dots, m\\
...
- 173
3
votes
0
answers
92
views
Extract/Inject Solutions (orig problem-space) during Search in MILP -> CoinOR Cbc
Task / Goal
I'm considering adding some customized problem-specific local-search component on top of a general-purpose MILP solver (= improvement heuristic).
The basic idea is the following:
All new ...
- 446
3
votes
0
answers
132
views
Harvest planning problem
I need to model the following problem:
For a planning horizon of $P$ equal periods, one has $N$ harvesting locations and $K$ contractors who can harvest at those locations ($K < N$). Each ...
- 39
3
votes
0
answers
379
views
In binary linear programming, what's the relationship between the dual solution and the lagrangian multipliers?
In my optimization problem the objective function and all the constraints are linear. The decision variables are binary. [so, it's BLP] Some of the hard constraints are very time-consuming to be ...
3
votes
0
answers
86
views
Resource scheduling problem with synchronization constraints: Weak LP relaxation
I have a resource assignment/scheduling problem which involves assigning jobs to $m$ workers. There are 2 sets of different jobs, $J^1$ and $J^2$, and a set of periods $T$.
Let $d_{jt}$ be the number ...
- 3,396
3
votes
0
answers
75
views
Linearization of a quadratic model, what is the difference while using gurobi?
I have a quadratic model of parking $N$ cars in $S$ separate lanes as follows. Each car has an arrival time and a departure time. Departure follow the last in first out principle. The objective is to ...
- 489
3
votes
0
answers
53
views
How to formulate a storage component?
Let’s say I have a drink for several customers, and I know their demand. Besides, I also have a storage tank for the drink during times when demand exceeds supply. The storage tank's size is not yet ...
- 517
3
votes
0
answers
201
views
Solving a nonlinear model with constraints of exponential functions and continuous variable multiplications
I have a nonlinearly-constrained model and wonder if a nonlinear solver like Ipopt or Knitro can solve the problem.
Briefly, my objective function is linear. I have the following variables with their ...
- 1,239
3
votes
0
answers
81
views
PuLP Python: How to linearize an inequality involving an integer variable
I am working on a Copper payables problem where the objective function is to maximise the sum of copper payable over a time period, T.
The total amount of payable tonnes i.e. what the customer will ...
- 327
3
votes
0
answers
90
views
Linearization of the shifted copy of a function
Suppose in a model I have the expression $y_{1}(x) = 10 + 5 x^2$ where $x \in [0,20]$ is a continuous variable. In order to be able to use an MILP solver, I piecewise linearise $z_{1} = x^2$, by ...
- 2,180
3
votes
0
answers
62
views
Linearisation using SOS2
I am trying to linearise the following expresssion.
$C(k) = B(k) e^{-d(k)}, B(k) \ge 0 , d(k) \ge 0 $
I am trying to do this by using SOS2 sets.
I set $X(k) = e^{-d(k)}$ and I get $C(k) = B(k) X(...
- 2,180
3
votes
0
answers
72
views
Integer variable optimization - decreasing execution time
I have a variable declared as follows in AMPL:
...
- 793
3
votes
0
answers
68
views
Discrete optimization in transport economics
I was working on a problem in transport economics where the optimal number of trips in a given duration of time is to be found out. The profit is a function of the price vector $p$ and time cost $c$ ...
3
votes
1
answer
102
views
Modelling Question
Let $W^C_t$, $W_t$ be binary variables and $p$ an integer variable with $1 \leq p \leq 3$
The variables are related through the following equation:
$$W^C_t = \sum_{\theta=1}^{p} W_{t-\theta}$$
I can ...
- 2,180
2
votes
0
answers
28
views
The facet-defining inequalities for a single resource scheduling problem
Suppose, there exists a scheduling problem $S$, in this case a single resource, with the following descriptions:
$$ \text{conv(S)} = \{x \in \mathbb{R}^n \ | \ \forall \lambda_{i} \in \mathbb{R}^{n+}, ...
- 8,450
2
votes
1
answer
138
views
Using networkx predecessors in Pyomo initialize method
I am working on the directed graph by using the Networkx package and what I need is to use its predecessors' method on an optimization model. Let's say, there exists a directed graph with just $12$ ...
- 8,450