Questions tagged [linear-programming]
For questions related to problems that optimize (i.e., minimize or maximize) a linear objective subject to linear constraints.
37
questions with no upvoted or accepted answers
9
votes
0answers
69 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 ...
9
votes
0answers
122 views
Ill-conditioned LP in Bender's decomposition
I have implemented a Bender's decomposition for a constrained network flow but the LP solver (Gurobi) warns me of the ill-conditioning of the slave dual LP. As you can see below, the coefficients seem ...
7
votes
0answers
74 views
Provide basic solution to CLP
I'm using Pyomo to formulate an LP with approx 500,000 constraints and 200,000 decision variables. The LP is solved using CLP. Some instances fail to return even a feasible solution after many ...
7
votes
0answers
136 views
Modeling traffic in a city
I am trying to model traffic in a city, $(i,j)$ represents a road in a city.
There are $H$ vehicles in a city they have some prescheduled set of destinations to visit, $A_{j,h}$ denotes arrival time ...
7
votes
0answers
62 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 ...
6
votes
0answers
53 views
Estimating multistop routing costs
In many OR problems, it is sometimes a good idea (or necessary) to relax routing constraints.
An example of this occurs in the classical facility location problem, where a warehouse can send out a ...
6
votes
0answers
60 views
Proof that the leaving variable cannot be selected as the entering one in the next round
Using the Dantzig's pivoting rule, can it be proven that the leaving variable of one round cannot be selected as the entering variable in the next round?
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 ...
6
votes
0answers
73 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+...
5
votes
0answers
100 views
Obtaining the system of irredundant inequalities from a set of inequalities using CPLEX
Given a linear system of inequalities $Ax \geq b$, I would ideally like to compute the irredundant set for those set of inequalities. I know how to do so mathematically, but I was wondering if there ...
5
votes
0answers
115 views
Is this a valid strong polynomial algorithm for deciding LP feasibility?
Let
$$A \cdot X + B \preceq 0$$ be a system of linear inequalities with $X \in \mathbb{R}^n$ $A\in \mathbb{R}^{m\times n}$ and $B \in \mathbb{R}^m$ where $m \geq n$. According to Farkas lemma, exactly ...
5
votes
0answers
54 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 ...
5
votes
0answers
31 views
In a binary logistic regression context, how to introduce a constraint to model the dependency between consecutive samples
Imagine we are running a logistic regression to identify opportunities for car sale promotion, using previous promotion campaign's result. Each $y$ is the increase of car sale after the promotion.
...
5
votes
0answers
92 views
Construct a direction of recession of the dual that is from growth to dual function
Consider the primal problem $$\begin{array}{ll} \text{minimize} & c^\top x\\ \text{subject to} & Ax = b\\ & x \geq 0\end{array}$$ where $ A \in \mathbb {R}^{ m × n}$ has rank $m$. Suppose ...
4
votes
0answers
99 views
Does anyone have the criss cross algorithm programming code to solve linear programming problems?
I have a project that requires programming code for the simplex algorithm and criss-cross algorithm. The purpose of this project is to compare the two methods. I've tried to find it, but the ...
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 ...
4
votes
0answers
160 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 ...
4
votes
0answers
188 views
How can I formulate this multi-objective optimization problem?
Now, for each system $X$ $(X=A,B,C,E)$, my objective is
$$\max\min\frac{s_{x_u}}{d_{x_u}}$$
here, $x=a$ for system A, $x=b$ for system B and follows...
and for the whole system, my objective is
$$\max\...
3
votes
0answers
44 views
Simplex method on graphs: How do I find a basic solution using the Ford-Fulkerson algorithm?
I'm tasked with solving a minimal cost flow problem. I'm asked to first use the Ford-Fulkerson algorithm on my graph to find a basic solution that will then be used to do the simplex method on that ...
3
votes
0answers
29 views
Linear functions in Lenstra's algorithm
I had asked this question at MathOverflow and was pointed here.
I'm working on implementing Lenstra's algorithm. At the bottom of p.5 (at "construct $n+1$ linear functions"), he says to ...
3
votes
0answers
92 views
On solving the Restricted Master Problem in Column Generation technique
I am working on developing a column generation (CG) based optimization framework for a large-scale airline crew pairing problem (a set-covering problem). First, I generate an initial feasible solution ...
3
votes
0answers
33 views
Constraint equivalence in PuLP
I'm working on an optimization problem in PuLP and I have to enforce a daily minimum of shifts and a daily maximum of assigned shifts. I have the following constraints to ensure each day has a minimum ...
2
votes
0answers
46 views
Reading MPS file for linear programming and reconstructing the Optimization model
Are you aware of any tutorial that can help me learn on how to reconstruct the objective function and constraints from a MPS file once it's loaded in MATLAB. I can load the mps file given to me and ...
2
votes
0answers
84 views
Condition for an integer program and its linear relaxation to have the same value
Let $A$ be a $(0,1)$-matrix where no row or column is a zero vector, and consider the following optimization programs \begin{align}(1):\min&\quad y\cdot1\\\text{s.t.}&\quad yA\ge w\\&\quad ...
2
votes
0answers
40 views
High-mix manufacturing capacity
I'm not an expert in OR but I would like to determine what is the maximum manufacturing capacity of a plant (or how much a plant can produce of mix products).
Each person in the plant has a known set ...
2
votes
0answers
67 views
Finding Optimal Route using different Paths
I have a list of paths e.g. path 1 takes you from point A to B. A person needs to complete 5 of such paths.
$$Route1 = path1 + ...
2
votes
0answers
52 views
Linear programming: extending problems yields non linearity
I had a linear programming problem with the following objective function
$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$
Where $q, p, C, c$ are known. Let the term ...
2
votes
0answers
55 views
Weapon Target Assignment Problem + Time Windows
So I am very familiar with the WTAP it the static case. What I am wondering, is there a formulation that has "time windows" as well? Let's say you have some weapons and some targets, you know the ...
2
votes
0answers
38 views
Public available MPS files with semi-continuous variables
Is there some MPS files with semi-continuous variables public available anywhere?
To me it seems MIPLIB does not contain any.
Erling
2
votes
0answers
57 views
Dantzig decomposition and Column Generation for equality constraints
I was trying to apply Dantzig Decomposition followed by Column Generation. The following is how I was taught.
\begin{array}{l}
\text { Minimize }-10 x_1-2 x_{2}-4 x_{3} \\
\text { subject to: } x_{1}+...
1
vote
0answers
53 views
How can I formulate an LP or heuristic solution for this problem?
[I welcome any alternate or simplified formulation of my problem]
I have an optimization problem. See the attached figure which is self explanatory. The solid line is intended signal, the dashed lines ...
1
vote
0answers
78 views
Expansion heuristic using gurobi reduced cost / shadow price (LP)
Gurobi 9.0.0 // C++ // LP
Let us assume the following problem with three nodes: (1)-----(2)-----(3)
node (1) is producing ...
1
vote
0answers
274 views
Canonical form of a linear program
I have a linear programming problem that I want to write in the canonical form: \begin{align}\min&\quad c^\top X\\\text{s.t.}&\quad A\cdot X\le b\end{align}
The problem is given by \begin{...
1
vote
0answers
39 views
Verifying the correctness of KKT conditions
I have a LP problem and derived the corresponding KKT conditions for the same. I simulated the LP and obtained the primal and dual values and manually checked if the KKT conditions hold. Is there any ...
1
vote
0answers
56 views
Linear programming with correction term based on decision vector
I had a linear programming problem where I am optimizing some function
$$f(x) = \sum_{j}x_jq_jp_j - \sum_{i}\left(\sum_{j}x_jq_jC_{ij} \right) c_i$$
Where $q, p, C, c$ are known.
I now want to ...
0
votes
0answers
111 views
Resource constrained LP problem
I am working on Diet Allocation problem. Where we need to provide food piece for protein deficiency. The data is as below:
...
0
votes
0answers
94 views
Need help in formulating linear program
Edit: updated my solution for linear programming
Can anyone explain the following passage?
Both semiconductors and power generation industries also want to buy as many of the remaining units as ...
