Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
285
questions
8
votes
1answer
123 views
Choosing better objective function for vehicle routing problem
I have a graph $G$ and the following variables.
$b_{i,j}$ is $(i,j)$ edge is taken or not.
$t_{i,j}$ is time to travel $(i,j)$
$A_{i}$, $D_{i}$ are arrival and departure time at node $i$.
My first ...
6
votes
0answers
76 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 ...
5
votes
2answers
217 views
Trade off between number of constraints and bounds of a variable
I am not familiar with the inner working of the solvers. I mostly use the python pulp or IBM CPLEX solver.
For fast execution ...
3
votes
1answer
114 views
Linearizing constraint with continuous and boolean variables
I have two continuous variables $A$, $B$ and two binary variables $x$, $y$.
Condition: if $A = B \wedge x = 1 \wedge y=1$ then $z = 1$ else $z = 0$ from
In an integer program, how I can force a ...
5
votes
3answers
181 views
Reducing number of suppliers for product portfolio
I have the following matrix of suppliers who are able to make a certain product, against all products in my portfolio.
What is the best way of finding the solution to "the least suppliers necessary ...
7
votes
1answer
320 views
Negative reduced cost for basic variable
I am observing something unusual : after solving a linear program, some basic variables have negative reduced costs (instead of $0$) :
...
6
votes
2answers
107 views
Optimising the current model
After developing the MIP model I noticed that solver is taking a lot of time to reach the solution. So, how should I approach to optimize the current model?
Are there any visualization tools or any ...
10
votes
2answers
220 views
Can we have all reduced costs (strictly) positive?
I had a number of students claim on their homework that "All $z_j-c_j$ values are positive, therefore the solution is optimal." Of course, I noted that they should say "non-negative" instead of "...
8
votes
2answers
1k views
How to formulate problems in the language of mathematical programming?
The question says it all. I am having difficulties formulating general problems (meaning no numbers just variables). When I read the solution, I understand but I can't figure how to formulate myself ...
3
votes
0answers
37 views
Extract binary value from continuous variable [duplicate]
I have a continuous variable $c$ which has value in between $[-R, +R]$.
I want to create a boolean variable $x$ and,
$x = 1$ when $c = 1.0$ otherwise $x = 0$
In more general form:
$x = 1$ when $c \...
6
votes
0answers
75 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+...
9
votes
4answers
861 views
Open Source MILP software for Python with user-friendly API to define the optimization problem
Following the accepted answer to
Assignment problem where assignments must be done sequentially
I would like to write a Python script which can solve the problem defined there. It's a Mixed Integer ...
4
votes
0answers
63 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 ...
6
votes
1answer
147 views
How to propagate time using linear inequalities?
I have an adjacency matrix $G_{i,j}$ that tells the distance between $i$ to $j$ (between 0 to 1) if there is no edge between $i$ to $j$ I am putting a large integer $100$.
This is my previous ...
7
votes
1answer
161 views
Is Dantzig-Wolfe decomposition finite if variables are unbounded?
Most descriptions of the Dantzig-Wolfe decomposition, I have seen end up with subproblems like this:
$$\min_{x_j \in \mathbb{R}^n} \{ (\pi A_j - c_j)x_j \mid x_j \in P_j \}$$
They argue that $P_j$ ...
12
votes
1answer
99 views
Improving cuts from sub-problem with problem-specific hierarchical information
I'm solving an assignment-alike problem with a Logic-based Benders decomposition-alike (LBBD) method. The master problem provides an assignment, which is checked in the sub-problem.
Define the set of ...
8
votes
2answers
129 views
Bounding arrival time at a node in a resource-constrained shortest path problem
Given a city map (a graph) $G$,
$b_{i,j}$ is a Boolean variable for whether or not edge $i$,$j$ is allocated, $d_{i,j}$ denotes the distance between $i$,$j$.
The objective is to move from $s$ to $e$ ...
7
votes
1answer
75 views
Linearizing objective function with absolute differences
I want to turn this objective function
$$\max \sum_{i=1}^{N-1} \sum_{j=i+1}^N |TX_i^T - TX_j^T|$$
where $T$ is just a vector with increasing integers (e.g $[1 \ 2]$) and $X_i$ is a vector ...
5
votes
1answer
153 views
How to model shipment size constraint?
I am working on an LP problem where I have to model a constraint as:
"The total number of units of product A and B should be shipped in multiples of $1200$"
e.g. $700\text{(product A)} + 500\text{(...
4
votes
0answers
162 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 ...
5
votes
4answers
201 views
MIP for similar production percentages in production planning
As a task, I want to produce three products $x,y,z$ in different quantities $a,b,c>0$ respectively.
It is not always possible to produce the full amount of each product, because of a lack of ...
5
votes
1answer
200 views
How to express this constraint?
I have the constraint \begin{align}\max&\quad\gamma\\\text{s.t.}&\quad a\ge\gamma b\\&\quad\gamma\le 1\end{align} where $\gamma$ is an optimization variable and $a$ is a function of some ...
6
votes
1answer
166 views
GUROBI Re-optimize a model
(For Linear Programming) I am aware of CPLEX's reoptimize methods. If I am not wrong, if you solve a problem and after that you add a new constraint, then you can call the reoptimize method for not to ...
4
votes
1answer
327 views
CPLEX Python API
I am trying to run the following optimization problem at Python by using the CPLEX API:
$$\min \{x_1 + x_2\ | \ x_1 \geq 3, x_2 \geq 2, 2x_1 + x_2 \geq 9\} $$
I just want to give a matrix of ...
10
votes
1answer
261 views
LP sum of variables that are above a threshold
I am trying to code a constraint of the form:
$$\sum_i y_i < K\,\text{where}\,\begin{cases}y_i = x_i\quad\text{if}\,x_i>k_i\\0\quad\text{otherwise}.\end{cases}$$
In other words, I want to ...
8
votes
1answer
227 views
Speedup or Caching for a Multi-Iteration MIP problem
I'm solving an MIP:
\begin{align}\mathrm{arg\,min}&\quad\sum\limits_{i}{x_i}\\\text{s.t.}&\quad A\,x\geq1,\end{align} where both the matrix $A$ and vector $x$ are boolean valued, and $A$ is ...
7
votes
2answers
271 views
shadow prices associated with nonnegativity constraints
Why are shadow prices associated with nonnegativity constraints also called as reduced costs, even if they have the same interpretation as shadow prices associated with an optimal solution? Why the ...
12
votes
1answer
252 views
LP how to sum up positive free variables and negative free variables separately?
For an LP problem where $x_1,\dots,x_n$ are free variables (which may take positive or negative values), I want to bound the sums of $a_i\cdot x_i$ where $x_i>0$, and where $x_i<0$.
I suspect ...
8
votes
0answers
66 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 ...
8
votes
2answers
263 views
Max flow problem without splitting the flow from the supply nodes - LP formulation help
Since max flow formulation can be easily solved using LP, I wanted to ask the following:
I am trying to solve a simple max flow problem where the graph is bipartite but with one added constraint. The ...
15
votes
2answers
246 views
Search approach to solve optimization problem with only a minimum where time series get scaled
Currently, I am working on a relatively simple optimization problem:
There is a set of time series (red) that get summed up to a cumulated time series (blue). The red time series have different forms ...
11
votes
1answer
81 views
Variable Sensitivity Analysis
I am working with the following MIP :
\begin{alignat}2\min&\quad\sum_{j\in J} c_j x_j\\\text{s.t.}&\quad l_j \le f(x_j,t_j) \le u_j \quad &\forall j \in J \\&\quad x_j \in \mathbb{N} \...
5
votes
3answers
1k views
Finding a solution to a linear program with a small number of zeros
It is known that, in a linear program with $k$ constraints, there exists a basic feasible solution in which at most $k$ variables are non-zero. How can I find such a solution?
Is there a polynomial-...
13
votes
2answers
328 views
Black-box optimization with linear programming?
In my research, I do a black-box optimization based on a simulation model with nonlinear properties. The simulation model gets an operation plan for a time period and then returns a time series, which ...
8
votes
1answer
298 views
Is there any relationship between KKT and duality?
I noticed the similarities between KKT and complementary slackness, but I do not fully understand it.
3
votes
2answers
188 views
Find all Combinations of a Matrix
I have a $16\times11$ matrix and want to find all eligible* combinations of this matrix including always entities from all 11 columns.
A simple example from a $2\times3$ matrix would be the following:...
9
votes
1answer
114 views
Introducing a big M variable in given equations
While I do understand the general workings of the Big-M-method I am struggling with the following sample exercise, in which the Big-M-method has to be used to find a first feasible solution:
\begin{...
8
votes
1answer
160 views
Is this formulation linear or non-linear?
Can you help me figure out if this formulation constitutes a non-linear problem? I believe It is a linear problem but my solver (GAMS) is unable to produce a acceptable solution.
$x,y$ and $\text{...
7
votes
2answers
144 views
Linear constraint formulation (OR-statement)
I have the decision variable $X_{iz}$
And I have two parameters $T_i\in\{0,1\}$ and $IT_z\in\{0,1,2\}$. I can only assign $i$ to $z$ if the following holds:
for $T_i=0$, $IT_z$ needs to be $0$ or $2$...
8
votes
1answer
222 views
GLPK: meaning of the "marginal' column in the solution output
I'm using GLPK to solve an LP.
I use it through its standalone solver, that I call with the glpsol command, and I get the solution detail written in a file using ...
17
votes
3answers
962 views
TSP with revenue maximization
How to approach a travelling salesman problem with an aim to maximize revenue at each town visited in a certain number of days (total number of towns is greater than what can be visited in the given ...
10
votes
2answers
176 views
Linearization $\max(c_1 x_2, c_2 x_2, \ldots, c_nx_n) \geq q$ constraint
I have a MIP minimization problem where I have a maximization in the constraints:
$$\max(c_1x_2,\, c_2x_2,\, \ldots,\, c_nx_n) \geq q$$
Where:
$c_n$ constants
$x_n$ binary variables
$q$ constant
$...
9
votes
0answers
70 views
What to do with cuts (constraints) when a fixation is contrary to a RHS in a ILP / LP relaxation?
I am trying to understand an algorithm in a paper by Crévits et al. (2012)1 (see algorithm 2, the cuts I'm referring to are from the reduced costs). It uses a series of successive cuts on a linear ...
11
votes
1answer
369 views
Linear programming with if-then-else (big-M)
I am trying to formulate the following in linear programming.
\begin{cases}\text{if}\,\,a>b\,\,\text{then}\,\,c=a\\\text{else}\,\,c=b.\end{cases}
I tried some things with big $M$, like $$a + my &...
11
votes
2answers
717 views
MILP: is it NP-complete or NP-hard?
The pieces of information I get online are sometimes confusing. Someone says MILP problems are NP-hard, and somewhere else I found the claim that MILP problems are NP-complete. Can someone please ...
8
votes
2answers
917 views
Complexity of LP and MILP Problems?
My original problem is an MILP. I make it an LP by relaxing the integer variables.
Can someone please comment on the complexity, solvability and optimality of MILP and LP problems, in general?
Is ...
10
votes
1answer
129 views
How to access neighboring extreme points to an optimal extreme point of an LP?
Suppose that I have access to an optimal non-degenerate extreme point of an LP. I need to find some $\epsilon$-optimal extreme points. That is, a point $x$ where $c'x \le z^{*} + \epsilon$.
One way ...
9
votes
1answer
143 views
Finding Dual Objective
I have the following simplified optimization problem:
\begin{align}\max &\quad ax+by\\\text{s.t.}&\quad0 \le x \le \overline X\\&\quad0 \le y \le\overline Y\\&\quad z = E-x+\beta\cdot ...
10
votes
3answers
1k views
Is there a heuristic approach to the MILP problem?
I have the following optimization problem which is a MILP. I can solve it with a MILP solver.
\begin{align}\min_t&\quad t\\\text{s.t.}&\quad d_{c}-t\le \sum_{n=1}^{N} B_{n,c}x_{n}\le d_{c}+t,...
9
votes
2answers
149 views
Linear Programming: Objective function goodness if variable holds value above a given constant value
In a Linear Programming formulation, stating that a punishment is to be introduced in an objective minimization function if a variable $S$ holds a value above a given constant $K$ ($K = 35$ in the ...
